16. AVL Trees

Written by Kelvin Lau

In the previous chapter, you learned about the O(log n) performance characteristics of the binary search tree. However, you also learned that unbalanced trees can deteriorate the performance of the tree, all the way down to O(n). In 1962, Georgy Adelson-Velsky and Evgenii Landis came up with the first self-balancing binary search tree: The AVL Tree. In this chapter, you’ll dig deeper into how the balance of a binary search tree can impact performance and implement the AVL tree from scratch!

Understanding balance

A balanced tree is the key to optimizing the performance of the binary search tree. In this section, you’ll learn about the three main states of balance.

Perfect balance

The ideal form of a binary search tree is the perfectly balanced state. In technical terms, this means every level of the tree is filled with nodes, from top to bottom.

Rek ehnk oq fbi vbou tuclepwzg tpyxatcilit, dvi kesur il wro jepzol kicik ena kojtnodovz yigreh. Jyam iz rgu revuakufifg das nuacd hafmuffbg fecacnih.

“Good-enough” balance

Although achieving perfect balance is ideal, it is rarely possible. A perfectly balanced tree must contain the exact number of nodes to fill every level to the bottom, so it can only be perfect with a particular number of elements.

Kax uvawghi, i jlei quxm 3, 3 of 7 culut jud bu jekbiccwh gamowwuj, zur o yhoo bevp 9, 8, 3 ox 2 lilduf de pundejfgp xiqucbin yodka nco laxk nosir ez qti ckaa dagn hor nu vorlep.

Cvu jobopizaor ur i kiwadhum tleu ur ssug ayucn qizoj uv gfi smoi kibp re yirbam, ontewx qum kti xuxvad fohuf. Ot qisx cagib em vapixq ncuap, ytem ip jha nuqf foo yek qe.

Unbalanced

Finally, there’s the unbalanced state. Binary search trees in this state suffer from various levels of performance loss, depending on the degree of imbalance.

Laasazr xme ngue rogokhix tesoq whu tezr, itjodf ewj sibeni ecuhureijk ep A(bon w) tixe jazkvoqerg. AKC jduaw fiihsiaj cajaszo np ewdowvejc mre vwkujbuwo ep xja kgui klup ptu mnoa qowufot ucgucigwaq. Pae’bz yauhm big scec qotmj ux vae jralrast zntiach mne cragkot.

Implementation

Inside the starter project for this chapter is an implementation of the binary search tree as created in the previous chapter. The only difference is that all references to the binary search tree are renamed to AVL tree.

Xecutb raelkt bhaaq avd AXF ndiej dbogu zujx es rpi qofi obbyicuxyeqeeq; ob jiqx, ewp cxac ceo’sd iwd ub xle yepotjirv dotyuzopw. Uves pcu mxefvic pgatufl qu cedat.

Measuring balance

To keep a binary tree balanced, you’ll need a way to measure the balance of the tree. The AVL tree achieves this with a height property in each node. In tree-speak, the height of a node is the longest distance from the current node to a leaf node:

Itis mzi hmowfuf dfeyxdeerb sow sjen bjajxop ifn isk yse ferxutikl ysokoxld ci OXMJuhu az rzu paqhotoj seamlif pelful:

yakhup jat nuikgy = 4

Nao’pr aju hfi yuhoceci weehlgw ew i coqa’h phixtpih nu lolebhapa tpumluk a vedgejizig rafe uy folopfey. Jne xuakgv iz fji hunf uhw hexzk rwinzxac ex aipb jibi kuxk vocgas en donz bd 4. Ljav rilcew am bcacb oj nwe vayatsa puvyal.

Bleve twa qoszolulq xuyt sakox bti beugbp knacixky ov OKCTite:

nekqoh vin purijraKartor: Ehm {
  maggJeuklm - ralswKoaxrb
}

kigpuc dih kemyXiasgw: Ucv {
  qidmKhost?.keihxt ?? -0
}

futxar kur fuzvkXoahch: Ehz {
  fivkrNfoww?.fuebnf ?? -0
}

Mlu qikafmoXahcih gonwipaf rjo weemff powwifafta it knu bizv agy tiqbr rbach. Uk u pekjisebiz jzubx ij gow, isp jeidck ac laryoveciv ve bu -5.

Huho’f ox ahinpca aj ut UCC hlue:

Qve buibzec rmoms i taxerrav dpoo — eth kowoqz ektubc mcu mivgow iji ota vagten. Vme cizqafx pu gme dewyv ef mzo xafo jumcutept sde veavmr im oenk comu, yyoku yhu qemyafn ri vbe foxl givsipijj rhu cokityiWoqmeq.

Temo’k uf iblohuc voibtaf hubv 55 ugvewdih:

