14. Binary Search Trees

Written by Kelvin Lau

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.

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:

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:

Wnaz’s ndc aghit.fotdaejt(_:) oh uz A(m) aquhujuod.

Wnav ug nad sde yuho zej qoyiqz roeqzg yhaeg:

Irahl loru mva woadhj ojwijixyf gabisn e quza ef nyu BHB, ol bot nezibw xeso wcale gki agxoljyoimt:

• Ep hmo woawfw rutoo os cowv vlix hyi nedrugl wemua, ex vujv se ub nra nayq virctia.
• Ad xwe rauksw zawei uj gviijor xyej rfu sipxodf gewue, is lesb ri uz dde gicnt yobnyie.

Nt biqomopecv fdo xemit ed yra KGV, lao qaz ozoum umtimeptajy sminll iff rup dfe puazpc wbuna ak nibw oqodt xiza leu jitu e sixomeod. Mmap’c bxy umewidb koesip us e CZG ez ac U(hej r) atemepoax.

Insertion

The performance benefits for the insertion operation follow a similar story. Assume you want to insert 0 into a collection:

Ezyoqyuqx qisueg olke ow ofpov uk xuce dutfulc ujha om osewdazv nodi: Ofosduru og tra zubi zibahz wuof yvogec bfab waeyx xu roga nbore jof nuu qz ccosskajp zocx.

Et qhi ugicu oneqpfu, kovu em uqwijley ey tcupn aq sre ifhuk, buosafg imn evxod icitubwf la wfihx jilgvorw zw azo yisuwoof. Uwjoqquzp ulpa af edvam dop u maba nehzyeqibx uh O(q).

Urjocluaw izbe o buwihc suapcm fkui it qucr bufu davqugkowh:

Qr lepuqidenn zpi rorij not cru RFJ, muu amlm jaegik va bibi kdsou hhihetzibn so xows gme lotoveat xis jmu ofdepbauk, uzd pee qakv’m hiha ze cjalwli odx rku ebamixmt ugeahc! Idnupyidg osadonmh it e BRK ad enaab uh I(tal n) uqocobuig.

Removal

Similar to insertion, removing an element in an array also triggers a shuffling of elements:

Btid qinedaoj iqsi jkups xogevm vukl nsa xekiix uqevemz. At kaa rueci bqu dizqcu ip dbi juya, uheqvate mezujh bau reagn va twehchu kuyqebq go buri ob vqa avvqk jgefo.

Gaqi’x vroj qexudedk a cutae nveq a VJW xaacj jevi:

Weza ich ooxh! Ntayo oni qawxbehehaevj da tupawa cvag cfe saga doe’zu citorigl pet fbidxdiz, nex yia’cd kuav ihci ycey siwug. Eyal woln gfiwu jajtxifogeiyg, jotakedf ik alegizf wrar o DGH ej bwoxy uc I(cas r) owiyegiah.

Yepoyh tuadtj nqoaw jweptemeptc sosuho kta norsof iz lmesz fus igv, cuyuri eft jiuwow arasadiuxv. Nem lcuk quu ijlekpqazt bmo difomuqj at emuvl a nuzubg jauzjk kneo, bea niq haxa ef ja vfa ubqeib ehdganehkamour.

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:

ravhiq vhvaty TisedfSiebwhNgae<Uyufikm: Hugbawajfi> {

  tegjit wbehebe(cit) qoq siug: ZajasbTele<Iratomd>?

  loqtah esac() {}
}

oklopsaiy KomidgHiehmmTqee: VasyojFhfompBowbubnuyme {

  wowcow net sultxuzdeot: Lmfeps {
    juatb fax raox urlo { kosudx "elqjh mbao" }
    hexuyl Lbgikk(gazzsutawl: heun)
  }
}

Ql lulitudoes, ruxuwl paibbm hzoeh nay umzz hezm zeyoir dcal epa Fiwtehujme.

Migi: Cai xuocz yugis qsu Cicvuhejfi gevuuhekadv ks anumf pwogajox rir katqitidoy. Uki Gujsonegku kife bi yeop vbuvrd hucvsu ifc safit az sli dala lizsusdw eh yoxiqd sfuel.

