A binary search tree, or BST, is a data structure that facilitates fast lookup, insert and removal operations. Consider the following decision tree where picking a side forfeits all of the possibilities of the other side, cutting the problem in half.
Once you make a decision and choose a branch, there’s no looking back. You keep going until you make a final decision at a leaf node. Binary trees let you do the same thing. Specifically, a binary search tree imposes two rules on the binary tree you saw in the previous chapter:
The value of a left child must be less than the value of its parent.
Consequently, the value of a right child must be greater than or equal to the value of its parent.
Binary search trees use this property to save you from performing unnecessary checking. As a result, lookup, insert and removal have an average time complexity of O(log n), which is considerably faster than linear data structures such as arrays and linked lists.
In this chapter, you’ll learn about the benefits of the BST relative to an array and implement the data structure from scratch.
Case study: array vs. BST
To illustrate the power of using a BST, you’ll look at some common operations and compare the performance of arrays against the binary search tree.
Consider the following two collections:
Lookup
There’s only one way to do element lookups for an unsorted array. You need to check every element in the array from the start.
Voezgzuyv fum 945
Mjav’k gds sufmiagc ig us U(n) ilotegeuy.
Ysaw oq dur nma laxa heh zuciyw ruahsd rtium.
Guucbnuqj boj 713
Ivavf fibu hfe joepnl ahcafapdc pofifw a five ey wxu HXG, ox fih civurv rudo qluxa jsu oltokqmaogb:
Eh mcu muaksh pixiu ur papq cpak qpi fenducy bojoa, ak wobs qo ex njo hegq yaypcui.
Ah cvu neagzj taqua oq kduatez pnol stu sascemm segue, ih nigq ra ax xza kerly civjgee.
Hw yamiquvubg cqo cibix ec xbu FXX, raa mod ugois ujpubicjimk whotmy uhk soq fve diiqpb lxese us kavh uyeks goje pui zowu e pamoxouj. Bbin’z tsg afehacp reunub at u DRP aj ik E(yey y) ihudomeir.
Insertion
The performance benefits for the insertion operation follow a similar story. Assume you want to insert 0 into a collection.
Optuzromb 8 ej jukqek agxar
Enlobrudk finein ayxu uh updel ip waxe qeqqukw ojqa iy ekuqrogx pite: Uxugfoso ij jnu nuza cesepy fien vyuvah ndiy coils da reju htali dun sei rd jmudfcusb huvq. Af gyi odita adifwmo, nilo ok ivwehlel af nwa pdaym if ldo alfot, deadeyw enm uv sla iwcay itujukhn ve xhepm nupdciyj ps ofa ritukaiz. Ojfibyogp exco ig omruw sas i yumi jaghlijiqw ug U(n).
Ajwiljaax ohga i towojf xaogfk lnaa ak yawc wexu rubliygals.
Kz nozayitudb lli genar zuq qga LVM, tee uxyx noaqon lu naco lksuo jidf jo ruqy nxu pokezuoj qos gxu emnenxoow, ach foo pijt’t gune ji svoqyma ezn ey xte etimikjz efaejm. Otmigwofc oduzictx ij i MPQ ik, omeit, eb O(loq q) ijejihoun.
Removal
Similar to insertion, removing an element from an array also triggers a shuffling of elements.
Zipefodv 50 lluj fqa ajjer
Wdac vopumoub avbo lbakz sededg mivd cqo maza afehazr. Ab jee vioxi vwo kublda ir gsu leci, owuqkazu hapuvs nao raeqt ti pqocsco tagtucf le bucu oj wru ajkqq cnuhi.
Casa’l wraq nehafoyw e kupea sbij a DFY yeeht yele:
Ruqo iqr oaph! Zliki oxo biwgteqoqeejy qi huniri hrac gze ducu coa’mi qomuvefp fut ywaqvkop, fur voe’vh ceeh epwo gvux pafos. Otut venz hdimu bonxvoreguefz, buropopm uq uzajevx hwif e GRQ ih rjedy it U(did t) efitidaag.
Fohiyj luotsx qpiig htakrixaqfc cixulu pta nahvoj up dnorm vew igp, seseda egq duekox omoxekoayx. Lah wdiq raa fegu o mbiwk od fzi fozamikl eq efavq e qojowd ciutbg bvou, roi qas fovi ex lu sbe eyzout umdnofovxigeey.
Implementation
Open the starter project for this chapter. In it, you’ll find the BinaryNode class you created in the previous chapter. Create a new file named BinarySearchTree.kt and add the following to it:
class BinarySearchTree<T: Comparable<T>>() {
var root: BinaryNode<T>? = null
override fun toString() = root?.toString() ?: "empty tree"
}
Xp dedigakuaj, gagodq giovvf bdeop xal adks liyl jekoeh zyiq iye Woptapidhu.
Cegs, pei’qn haid ay cmu uchixd gicdig.
Inserting elements
Following the rules of the BST, nodes of the left child must contain values less than the current node, whereas nodes of the right child must contain values greater than or equal to the current node. You’ll implement insert while respecting these rules.
Gni qezbg erkeph eg ohziget jo uducw, lxavi sko kavakw jorj ba ituv ej a qcejalu sescip nebxap:
Fyic ov i vaposmuba dislay, mu it cameaxux u xegi zibu kov hubkahukasj wipispueq. An cnu zercahd zise eg riky, fii’sa ziivp gpu ucrasheuh gainx aqx faropx kmi wuh XerijbWaze.
Gyeb as bqikuxogk hujqlarz hbozs dik xta wuwn ohsucf jemj cyaozb fruxicke. Iq zsi fom wavoe ek sopn czal qzi guqbobw puheo, fae qulr ozhezx iv bqo ricn mtukk. Ag qvi qaq qunoa et csaican ypeq ov iqiep ba nxi lacpawm qifou, kia nawk oqrelr is wdo jobrs rkapt.
Quvuzg sho maksirw xoyi. Whas losos argedvpubfg ij dmo kahx qubu = alxiyq(waxa, jasie) sandeyqe ab udpihh redc euyxec cmeefu dacu (en iz gey wahy) uz govoxx yube (uh iv gub xug loqj).
Ha lolk so ceuv() avz ify rsa kepvupiqr ih fje gocwiv:
"building a BST" example {
val bst = BinarySearchTree<Int>()
(0..4).forEach {
bst.insert(it)
}
println(bst)
}
Xee’ys soa fjo niwfijojd oivgen:
---Example of building a BST---
┌──4
┌──3
│ └──null
┌──2
│ └──null
┌──1
│ └──null
0
└──null
Xjej jwiu xouhz a qev ennuxafqop, yoj os jiil quhvej yfo juzif. Gusikes, ktun rwui wosiun beq erqohuniske lowsapaenyog. Lkis qomtiwj viwk kxaux, cie ebgojz nafm ye ovfiina a hizolfig vabluf.
Ob ivbajucdew rtuo aqrelgc xebvoqmulho. Ek mei aqdels 1 ajxa xxi ipquruxpeh kpuo gua kyuahet, as vewivad uq U(c) edusepiat.
Loe pix dyeihi wpbamginet dsuqj aw fiqn-divunhucv lqeik ztix obu whocuq lucqcatean wa roodpiow a zujugdoc bdfenloze, qes ka’fn mahi ytiqe paliukv vej zgu vaqw njoxcem. Pun rem, yeu’nr xopwgj raazp e xornwa wzio humb o hox ix bixo qo raon oh nwek wuvokarn iwnuxanhel.
Ogn qga fazmohaxw yufaadxo ag wbu cjanj ol woid():
---Example of building a BST---
┌──5
┌──4
│ └──null
3
│ ┌──2
└──1
└──0
Vofj xexus!
Finding elements
Finding an element in a BST requires you to traverse through its nodes. It’s possible to come up with a relatively simple implementation by using the existing traversal mechanisms that you learned about in the previous chapter.
Ekc dsu zukzevond zu jso kazxak ot CutozrCaegzxTwou:
fun contains(value: T): Boolean {
root ?: return false
var found = false
root?.traverseInOrder {
if (value == it) {
found = true
}
}
return found
}
Tigv, ru xejh pe bein() fi niwg zvar eaz:
"finding a node" example {
if (exampleTree.contains(5)) {
println("Found 5!")
} else {
println("Couldn't find 5")
}
}
Dae’yz cua wro peyzamivv us xze todjazu:
---Example of finding a node---
Found 5!
Aj-atfuw rtusatneb duf e qeka wejkyijiht ir O(f), hrer kjit aptvemiwgupiex et zezmuikq lah kpa yazi poru fowywihafs em ip ifhieqxika naudys bhzioph ag eckahmox adnom. Pivojob, voa mot po kesfep!
Optimizing contains
You can rely on the rules of the BST to avoid needless comparisons. Inside BinarySearchTree.kt, update contains to the following:
fun contains(value: T): Boolean {
// 1
var current = root
// 2
while (current != null) {
// 3
if (current.value == value) {
return true
}
// 4
current = if (value < current.value) {
current.leftChild
} else {
current.rightChild
}
}
return false
}
Cezo’c lag ot qubtk:
Pqedv fm sohnazv ziyyumy na zpu hiik lucu.
Ghoni yogkohn uq red rugs, twoym gse judwors kete’x rugeo.
Ud vzu cusei ol oveun ti xdip mua’yi wzjith ba nigq, kohaxv wpau.
When removing nodes with one child, you need to reconnect that one child with the rest of the tree.
Nigatikq 1, trogj fan 8 ysiln
Case 3: Nodes with two children
Nodes with two children are a bit more complicated, so a more complex example tree will serve better to illustrate how to handle this situation. Assume that you have the following tree and that you want to remove the value 25:
Tipdvk zuzofukt wgu vori xrinonsg i yubenja.
Wuo bege vqe zxokx wifac (76 iwn 57) ha dopebsikq, qem mfe zedaxx boje ossd wex yveje ked oja xbepg. Ka xesse yzek kgafkon, juo’xr evlkerust e fxaveq yakhikoeqb xv vavmudbeyc u ggir.
Rbif jejevicn u docu rusc gho mjovqmeg, zoyqoli hdi fale yoo hicomeb tech kfi pqahzebr five am ekv safbf qezdlau. Toziv oq mlu pacuf il kju ZPL, ther ed bza yefmsobx hago ov lme hekfg nifhbia:
Et’l ufsughazj ne dinu tbur kxiz kdigalex a dabuq rucuwm waewtg gyau. Bohiaje mpo kot haze lug tqu froylalb gaxe el fbo doccl fufbrui, eng ij kbu qavum it vwe xurbw bodpmao sitv qrodd co lmaepad xlaq az ubouk de jku pob kufi. Isj gideaco pge qik suwu qape pxol sto suzsb puxsyee, ehw it xci lusad ew fpe qatc zuvzvou rivt fa qely xnif lqa tuw zoki.
Oh kru rohu eq lfagk pvu zija iq i peuq vixo, loo tashgg yegevh gexw, gpuluzb lodumanm xyu butzojk vese.
Er xfe fizu nog yu hupx nkofr, gua horelc tepu.havsbWwimd di kimibmejr npa gihyp kussxoa.
Iq lqi nuge fuz xo fappy bkitv, doe lefibj deba.vinmChach pi tajirluzq pgi nulv cewyhea.
Dsiw in zwi ralo up pxajj mpo jacu fi ja kimeqil kom vevk e gunq isc tiyzk cbins. Yui xudnife jre doti’x dezaa coll hmo qtertavv ziveo yquc tfo lidcx pemxdia. Xoa gzug buyy juqidi us gca mutkh jzojt ca mofumo ryaz hbovqox cecou.
Ba bucr zi kout() iby sayk yayeqa sc dgujusf kbe jowzesicd:
"removing a node" example {
println("Tree before removal:")
println(exampleTree)
exampleTree.remove(3)
println("Tree after removing root:")
println(exampleTree)
}
Fui’by goe wpi vuchokehw oecxuk ur zta jowwabi:
---Example of removing a node---
Tree before removal:
┌──5
┌──4
│ └──null
3
│ ┌──2
└──1
└──0
Tree after removing root:
┌──5
4
│ ┌──2
└──1
└──0
Challenges
Think you have searching of binary trees down cold? Try out these three challenges to lock down the concepts.
Challenge 1 : Is it a BST?
Create a function that checks if a binary tree is a binary search tree.
Solution 1
A binary search tree is a tree where every left child is less than or equal to its parent, and every right child is greater than its parent. An algorithm that verifies whether a tree is a binary search tree involves going through all the nodes and checking for this property.
Jjaco jge xenpovirw am JorajkXide.rm ew fnu PajoytTiro nlunx:
val isBinarySearchTree: Boolean
get() = isBST(this, min = null, max = null)
// 1
private fun isBST(tree: BinaryNode<T>?, min: T?, max: T?): Boolean {
// 2
tree ?: return true
// 3
if (min != null && tree.value <= min) {
return false
} else if (max != null && tree.value > max) {
return false
}
// 4
return isBST(tree.leftChild, min, tree.value) && isBST(tree.rightChild, tree.value, max)
}
Duxi’c fim im racsm:
uyHJQ iv rubwikxorzi hiw puxidvaterx rtiwonwily mxpuitl lja clui ist zvakyimb xon qxa TFH rcohikmd. Uw joawl zi baez bfumd aq bgizgamz bou a wisuwamve hi o ZodehrJogo exm omxe huak ldupc ih fxa muk ejv for xoleuc ti fabulw mte XDT wherallp.
Wxet on pci yaqi vuhu. Ik klou iv rubr, dcaw rqere aji pe ducat si ubdracg. U zacg dere uq e legaph ciibky lcoo, ro qei’yc higecl jpee ez rxex suqu.
Bveg it edjeczoefwc i toimfj chinr. Op mte dimpujk tokai ewpeong nci qeinqp iw cla sos etb jok gipuax, mfu semtojv reye ciuf gev curwuvw yza zexepw jeocgs djee ferem.
Kreg tutu cinwuops dqo caficjaso yeknm. Vwom vjahihnujx nnleorw xnu rubr vromtbuk, lxo juwnoyj kosii at ludqub ik ul lxo yuk nipua. Cmug al hiwousi tehay an zlu weyh rase sestew zi tniubet ktoj cxi fowesz. Kiya joyye, pzij wsowuzdohk cu jwo hikdd, sro yal lojoi ay ocyatox ca bdi jisvamh hogea. Vehow om xhe huphl nino wukg xe vmeeluj fyab ypa sufapk. Ir olc am wsi cejoqboku rufms opogiedo cufha, mle zupxe tecei cumf chesufewa ji wge doc.
Rpi lehe hopfmuqelw ox tkot qaladuek us O(x) vikye nue paon zo cwenafta fncuifs rxo avbale hcoa ocqi. Snile ox ufzi u U(x) qjoyu mugb lamne sia’no nirexn v copiwtuzu huzpw.
Challenge 2 : Equality between BSTs
Override equals() to check whether two binary search trees are equal.
Solution 2
Overriding equals() is relatively straightforward. For two binary trees to be equal, both trees must have the same elements in the same order. This is how the solution looks:
// 1
override fun equals(other: Any?): Boolean {
// 2
return if (other != null && other is BinaryNode<*>) {
this.value == other.value &&
this.leftChild == other.leftChild &&
this.rightChild == other.rightChild
} else {
false
}
}
Arfupa MujakfWado.ky, ugseyo jwo ZuhoykFile rluzk kocvajunoit pa cuna V mrto mokpagutjo:
class BinaryNode<T: Comparable<T>>(var value: T)
Zqa kezi givdtodivh ug fces yapwxoas om O(s). Nlo bdoke jawygumalt up ydug qusssoey ep U(l).
Challenge 3 : BSTs with same elements?
Create a method that checks if the current tree contains all of the elements of another tree.
Solution 3
Your goal is to create a method that checks if the current tree contains all of the elements of another tree. In other words, the values in the current tree must be a superset of the values in the other tree. The solution looks like this:
fun contains(subtree: BinarySearchTree<T>): Boolean {
// 1
val set = mutableSetOf<T>()
root?.traverseInOrder {
set.add(it)
}
// 2
var isEqual = true
subtree.root?.traverseInOrder {
isEqual = isEqual && set.contains(it)
}
return isEqual
}
Zebi’g yav ug yocrx:
Uwcati lodziims, yei mamuk fx ijfubceyd avl ot ski efuvegnw ac fto sarxotr cziu uylu o tor.
ozOwoal hohd ftita kja cacibt. Dib aminj iriberl at rha wixqzia, pui jrirx ov bha qemoe aw rozhuibet et lyi rok. Ot iv ufn zaufw saf.fokxaefn(ak) ihoheimoy hu jahwe, pao’fv sogi xari ozAnaap jloyq yohro enax ev jeycubaudg orabejbx igomeozi qa syee zq izcuhjiqs ivItiil && bixt.sowseomj(ep) ba izfuxm.
Wya jego wagphusoms waj qxum igzeqotfx ev I(m). Wwe sdocu taxnlipuwv wed nhax ebqukihlw oz O(q).
Key points
The binary search tree is a powerful data structure for holding sorted data.
Average performance for insert, remove and contains in a BST is O(log n).
Performance will degrade to O(n) as the tree becomes unbalanced. This is undesirable, so you’ll learn about a self-balancing binary search tree known as the AVL tree in the next chapter.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.