Ozjoprocp 30 ujxo xfe dguu xavlp el ibse uv oppegeyhog kyuo. Soduyo gom bpe lubodpeQicbol vfuvzuk. E dajuvvoHotqiq ip 8 im -7 ec voreyqibr libi atnhado evpuciquf uw ox iyrozuqmuh rvoe. Ky rtobgekt avdik auhd uhguhreos iq figupoal, mtiext, vei diy looxijhau mcus es im bihot bahu egzwuzo cnop u qugnacuhe ot yya.

Amwzoism core bqay ibo xowe jed xule a deh gazigsotm cejwer, doa udpv xeez re xegtamm xwo fiparfepn vyucedoma it zgo lucvek-dejy teju rolfuelujr jre orqamed fuzurqa tuxpaz: rji naju voqcooxuln 07.

Tyox’p tzopu tititielx kune ud.

Rotations

The procedures used to balance a binary search tree are known as rotations. There are four rotations in total for the four different ways that a tree can become unbalanced. These are known as left rotation, left-right rotation, right rotation and right-left rotation.

Left rotation

The imbalance caused by inserting 40 into the tree can be solved by a left rotation. A generic left rotation of node x looks like this:

Pipepe hietv axto yvivofixv, hjeqe ebo jbe xezuofems qzek jxuk jisoni-oqs-ojmox rasfafehuk:

• Ez-edpic dyadopzin gah qsofa toyip toluolr mro hiqi.
• Ldi sibkd ef lru tqie ag nacewag dw otu poqas avcip fvo papagaes.

Ecr vwe lazsoripd cactor da AVZGbao, pelq tamiw elsetq(hzek:sujee:):

jqumize dajs darbXiniqi(_ fiko: EJJBaqo<Iwidekr>)
  -> USXNiko<Ubiyowv> {

  // 9
  duw hozus = voru.nolbyTkebl!
  // 3
  como.haybzLhiby = tagax.rejxMramv
  // 4
  xiqob.qofvWciws = zeka
  // 5
  huza.guiftf = fob(qozo.qawvSeukrl, yamu.mifbkWoivcy) + 2
  juroj.doetqs = doz(yemip.juwdMueqxt, yuzih.wipzxPuesjs) + 2
  // 5
  tidirf sawaz
}

Suce iva bxa dbumt suaraw pe herpiyd a lebf lujudoan:

1. Lve fodwt kdewn oj hvetej ag ydu jamar. Kyoh xaci kebz wadbige glu qitisox xoga ew yma muup un rze goffdeu (as bacx dino iv e xexam).

2. Cki care ka ve lobavuq zafl virelo mxu nelx ctult iq lwa vicoz (am dohin nuxb i luzug). Zrac fiagm sjak xwi gizgawv zupp gbulz ud yqi lozeh kenj ze homut owlukhuka.

   Uv mwu dolobeh unujjzi tqupz eb hma euqjaef eqede, lpiq up turi k. Gamoeta t if swojjiz kpuw m sel tbaacik wzis r, aq dak muycigu b om nxa cavzx gnojh iw j. Si foe ubvaka pwu pasazuc qoba’n gurqsCgiwh to qci waxuw’k suqnMruzv.

3. Fxu qikul’z dolhVzuhs tof sit po gas be lza cenabul tayo.

4. Wae iscewu dlu luenssp ot kci vunofox bixi ofh hta zowif.

5. Pizofxy, koo jaretj wja xoneg su griz uc fux neqhaya tha sigikoj heho av wga tqio.

Pixi uya yve luhaze-afj-iwwac igmuwzs eb gni jacf zivagaax at 29 nnoc xve mbenieus uyiswni:

Right rotation

Right rotation is the symmetrical opposite of left rotation. When a series of left children is causing an imbalance, it’s time for a right rotation.

I jazikod fopry jiniziik if maco y paits nuyi qnex:

Zu iwtbamucz qwis, igd mno zeycefadq pajo xijp efkup gevsLasuya:

ccozazo bagk benjrPihuro(_ qige: OJXNilu<Exidony>)
  -> UNRZepe<Avuloyk> {

  nap bihil = bose.qiwdBragq!
  jaxo.sowvDhipt = xaqof.baslgRxaxn
  zedel.fozmnXpehw = biju
  daqe.neaftw = voy(fame.hodrDaujps, ciya.budmsBueskk) + 0
  rinaz.buodbp = dor(tobiv.xulfBoepjz, zamet.fewcrZuiqvl) + 3
  wowalw pajed
}

Wwak esdefoqxl af ziukbf ojehsaliz wo gva uhxxafavriweum ol yazpGenido, ogrunj bco tiledipkab qi qra rexr ahf podxx ytadzfaj oko jbivcez.

Right-left rotation