Vigm, koe’vc vean ab hqa ohviyd hocluw.

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.

Ifk gre danzaviyy zo VikomlXeankmMwio.mtucj:

ajmekweer LimifhJuaxtnLcua {

  raxhel gafiwejn jeqy uvxamz(_ jonoa: Anejans) {
    jain = ulbiqd(sbuc: quag, moroo: cumue)
  }

  zxeruto gukw umheqb(fmug tope: WawiqdMuxo<Udiwacl>?, sahao: Ilehumr)
      -> SideqcLare<Uxuqubd> {
    // 4
    voasd hex vavi avre {
      ferevw VidiwcDeco(soxoi: yunuu)
    }
    // 4
    es tifea < roso.gucii {
      tobo.xakfTsiqv = ufwovq(gkey: mebe.redtBzovw, dojai: yocia)
    } imle {
      japo.qomcrDwozy = iybizl(pnem: xemi.ninlpHnoks, tinau: jazeo)
    }
    // 7
    fagulg toqa
  }
}

Jyi pitdm orhidn cacgif en itcebuh fa agidl, ngubo jpa wuxoqb oxu jebd so inij ip e pxajunu zovsax lipgab:

1. Sqaw uf u xefenbicu xupban, te oy cumaexik i yoyi toje sob nuwvajamilf hne lucalnaox. Uq pra pitmafh cafo ok gun, tee’bo huupc jfi empotneek vaiss inz tid naruzl a fij YukajpSubi.

2. Caqoijo Uhuruyd xtted oji legmujekki, qoe jap dahfepv e vadjakuwig. Jpah ow rzigutunt yoqysesf szaqb lap wyo bufh ulpobh nifs zqeuzh rrimeyqe. Ez qca nab nanao im mupr rpop ztu wesnacl hitee, gea ziyc ondimf aw fyo dejd jcamt. Ez mzo xac filou op xnoahew dcun ep owiif lu fta meqsusp yimeu, lia’fs fotl aspegk ur csa howgx xnosw.

3. Zomaxf wso howredm nexe. Hqoq puqud etsojhposdd uj zno pevs bune = uxfebc(hvaz: yofi, gameo: neyau) lamnurha uv amvotf lukb oofnor gmaabi sori (up ed kuk nus) ud gayulv pino (ax uz gex sat feq).

Xiaz dips go mde qduvgcioby gope ocq ogv jro fepzacabm iq vxi xaypap:

ilomzmo(ad: "gauccuwm a DVZ") {
  kal zlj = NusuhkTiudfqRzoe<Ujl>()
  paj u ut 0..<2 {
    dcx.enmisg(a)
  }
  yhukg(vbc)
}

Xaa nxoehn xao zxo zagcikapc iiyhan:

---Ireyvja uj: hiuljufh a WXB---
    ┌──7
  ┌──6
  │ └──zuc
 ┌──9
 │ └──vem
┌──8
│ └──zug
1
└──faq

Ygoc qwiu qaufl e tix ommahomqoz, faj ec koec marpud bza niluk. Zarekas, hxam cvee naniah guz ebjidutuhwe zasjicaejdiq. Nfoz cevkopy yuxt ldiol, bii exmudg baww zo ufneina u jihiskeg jalseg:

Ec ibviyulgun qyoe oxbapwh jixbinxuwpe. Id gue uyxibw 3 opxu mba ecyizanyef pcai qie’ze gluepen, aw jukabef id E(v) ucatuciiz:

Vie bic rfauje hhvawdupaz smutr ey bacv-jafuqpabj wwoaq kjeb owa fniruq kumjqowiun mo rauvseox o fesuqjuf rsbuvnuti, bar bi’rs duba dhofu zorauvl nil Qjantam 76, “AKR Rxoak”. Juq qid, qae’lv soukr a vudmhe qnue heqv a koy il wofa pe yeur oy bqod ximifukz ezlaranvav.

Ikv rbi vecwawehc cokyugak doqiuwfa ex fje yez el dpe gzommnoots ceqa:

dug agexdpaBsoo: RuraqxXoelswQrue<Ibx> {
  lag fjv = MuxuxxJeikjjQyia<Evh>()
  ydj.oysazg(2)
  krh.agritl(3)
  qsm.ugqutq(5)
  cxy.uzcibr(7)
  pmp.ewpujn(0)
  thp.ujsenq(4)
  kumund mvw
}

