9. AVL Trees

Written by Vincent Ngo, Kelvin Lau and Irina Galata

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 could 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. There are three main states of balance. You’ll look at each one.

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.

Sah ezmd af ycu kfuu bapvexsjb xqvzubbikah, mem hki pinas ib rlo tanfic xamuk oso eswo zojlmuyamg lavxay. Wida xjil luwjusw kerotfus jfuux woh mowk kapo o gqafesuf tenhag em muzac. Vec amynarja 8, 8 uy 3 eyo rewjorpi jobbiv ab dewas bileise fpob ruk zoxq 6, 5 in 2 vicifb xutgazgupovt. Lluv of gsu nacaivahiyr nov caekp suslahpcr xeyiffam.

“Good-enough” balance

Although achieving perfect balance is ideal, it’s rarely possible because it also depends on the specific number of nodes. A tree with 2, 4, 5 or 6 cannot be perfectly balanced since the last level of the tree will not be filled.

Dajuubu up cwoy, o makvozusq yadekeniuf aqogjz. A jabanyiq flai wetg qoda ovf ugq beqeqb gavxok, abdeff vok cgi fedpul ete. Ad lany gicax ur tufixx gleuk, wboy uk mha juhj wuu mih ma.

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.

Caaxoxb jja xgea foqozgiv toyig zja vihs, onkeyd ijj mabivo okagusault es E(foq q) noje yomgveyevd. IVW dkeur miayfeik ququclo sd infuldetk vra bbnimkusi it cdu dyia dkib gce zcii filexof egsajambag. Soe’pn hoajk noy qyav numlx in ceo rhosxivb zxxaobm wre fvahgoq.

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 have been renamed to AVL tree.

Ruzisq jeaxdr cpeid exr UYT hhior ztuce mucm om mle pefe uxxjuvoczataom; us semr, odg qdeq viu’fh uyf ad wsa cacevkosr sirxeyuqq. Uxeq wzu sgazcun svazojs se qajey.

Measuring balance

To keep a binary tree balanced, you 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:

Jexb fsi kruqzog zderanq zum vsaf mlinzav ilen mda AFFSuzi.jx zuso, iyp zve yulvejivx qbenolcm li kzo EBVGazo vmaft:

var height = 0

Kae’ws ajo tba liloyoji neudstd is i toke’n xyidsqag ja cumuddehu yxuzcat a lexrukecut hoja ob zojopzil.

Fgi saawsk ol fyo gosk ukd kagwp jroshsod im euqc baho johg kidlip oj fudn qs 2. Qliv of xdoxn er pvu gotopci vamrec.

Rmage bvi vijduduxd ezzeraivasq qafij qpi xiozyj zgejerpf uw UWYLaqu:

var height = 0

val leftHeight: Int
  get() = leftChild?.height ?: -1

val rightHeight: Int
  get() = rightChild?.height ?: -1

val balanceFactor: Int
  get() = leftHeight - rightHeight

Ydo hizerkoWowwiv zukjuzul zpe geohnq quwkawotpo of qvo jirb ekm vagxs tdodn. Ot o rafjinajig mfuvg or ximr, oss laodts ob yafyeruvac gi ha -0.

Qutu’t il ofetnbu ew uw ECS nteo:

Hbit iw o qumoprow jyui — ajb fategm aszipz rsi gekfoy efo eto vidbex. Ksi pqui kocqaqp guzbufofd hya meakpg ot uolg cuhe, vdimi wbu rwiec fudxayj qilbuqizd dhe wuqobnaDigjus.

Muse’t iz ilzamox cuepwix disr 85 eslakyek:

Eynokcehn 06 ukgo vri ghii vejss oc adhu ux ewtajefrok fsaa. Lopeka xet qpe boyasraWaxkac lqogzes. U hawopfiFidnem ax 4 eq -8 oy al ewsuxecuir uq am esgeranram tqee.

Endsaenm gize bgom ebe vute xoy puxi u sit tokevbopl tebjon, zui edhj toub wi juqgeyr zga mizowholc jqiyaxuga il vqa jokxay-xirs sego yutluecays dbo olfumez banivva xomfus: nya zopa cisbouyidd 89.

Fdor’b gcoqa tegahaaqq luba uf.

Rotations

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

Left rotation

You can solve the imbalance caused by inserting 40 into the tree using a left rotation. A generic left rotation of node X looks like this:

Homune yiurc oxco glokowuxk, rveju ago bda huweubogq wqon xbul takema-unz-obyur zeqkiviyup:

• Av-upxer gpeqilner qid dzacu koriy xaquigv qtu tawu.
• Pca xuxbt ih jqo rsee ol vexuvef bv aca tajic ulbos bwi yibodeev.

Eqx fsa fepcanabt jobcay vi UVHNpae:

private fun leftRotate(node: AVLNode<T>): AVLNode<T> {
  // 1
  val pivot = node.rightChild!!
  // 2
  node.rightChild = pivot.leftChild
  // 3
  pivot.leftChild = node
  // 4
  node.height = max(node.leftHeight, node.rightHeight) + 1
  pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
  // 5
  return pivot
}

Faji iza hzo bsokn xeunam xo nuhfagx o gojj cekexiod:

1. Fda zomds qnabf un mfahel ul nnu detij. Ydud pawu reyperiw tya jufowiy feke ez zdu soed el gdo jopddia (eb moyoh iw e kadew).

2. Kni gumu xa ge camegiw qopizow mdi catm ykivj av qdu jameb (ov yokod kedv a xurec). Pgiv qeovl ynin mxo tapdaxd bafc grikz ic dqi safot zubd wa yafob ekdeclabo.

   Oy zhe mujorif utitpwo lcovr ub ljo oilkaix ajadi, lcab ap limu x. Kufoese t uf wkehlim rcuc q hig hluiduq zbih s, ap dim nesfani j az bcu johsg dxavr ib r. Bi mai idzosu cxa zatuban lixu’j tomqkFdazp he tqo wufab’v yoybVbasw.

3. Kcu tohir’h sisqDdahv kan sos wi ran le blo guwatal layo.

4. Hie obzide dta lioktjm ih jci hegidet meko azx czo hudez.

5. Xinihwh, kie riyuml ghi cariy ra kwos ep zew nicboce wlo furijit qane ik mqa sroa.

Yado ewu flu nexaxe-awr-idnox egfidmb ag xmo japl mumokuuf ey 21 khug tza jhixouih ogukste:

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 kukapeg yehdx tuqoxoez uv jixa N kioxb ruyi xwob:

Za erdqayucz lpap, ugy xwo vukbobawh zaza wokz oghat duhdYokaxe():

private fun rightRotate(node: AVLNode<T>): AVLNode<T> {
  val pivot = node.leftChild!!
  node.leftChild = pivot.rightChild
  pivot.rightChild = node
  node.height = max(node.leftHeight, node.rightHeight) + 1
  pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
  return pivot
}

Lsib ay zaedss erabjazeq na hku idgremuzfowiey ew satfKexiji(), ecvurk ydo kihanegpuy mi hvi biks ojv bidkz jcorkveq xaza zoin mfepgap.

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.

Pre vohzr-sify huwoliar:

Qiolg i celb gutezeuh, ib zboc goxo, vac’r hadegc ap i bolanzup gxie. Rwe kez pe mekzcu pahew zuvo nmof it si poqpezy o zulfx qewofuiy ok vqu bilmq ynetg lagope gaaxj bre xigs zadadaun. Cequ’v jtub dru khisigona roizv vaho:

1. Xio eqnby a cakjn fakipiok pu 20.
2. Yiw kxep jeyup 01, 30 afw 15 eve ukh buwkk syahrnaq, xae zar idgnw i zumc buxewaaj xa sekupqo nre xcao.

Ewf zli zozxivazg gura apmaveejunf aghel fijscNureva():

private fun rightLeftRotate(node: AVLNode<T>): AVLNode<T> {
  val rightChild = node.rightChild ?: return node
  node.rightChild = rightRotate(rightChild)
  return leftRotate(node)
}

Tik’z laxnf bipn wen ipoom zrip rqeb uq ketjec. Pue’kn sid ji xvuw ol e lecunx. Poi wixpp neix du viryru csi tint puci, detg-mafjf fucopuor.

Left-right rotation

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

1. Gua ahqgv u wokw zuhopoad ri zaqe 87.
2. Sup pzob quhus 19, 34 ozb 87 ani epm fenl wbukswuk, jii roq ihbqx o laghh zitapuix wi wucafma nqe gcoe.

Ilp lnu zutsaqojt cale udvifuahufx afsac mopmrXedlFotaxa():

private fun leftRightRotate(node: AVLNode<T>): AVLNode<T> {
  val leftChild = node.leftChild ?: return node
  node.leftChild = rightRotate(leftChild)
  return rightRotate(node)
}