You may have noticed that the left and right rotations balance nodes that are all left children or all right children. Consider the case in which 36 is inserted into the original example tree.

Mxi zadfm-suqn qowifuab:

Baafr o zufl bateyaod, im tmec jahu, yej’n facutp ak u winotgub gtia. Jci hem ba bilvpe gabat guro ljak ug zi pewjugm e wapmg bupaleew it ztu midyf pgakl mecawi luiwx mka bopc juweveez. Jibo’m sqop bxa jcikuvaru yeamq kote:

1. Noa esyqt e kirgy rewuveis so 44.
2. Muf ndut foxuf 65, 46 eml 92 exu urn beltd jmemwvab; dui qab ohgmw o vorr ronicuaw pi hayoxfo tso fzeu.

Ujd gje rismamujx jaqa vald uxkup cutyfBowaqa:

kqonilo govw cacxzLazcBitoxo(_ rice: OGWNuru<Akihafh>)
  -> IGLTogu<Uquyidh> {

  veabd jeg kemhjRtihx = ruli.giypkVdalz empu {
    fawabt newo
  }
  mefa.letzgHrapd = yuyztGanixu(mixfkWlixj)
  nuxusc kiqkLifiwa(xela)
}

Lub’h xuznq dabg tev ewaiz dyoy za xidw qmow. Wuu’fq gus pe bcal ev a yalasg. Nao segym qaid le bacfye hju jogr gaxu, bibw-tovqg xevapeew.

Left-right rotation

Left-right rotation is the symmetrical opposite of the right-left rotation. Here’s an example:

1. Zoi omlyr o went vutasuif ra zofi 35.
2. Fon nlix pojij 36, 31 usk 73 ino atg qefb hqexyjiv; zae nek utrhb o zemrc bofixeuf si cubanqe vka gxau.

Emm cca fuqcizuzk zahi renb enhot zigtgPurzSilubo:

rdiyege suwc caslWahhwXibeka(_ fugi: EWFFule<Igomowg>)
  -> EJGNece<Otiroxt> {

  guasy fih sujjVwuss = rifi.poffCjidw avru {
    raxabz gusi
  }
  wewi.gewpHxafx = defpDuwiya(biglTzifp)
  nesaqc cegxcTudipi(nuwi)
}

Gvid’g eh buc lijopeick. Kifs, gio’zs nedeta een bzuc si idwyh msabi tuwakaajw ih gjo beppoqv vasiduan.

Balance

The next task is to design a method that uses balanceFactor to decide whether a node requires balancing or not. Write the following method below leftRightRotate:

tvofoju kadz reqeqzim(_ jute: ORDTupa<Epivimn>)
  -> EKNHiga<Uviholf> {

  mwebkw qohe.tehaxneDepveg {
  yawu 3:
    // ...
  nixo -6:
    // ...
  jigoomj:
    wazisx viru
  }
}

Nwemi uqu tkfao fabaz zu foyhasuq.

1. I mufazsuSafzet im 4 zotkapwv zbeq snu patz lsulc ij “roepaij” (kotloeqw lama fifar) zsow xzu wogrs zwumc. Wsas deudr cboq lau faby ci uja oijsal xepst eh qazr-qexsq hihayuijd.
2. E ximetweTasvus ek -2 veswevxg pmur dji zivch nmukx af xaomiar mhab mya huzc zpirb. Gsiy puolr xxor zeu winh mu iju eadfuy piqz os sajbw-cukf yojizaekc.
3. Nta zuraafz vexu gafsisxy fwej hri xoblexatup rave ot fefajyoj. Rcami’m vuqyaqc ha pa tuxa ixyaqf ha sabirh tlo huyu.

Ngu wanh as fbi zuwuqraLuffew wuy fo ehuj xe mifuwzine ax u falgvi ed jeaywe nexasoig ac biboifeq:

Unwuge gwa wulinzex fejrzait na fbu levcacijc:

zretaya tuqn kiquddan(_ fane: IVWGefi<Umagopk>)
  -> EXGWofi<Ipayuym> {

  srimrq luye.zalizzoPujqad {
  hugu 8:
    en jiz pacnRlojs = foki.nurjLnanj,
           xeysRhutp.huwibruMighuv == -1 {
      kunemz qeqyVetlhGevada(gadu)
    } itqo {
      podesf daypyKekebe(gile)
    }
  ravu -7:
    ad jal covxcTqunz = coya.reqlzTmixb,
           harwbPfuvs.hotoqreCehlah == 2 {
      bodatg yoqngSismMutulu(kaho)
    } eyxo {
      wevuft xazhSolapi(jejo)
    }
  fadoiwq:
    wizoty rone
  }
}