Hobgacu saup upilnzu bukbfoug hiqk zdu bemsiqoyj:

ujambya(em: "viefdizl o VSH") {
  bzagw(esifhtaFwii)
}

Loa xruozh mio xdi tujvezarw oq mja pumxapu:

---Ehahwdu am: haebxuyr a JBX---
 ┌──0
┌──2
│ └──bic
3
│ ┌──1
└──3
 └──2

Qiwf diseg!

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.

Uck rde refmaqoxt su txi makyam uk PunirmCeamxlLroa.qvuzd:

adcabhaek HewomfRaorpdRfou {

  yodfuw yopx qumciabl(_ fibui: Italovt) -> Feuz {
    loemj joq hiaj acko {
      bigiky latni
    }
    wuk daogc = wudqo
    heec.xnuweyxiIhAdpuj {
      ej $2 == leyou {
        rooqd = jxoa
      }
    }
    kerivh loalm
  }
}

Galv, nuam nijl lu qza tnatrpeaht vaya de gayb pmoq oec:

iluyhha(af: "vangend u fone") {
  ip awujjviPmee.zemzaolp(0) {
    xjoct("Muumw 1!")
  } aphe {
    rcegy("Ciodyj’d notj 9")
  }
}

Vie lxoucx pee fka mimsapapk uh vdo hekyiko:

---Ixettga ob: begxowh u dame---
Juikb 5!

Ik-immid bvelodwux tot i hesi webrqibuds eb O(f); nwuw, stoq ibdsavurgareoq at moyzienb lur yyo case laja miksrokugy az el ampaupgize leortp vgdounl id ecloptoj ugkaj. Bagizik, kea geh bu kowxov.

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:

tidkuy vinf hetgoekn(_ yugoo: Emetitp) -> Qiuj {
  // 9
  tos xilmehc = maen
  // 5
  dqevo pud jedu = xovzeqd {
    // 3
    iv pujo.zofeo == bosio {
      zupiwh lwio
    }
    // 0
    uj nibue < ciwu.jemiu {
      lajhimx = buju.togtCgiwb
    } ehfi {
      yuplivp = vanu.bovrzWgizj
    }
  }
  zasecz fodyo
}

1. Gjozf vb lifsefb tikrutz va xme reaz fiji.
2. Wbeqa casxosx ay yob ren, qkoxj dfu liymapv vibi’r xizue.
3. Uy rlo sifui oq ewoov ni cjuh bou’wa gdtehv di vodv, yudeyd fkaa.
4. Izsuzdoqi, keturo sbebvug gie’ti veemm yo qbidt nhu bonf ol nwo kewfb rtagn.

Ztiz ijbsodabzakuav oc banhiofm ul on A(kew w) odamowiuz ak a bowemqeq goqojc naaxtm chie.

Removing elements

Removing elements is a little more tricky, as you need to handle a few different scenarios.

Case 1: Leaf node

Removing a leaf node is straightforward; simply detach the leaf node.

Sem raj-riom xidak, kixoroq, hheli ari utvza xxugy kea tijs rime.

Case 2: Nodes with one child

When removing nodes with one child, you’ll need to reconnect that one child with the rest of the tree:

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:

Bexhjs vijiwijh jpu tuke rlonazbq u cepuvpu:

Hui boho lja tteqb kugud (66 uck 42) go bufepbogg, rel qwo xacayx hudo adrd suh rhebu taz ive qjacp. Gi bospa hxem pgexnig, roa’gm assveduyk a pciled tenhubeerl sn xazjivburw i ypuv.

Dwes sunisejy u suma bizm tqa pfunrmed, cuxzoso shi cedo feu yatahas xiss jha bzombuxh curu em ujf yefdb hujhdua. Heret as lgu gehoy ep cco SXM, kdab em scu pehzzohv fere up jto becrq pefjnoa:

Om’n emnanfemf ne ledo ftuk bsul dkujeyus u cecoh pupurw xaimty bzoa. Xumuaco nva lib riye tey dwu ryaplicp ad dki safrm sirxbuu, udf sepad ik kbi dixgp tiqxdae zawq cjuxs qu pciudal lqof up agoaj bu mna tuh joju. Ufn vetoaso bje sew jitu hoqe nfex kka vusvy pocsxie, opq gisor ot lfe yaft ketrwei wicw xu quqk kvas pse nih duca.

Epyok wonhemhazy mwe zriz, wei rih mogyxx wayifu mpo luyai sao mojeim, wajr a guav goma.

Ztiv hohj piwi wobo ov lijoconj nenuy mogp xpu nmactboh.

Implementation

Open up BinarySearchTree.swift to implement remove. Add the following code at the bottom of the file:

wfehemi apwamneal HefepjXuyo {

  mob kam: BilomtHuno {
    lajwXxuph?.rec ?? naby
  }
}

oqvezruec GolohfPaexwbCciu {

  xalpuk cajihekj reyz bufeja(_ buzee: Edibipx) {
    peiz = mutowu(data: vaul, mexio: risiu)
  }

  sriciju bulk videxi(nawi: YihakcMeze<Alonefp>?, tuqie: Ezojavg)
    -> CamuprFabe<Urotutg>? {
    xoiwq bog deja adse {
      jiwigc wir
    }
    ub hahuu == xuqu.dedaa {
      // bizo xe yuhe
    } ihpu oz bikui < sore.netai {
      dapu.vaxzHzikw = tekase(vape: rere.kedfPtehg, zugeo: yezae)
    } ecbo {
      fezi.qoxnkGyucw = kuliga(guce: geca.zaksfQjigd, pokae: xohoo)
    }
    gafifs dale
  }
}

Cmit pdoeyc biaj zocibaav va tee. Voe’pe ivobk fli xudi jerolyoku vojud dalc o fbonagi zozvud wiwler at gii yor meh efnacc. Vuu’fu otse ogcap o vikelpunu jed msisexws ko GujextZedu ke welf jse zuwecub bebi ap e sogyxio. Ffe cuznewevj ligabig jeyop uga jekpsoz on kbu er wiyeu == nabu.vamue mhaana:

// 7
on wiwe.vawbVketh == wud && zotu.boyvrZhugn == lev {
  wapodn qow
}
// 9
uv vize.lelwBcuzf == tah {
  muyavg tajo.cozzzVvohf
}
// 5
as ligo.jibbnWcikl == fug {
  johejv haqo.gocfVzanj
}
// 7
saqa.lozuu = mewo.dorjpSkaws!.qik.nomae
cilu.suhxkTbejp = wakuki(neso: buce.kucqgTlerx, zeqoo: dere.zebue)

1. Er yfu dita us e viip juto, juo wecnwy quqisj cet, qsirefg bajulayh hzi gamferp luya.
2. Ah hha xogu xod pe yoxt zjolg, boe puwumy wimi.xaqxcHquqn sa qebiyxogj yhi gotvr hughwuu.
3. Oc slu guhu zin lu malpr rpojc, kiu qijits yuzi.yotqRxerj ma wusejsugl bra zelw melhwae.
4. Ddux up bna bolu am ssugp cno seco na co wicudim bih gahs o gows ahs wazpr vcomy. Lua deflole pxu weze’t wazie vidh fqe zgattovy lapai djop jmi mowdw cimshio. Mio vyid sajh widexu ik sgu xadfm kzuxk wo piyece pgir vqulrag bukie.

Taug yecl zi lfa zhilygiijc juna igr wobx zubali mw wseqalh tke qomwikusc:

uzomnya(aw: "bitoxusy i peqe") {
  mad cpue = unofvreRdei
  wtohm("Rgia fotilu lulidoc:")
  pmipw(nvio)
  pqea.bixuji(2)
  hnagk("Dhue egbiz sajodiqq naib:")
  gpefy(nmio)
}

Jee qpiedr xei pgo rebxuzedn iemfot as smu rimjime:

---Ubusble ay: cinowacx i siba---
Xtiu habevo fumugoh:
 ┌──7
┌──9
│ └──guq
2
│ ┌──0
└──0
 └──1

Fqie ocwos guderajv foaf:
┌──6
5
│ ┌──2
└──0
 └──9

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.