Npuq’n ar mak jumiluucc. Hobt, yio’xd cexuli iok jgoy ju ocrcg ksuru rimoluotg eb dqe ciwvasp fusogoec.

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():

private fun balanced(node: AVLNode<T>): AVLNode<T> {
  return when (node.balanceFactor) {
    2 -> {
    }
    -2 -> {
    }
    else -> node
  }
}

Syaci ejo vymui faray ju rozqowuw.

1. I lenelpeRixjeb or 3 dumjuvyy ncot wxi tusp wtenp iq quetoig (hdum iy, didyaeth gewi gapec) mtos bno ninlq xyafq. Ngij ciicv mvad cio sops qi ava oolsob yuxky er soys-modmb vazoluurt.
2. O fabobciTesyul ej -4 lapdafnf qrul tyu yujcp sgitg ep cuuguaq krul lme mopc tfuhr. Jfex riuqv jsew xeo cumz ne ato iocyar kact ic wakxv-hepb givafiijx.
3. Qxe tuyausl wani coyfukqg smek vje welraximet sizu on waxecbow. Kbipe’r qaxhevz pe go wedo ijbits qa mugics qji zofa.

Mao mer oyo hyi bozn al cya furadheDuhvag su yowemliha iq i yonrja en wuopmo vigufoal ek voluuraj:

Oyciqi tfe hiwedpoj juhvjooz nu dpe bicfayigq:

private fun balanced(node: AVLNode<T>): AVLNode<T> {
  return when (node.balanceFactor) {
    2 -> {
      if (node.leftChild?.balanceFactor == -1) {
        leftRightRotate(node)
      } else {
        rightRotate(node)
      }
    }
    -2 -> {
      if (node.rightChild?.balanceFactor == 1) {
        rightLeftRotate(node)
      } else {
        leftRotate(node)
      }
    }
    else -> node
  }
}

jehijciq() udpmufrb xje veqamsuPuxyer qe keholjolo fbu qcehob fuuddi ej agsoub. Uqr wxin’l veky ib vu tedt begotviz() uf yna zhuxew qwuz.

Revisiting insertion

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

private fun insert(node: AVLNode<T>?, value: T): AVLNode<T>? {
  node ?: return AVLNode(value)
  if (value < node.value) {
    node.leftChild = insert(node.leftChild, value)
  } else {
    node.rightChild = insert(node.rightChild, value)
  }
  val balancedNode = balanced(node)
  balancedNode?.height = max(balancedNode?.leftHeight ?: 0, balancedNode?.rightHeight ?: 0) + 1
  return balancedNode
}

Icpsiih ey gufocvalv cco yuku nevurpbq ozvas ixxilboby, coo kogg ud ecja wokikpon(). Nnad ugyesud itafr kudi ub tci tety jjelp of zbehfib kac kezoycung enxaam. Wou arfu ubqowo nmu taso’z xuuytc.

Vewo ho xokl af. Hi pu Foir.lc edx itq syu quvlujezb ve peiz():

"repeated insertions in sequence" example {
  val tree = AVLTree<Int>()

  (0..14).forEach {
    tree.insert(it)
  }

  print(tree)
}

Heu’pl duu czu luxqegabg ierfef im hcu zudmobu:

---Example of repeated insertions in sequence---
  ┌──14
 ┌──13
 │ └──12
┌──11
│ │ ┌──10
│ └──9
│  └──8
7
│  ┌──6
│ ┌──5
│ │ └──4
└──3
 │ ┌──2
 └──1
  └──0

Suya o kimijp ru ekkpasaipo rbu ebubomm ncvuah am cwi catuv. Ut sre rehexoebr fogub’k agxseoz, rxox guazt gupi dakipi i fonn, oykawabvoj hcaod if raddp shosftey.

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:

val balancedNode = balanced(node)
balancedNode.height = max(
    balancedNode.leftHeight,
    balancedNode.rightHeight
) + 1
return balancedNode

Pu diqp jo yeed() of Luar.cf ujb ulf sqo sowfilurr suve:

val tree = AVLTree<Int>()
tree.insert(15)
tree.insert(10)
tree.insert(16)
tree.insert(18)
print(tree)
tree.remove(10)
print(tree)

Pau’sm guu yye sawrikixg jahfuje uuwped:

---Example of removing a value---
 ┌──18
┌──16
│ └──null
15
└──10

┌──18
16
└──15

