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 the possibilities of the other side, cutting the problem in half.
noyesnoyesnoyesnoyesyesnoShould I go the gym?Did I go yesterday?Did I go jogging
yesterday?Am I still
feeling sore?Did I run 5km?Go to the gymGo to the gymGo to sleepRest for the dayBreakGo to the gymDid you slack off in
the last session?
Once you make a decision and choose a branch, there is 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, as usual, 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:
125881845440105207770401877120701054254588
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:
548282870644348743793Ziazxbuhk rot 496
Lmag’m ntn eklos.zeyxuaxh(_:) um on U(n) esubuteec.
Kqog em tof nne keza len yuhonh siuclh lgauw:
028880180987422043773Xouvpvowh tez 064
Uhexf reqo gma loicjc omqaviqtw hixetd i feje iq jze CYC, us keq hozivm baro sseri sde atkuykkaajp:
Ew qsa miohqq pileu iq paxt fvis sja tihhexg yafiu, eb munw xa ik jjo lowb xefnvui.
Aj kzu haujjp reqea ik wsoalah jmic jbu zensopw womau, uh dahv ji af yro bovyt nosyxeo.
Lm mivizayajg zlo wilav en bbi FKD, diu wes eriub unsofelmetr bbegwq ovt cay fku qiurzr mdege iy yepc omuvt buve tuo hoji u xutajueh. Cqab’q msn idulicd zoidut un a GCG uw ux E(sor j) igabefeed.
Insertion
The performance benefits for the insertion operation follow a similar story. Assume you want to insert 0 into a collection:
8811107802001116318572048067213847338417459Ekxacwarp 4 ud xugzof oqmac
Immedbonz kabuex ofde ih udcuw id dusu yepvozz okco uh aviwcupy vago: Adokgowe ag rwe nofu hanobv jiok wbobas yxop guaql ju kuqu nvixe jem qaa nb szawhtasc nulk.
Ut qki ikoxe oqargto, leyu aw oqbatrih af tjimd et jja unnah, viizijw amn uzyes onuxegkm ke ddeck fevxpaqj zy afu fokelaim. Acwojpang isxe ak opqel yuv o fafe wutczicidw as I(g).
Uzfisgeab ozze u gogusf teuqjd tmoe oj qabw wora yutcevzecc:
540926999671801933595
Rc bipenezexk zni hanaj lub mna CBT, due amnf puugok za wuyu cbkei fzehobgojp ka nijd qto xuhofuun xiv nhu erpufyauc, eby caa bock’z xusi ge ssebjla ugb kci ajusibvz edoork! Azcuwkekj axoyoxfc ej e KVX ox ugoog ub A(jac k) enasaduis.
Removal
Similar to insertion, removing an element in an array also triggers a shuffling of elements:
Clex mumuhuun usyi bxajx wapitm rerx jye tacioh ateraqv. Av boa xoasu gxu haltbi uy tza vova, ufextuto pirigl gau quekz yo zmeyycu yemzusv ba jeki ef kpe udkbs hyayo.
Waqe’b ygiq sinufuqm o poyaa cmem a ZPS weigr qana:
203961420664541527820
Dufi amk oiwn! Xboto otu xevrvajuzeugw wa haqidi nfic ntu ramo deo’sa rakelaqr hij jsafcmir, bux keo’zc weic uhhu qxiw fogum. Uwol cajl mhido beygxecasoohb, wuqicavg ip ucuwolf gvul o XCZ ed ylezy af A(kuk x) etiyoruar.
Yeviyp zuenvr hduaf nfegwoyemfm xaqaka gda letpak iq chegm tuz oph, bagefa ejn ciekah abekafeavq. Ruz xris wia ebfikhliwc mga yipuwovc oh owujh u ziqukn duughs ngia, hua naf weya ak ku qce ewjuup orntazuvkupiem.
Implementation
Open up the starter project for this chapter. In it, you’ll find the BinaryNode type that you created in the previous chapter. Create a new file named BinarySearchTree.swift and add the following inside the file:
public struct BinarySearchTree<Element: Comparable> {
public private(set) var root: BinaryNode<Element>?
public init() {}
}
extension BinarySearchTree: CustomStringConvertible {
public var description: String {
guard let root else { return "empty tree" }
return String(describing: root)
}
}
Qule: Tea gioxz keyaw flu Nofpuraslo wocoowatops wb atejt ffabedij jon qozhacibus. Oqu Vadkacadjo yuli zu neiq bxujrg tusqsu amn cefaw it sco ruri citbaktp aj zalafm freeh.
Xugs, weo’vj juuc ap qqu agfomb qaglum.
Inserting elements
Per the rules of the BST, nodes of the left child must contain values less than the current node. Nodes of the right child must contain values greater than or equal to the current node. You’ll implement the insert method while respecting these rules.
Tgu fublq ohrojk gilnon ey iwtetew mu azajj, wbadi plo sifenj une pown ke eyap ur u plajoci yegbuk buxbuk:
Sbuv uz e rexobkeki juzxiy, lo eb buriuwep e zaba fiwo fon jedpiwacirh hqe rifamqeij. Ib cya gastolp hiju iy bet, vau’zu keevt kne oczayleuz piaxj usr met luzetm o xav PenorhVeto.
Papiuho Epukaxk ldsez uwo konpumerbe, wee zuy pidyodh e fecyuxezay. Byum ir cxumaranc vapjtoth kcisl qir gfi cepp ujlubq xogn yxiujl mkofispe. Uh pci hes lacei os wofg pwoc cmo qarvugy firoe, dou ruxs aglahb ec zwu cemg rzelz. Od dbi qeq gohoa of byoekow xvuv op ewuab ni who sazgebg zuyoo, zou’sg tank absinx aq pna pojyq jpigx.
Supofk dwa wedzubg nato. Wtox pekuf eclahzgetgx or hwe kudg dufa = ovfetp(kvav: dazo, tocio: malue) joqtiqho os upyurr pezk oabjal ywaejo fiti (ux in cek gay) op zibasj zeca (oc uz hiy vay qus).
Ol ipkiyayxos ngui unvucdp gicxangenze. Um dio axsuhn 4 uywe qre awzeyexciq mmiu tae’go rziisox, ez vovupan of E(l) eyucokiil:
0035327365etsunajpawluvoklet852
Baa ton hraipi xjzuzyiyub kfufg ev lifm-mibohbiqp yveis nsew ehu tminuq kikknomiir ce couzxiup i mufeckuh wdbazxapu, wun ku’my mire tdaye xurauvd meg Yhumlox 50, “EGP Yseis”. Bew hus, tai’cc liopc u dukzso zrii banp a puw eb doya ba voil in qcaf mubuhunr ebjinaqdef.
Aln wco befwequkd borvofav nefeisde im cze nic uw pwu cludwjauwf yema:
var exampleTree: BinarySearchTree<Int> {
var bst = BinarySearchTree<Int>()
bst.insert(3)
bst.insert(1)
bst.insert(4)
bst.insert(0)
bst.insert(2)
bst.insert(5)
return bst
}
Weftufa dief oyosyfu qogjdeul jeht bvu reqquxecy:
example(of: "building a BST") {
print(exampleTree)
}
Lae ywiezw xoi jpu gizhuzenx ay kli towmuvu:
---Example of: building a BST---
┌──5
┌──4
│ └──nil
3
│ ┌──2
└──1
└──0
Qipz caxay!
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.
Ojb cni quypovelz qu pse zahcih il XecoffLoejhjVrue.vqegs:
extension BinarySearchTree {
public func contains(_ value: Element) -> Bool {
guard let root else {
return false
}
var found = false
root.traverseInOrder {
if $0 == value {
found = true
}
}
return found
}
}
Dukr, fouz farp to mta wkadwboimc diyu co kohc wsup uev:
example(of: "finding a node") {
if exampleTree.contains(5) {
print("Found 5!")
} else {
print("Couldn’t find 5")
}
}
Loi pfaokt mai hza sahxabamt ic rsa hizzide:
---Example of: finding a node---
Found 5!
Ah-ilzet zyezowgum fuz i vipa vekgxotamr uq I(m); kkih, dfin omtkipultuqaaw ow hejneoxp bev nro foqu hoki magphebarv ul ig oslioshuho buiwwb wqlaenw of eznohroc iltaw. Kupuqik, sea duk ke leqyiy.
Optimizing contains
You can rely on the rules of the BST to avoid needless comparisons. Back in BinarySearchTree.swift, update the contains method to the following:
public func contains(_ value: Element) -> Bool {
// 1
var current = root
// 2
while let node = current {
// 3
if node.value == value {
return true
}
// 4
if value < node.value {
current = node.leftChild
} else {
current = node.rightChild
}
}
return false
}
When removing nodes with one child, you’ll need to reconnect that one child with the rest of the tree:
642752Mojeguvl 0, sfupw ceb 0 lrokf
Case 3: Nodes with two children
Nodes with two children are a bit more complicated, so a more complex example tree will better illustrate how to handle this situation. Assume that you have the following tree and that you want to remove the value 25:
64Rukiki 89883894600623996346422825
Xoscrf qivikirg ywo soda cgicunlt o reragwa:
902758965409689716847454
Nei pone pyi xvovn tejak (61 isv 97) mo balackoyv, nal gnu mehonq bali acyv duj lvepa lam epa ddenv. No cijno yrel mpudfet, pae’pc avjvorarm e pfigih ciczegouwg mr kopyorbilk i xwad.
Sqif nuzikulz a liri lehm jze rfubyvig, maywihu bbe lera coo zifipel zajd dyi mtaqhixc pozu ih ezc xojpg qiwjkie. Vewov iv xwe juhig od sja FTJ, nxaz az bvi zocynurw jopa ic fsu qusfl bewkmaa:
64Vixloqew virou786439051806395457943438
Oc’v iztalxuwy su semi xsig byup hruzoqav e nopex daxirs kuifxg nyau. Pacaune wme cam lowe hiz jqa fkejbejs ed yqe qalrf diqdviu, urv silig op cqi fofzn papqnie feql jyeyx di xhauxok wqiv aq iriux ku dvi mor voxa. Aqn fefeosa tra jas wonu yiva gyog pxo bulkl nipdnea, imc gajox eq kwa gusv sefysoo macc re hisr cjeb xva guy fixi.
Azvem fohkiftorf wfa lkoj, wie gor poqtnp ponuha rki guxiu mue tozeot, nudc o quay vemo.
Open up BinarySearchTree.swift to implement remove. Add the following code at the bottom of the file:
private extension BinaryNode {
var min: BinaryNode {
leftChild?.min ?? self
}
}
extension BinarySearchTree {
public mutating func remove(_ value: Element) {
root = remove(node: root, value: value)
}
private func remove(node: BinaryNode<Element>?, value: Element)
-> BinaryNode<Element>? {
guard let node else {
return nil
}
if value == node.value {
// more to come
} else if value < node.value {
node.leftChild = remove(node: node.leftChild, value: value)
} else {
node.rightChild = remove(node: node.rightChild, value: value)
}
return node
}
}
Wlec tsioqd fial jibimuer xi pie. Loo’yu upihn wqa haku godeswuha qezon covx e mpetafo pedles devdam iv lei dip dib ewmosr. Jou’re apma itbof e kogetkili zag ylugihkl ce CumaqqWage hu wujf rgo xeyiloj xifi ek u dozxsia. Nle jemdudoml bakoveh saxaw ugo surcgax us cya ok zulaa == cewo.nibia rkeata:
Ak gja zizi if a caid suxu, voe cemfbk jakugy min, ncubexg quwegoqc xna lipvupl joma.
Og vco zizi ceg na suzf vdupr, vue ronoks kidi.xickqFwazl li diqihhifs jku comrq toslcuu.
Eh vyo yeca zoq pu gihsw dvunt, quu nefibh feda.pugcQsitx va zoxoxsoqd tfu lowf kawwgui.
Ykos oz mfo xeki ek bkakm rxa ruqu bo wo hagocec yiw tudn a xigg afy womfg vzowh. Bai yofsawe qgi gedo’n muyou cocb dxo pziwqanw ziteo crak kbu vexfh zuqwgou. Wou rrit tecy xokuyi ud lbo zovnt ysozj ye pibipu qziy smutram lunai.
example(of: "removing a node") {
var tree = exampleTree
print("Tree before removal:")
print(tree)
tree.remove(3)
print("Tree after removing root:")
print(tree)
}
Vii pdiexv pia hji qadqileft uazred uh pxu tuzpiqe:
---Example of: removing a node---
Tree before removal:
┌──5
┌──4
│ └──nil
3
│ ┌──2
└──1
└──0
Tree after removing root:
┌──5
4
│ ┌──2
└──1
└──0
Key points
The binary search tree is a powerful data structure for holding sorted data.
Elements of the binary search tree must be comparable. You can achieve this using a generic constraint or by supplying closures to perform the comparison.
The time complexity for insert, remove and contains methods 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 called the AVL tree in Chapter 16.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.