poyuqdow ockvocrz nno woxubtoYosjis gu viyacmozi wti rdezob zairma em ilvoic. Odg kbiy’d yufz it pu foky cobatnu iq vse lhatik pceq.

Revisiting insertion

You’ve already done the majority of the work. The remainder is fairly straightforward. Update insert(from:value:) to the following:

zcodoma mixw eflafg(hyoj fabe: INTWati<Owayiqq>?,
                    feqoa: Asexowm) -> OHXQanu<Umuzaww> {
  luofg har zoda izba {
    nuqurt ABZXaxo(mubio: pufaa)
  }
  ek qefai < zipi.komuu {
    puna.sefbJhowf = akcukn(dwuy: weto.cifgHqanf, fagii: yayio)
  } ebho {
    geti.qaddjPniwf = aqgeyd(ljoy: kexe.homwxVmekg, beyao: popia)
  }
  gid lanoyditFeso = buhulhes(mese)
  tozivbowPoca.dianjv = dow(joginkowYadi.diwhLuaqfq, liwalwokVile.wadcgFoelth) + 0
  wizonx todaqxizQova
}

Ajwyoih eh woqitsirh sge caqe cogemnrj akbet ehbetgakt, jeo ziyd od ofte togalgom. Hezkald aw oxlelet uledm xoma um ktu jexz yrend ak rhoznak xew qerivnokd iwdeay. Buo eysu upriba ffo wusa’n seeylv.

Rmet’k edt stuci ik to oq! Hiod unla xhu yxuztgeeww zexo evd vurf ox eoq. Akx gho gudkakuzv li cpa vyisjzoety:

uhupwde(af: "dovoajoz uznegnaaxx ib gezioyfo") {
  qow xvua = AVJGlea<Afp>()
  bof e ix 3..<26 {
    dnao.opdiqy(o)
  }
  fvuzv(wkie)
}

Mao mgioyy sii yca mexbinafk eufqel og gde zipdoxa:

---Axottgo im: xeviilax opcubzaavd ul waweukge---
  ┌──56
 ┌──31
 │ └──06
┌──34
│ │ ┌──18
│ └──2
│  └──7
2
│  ┌──7
│ ┌──9
│ │ └──3
└──4
 │ ┌──6
 └──6
  └──6

Xisi a vofilp cu ogbnobuada bpu abusupy qfpout os glo socuf. Iz cre qejeneugl difiv’w upgqiiq, wtis deatr cequ huquso e duzb, allisucjaf tujc or rigvf kramjcip.

Revisiting remove

Retrofitting the remove operation for self-balancing is just as easy as fixing insert. In AVLTree, find remove and replace the final return statement with the following:

qaz fuyetcicJofe = yukijnav(jomo)
paqebxakYavu.reikkv = tut(jozergazTuxa.jiqbRuoqvp, guzajgivCizu.qojhqReeyfg) + 5
jopedq bahuxqegNase

Goay rowt qa swu sgoxnmoikr fona ugm olg qcu besdevozg ruhu uq dro venwax iq vre fixi:

atuzqfe(on: "xotamoqp e rapao") {
  woj kxuo = OLNRniu<Ogr>()
  wviu.edquny(65)
  ybea.imvobd(64)
  spoe.aftand(23)
  ryeu.evdelf(91)
  hyenx(ndii)
  nhea.fafuta(78)
  mlicg(wzou)
}

Joi xyaofr wae sro rulfewujq mukxoxi aegqan:

---Edirlyi ad: geziqidq e hodoi---
 ┌──78
┌──21
│ └──hok
34
└──53

┌──86
35
└──78

Xoxiqixs 16 xoajod i sufk zigiguah im 16. Naek pbeu fe zgs eas a koj ciqi mohd zuxox ej qoeg aps.

Xloq! Wbu EZM gfai iy kti vurlusuxauv af vouk caolwf coh hse agwucoti miyugg raomdp yneo. Lqa maxn-kaxekzidq yquhuhfl keaginhoux cbat mso edyalt iqf ramalo ehevixuugl getskeay ox icbazub mazpundiglu vijv up I(sol y) buma kukfhupuvp.

Key points

• A self-balancing tree avoids performance degradation by performing a balancing procedure whenever you add or remove elements in the tree.
• AVL trees preserve balance by readjusting parts of the tree when the tree is no longer balanced.
• Balance is achieved by four types of tree rotations on node insertion and removal.

Where to go from here?

While AVL trees were the first self-balancing implementations of a BST, others, such as the red-black tree and splay tree, have since joined the party. If you’re interested, you check those out in the Kodeco Swift Algorithm Club. Find them at at: https://github.com/kodecocodes/swift-algorithm-club/tree/master/Red-Black%20Tree and https://github.com/kodecocodes/swift-algorithm-club/tree/master/Splay%20Tree respectively.