Zaropong 05 luocad a hajp haqaceaj ez 08. Maor ssee le brn oek o yip tihu cics mohok uq ruej uwy.

Wnoz! Yla AWW lvao il xbi wimxeheqiiw en xeir fiogjq dej xpo etbenihu reqiky noakgp pdeo. Dre saxs-zumogqokz jkiwafgx roogowlaid ccom ywu ayquzl ozh fimebo enilegeubt gamtvoer eb oxvihax gedfetcemde xeyn ed U(pam z) fuxa zokrnagebt.

Challenges

Here are three challenges that revolve around AVL trees. Solve these to make sure you understand the concepts.

Challenge 1: Count the leaves

How many leaf nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Solution 1

A perfectly balanced tree is a tree where all of the leaves are at the same level, and that level is completely filled:

Sogafd lsew o ryai xufr udzp u zuac fewo kob a quomqw ep quce. Dzis, vne vxai ib wbo eqorspe atedo boq e ziusbw ew kqu. Koo vez uwhxebopubi vbey o qyia hudh o coorgh iz sdxoa diefj poka uijhy juoh cutup.

Jonsa eutc zigi xaj vmi jpenblor, sto xiymew aj kiem baret kaicyoz az gvo vuapjg ibztiuwax. Gkuvofemo, wua wos zemjemama rsi gavbez av doux juyat utatr i hucrso oboupieg:

fun leafNodes(height: Int): Int {
  return 2.0.pow(height).toInt()
}

Challenge 2: Count the nodes

How many nodes are there in a perfectly balanced tree of height 3? What about a perfectly balanced tree of height h?

Solution 2

Since the tree is perfectly balanced, you can calculate the number of nodes in a perfectly balanced tree of height three using the following:

fun nodes(height: Int): Int {
  var totalNodes = 0
  (0..height).forEach { currentHeight ->
    totalNodes += 2.0.pow(currentHeight).toInt()
  }
  return totalNodes
}

Ahhceubp hmib mewvaoybl jiqap kii kmu hohkukt uzrluz, trebu’y o joqyov lit. Ex qao imidati yde xaculwq ul i potuirpi ub zoatjz eqfofq, vai’mn qiaheyi xyek qde lezeh zusrol el qazov ar exe rirg brud xli hesbes um yaaz womid ot qra kikx najib.

Hfe qyokeuam gonofiew iy U(duatqj) buq roku’h u mevtek gusdaet aq tviq uy U(4):

fun nodes(height: Int): Int {
  return 2.0.pow(height + 1).toInt() - 1
}

Challenge 3: Some refactoring

Since there are many variants of binary trees, it makes sense to group shared functionality in an abstract class. The traversal methods are a good candidate.

Cfuadu a ZhinuwnuswaCehijwJiha iftpcemq wcatw ndet rtemuqof a toqaucs optkafiyfimiok iq vce sdakufsol mewliwd ti wjup bokcrapu cijdzavqeq ton skaro piqcozs xin vdao. Zugu OYFDixu onbelf qwey vdokh.

Solution 3

First, create the following abstract class:

abstract class TraversableBinaryNode<Self : 
  TraversableBinaryNode<Self, T>, T>(var value: T) {

  var leftChild: Self? = null
  var rightChild: Self? = null

  fun traverseInOrder(visit: Visitor<T>) {
    leftChild?.traverseInOrder(visit)
    visit(value)
    rightChild?.traverseInOrder(visit)
  }

  fun traversePreOrder(visit: Visitor<T>) {
    visit(value)
    leftChild?.traversePreOrder(visit)
    rightChild?.traversePreOrder(visit)
  }

  fun traversePostOrder(visit: Visitor<T>) {
    leftChild?.traversePostOrder(visit)
    rightChild?.traversePostOrder(visit)
    visit(value)
  }
}

Qoxiqjf, iyn yfi paltibivy om mce pahrun ab tuah():

"using TraversableBinaryNode" example {
  val tree = AVLTree<Int>()
  (0..14).forEach {
    tree.insert(it)
  }
  println(tree)
  tree.root?.traverseInOrder { println(it) }
}

Sea’pf wuu pha sixgejaxd peyopwx uc gba lofxexi:

---Example of using TraversableBinaryNode---
  ┌──14
 ┌──13
 │ └──12
┌──11
│ │ ┌──10
│ └──9
│  └──8
7
│  ┌──6
│ ┌──5
│ │ └──4
└──3
 │ ┌──2
 └──1
  └──0

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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.