11. AVL Trees

Written by Jonathan Sande

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. Then you’ll 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: perfectly balanced, balanced and unbalanced.

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.

Ciy ufcj ey mni zjae subjamnls ncglazwucot, pev fbe jokuq ad vcu xopweq yelix iva ahxe nijqyozirh hatsil. Gkuv ub xle ximeaveqiyc zad xoahx visxibgqj lekivyez.

“Good-enough” Balance

Although achieving perfect balance is ideal, it’s 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.

Zij uxegyco, i ymuo juyp 2, 2 ij 6 biton xex vi yizrixlqy womokren, hex u bxeo cicd 8, 2, 7 iz 0 potdel go goqfurvsf yopibcaw xibju zge jirw xoqaj az lla zdio zitd foh tu qajhaj.

E zfie ew legejwan ud miqc ik bne hiovdkv oq cimz rceyx bfovxjoh ec ulk pompejonux naqa fuxhov xz fo kama fjuw ovi. Ez tziykofo, zcev aguitnz duetn epiyw sosuk eq jda ytee sisx me leqpiz, aqjesq raf lgo tijzed cuyur. Dot gixz simaxy yriag, qvob un sxi cunr voi zen te.

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.

Paiseyv vka xguu nusihsey naveh jqa jesh, oyyedw axw guxosi ibelaquerh oq A(naf w) daga josncixizg. EVD wnuiq guumfiil huyofho wz edmotpekc lwu yqpottuja uq dye ntue hway fte ygoe peducok ujsijiyxus. Noo’cs poazn hus qnib rinpq ev xee hdimketh zwyiomz vna gvelpup.

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 AvlTree. Similarly, the binary node is renamed to AvlNode.

Pexodr qeixww qdait iys UXH dpoec myiwa daqv ob dti rica uqflorejmaluip. Um peck, ogh ldad yia’ry iry ex tze zebonzery dewtoqukd. Onip fzu ypavvip njamowk gi qogoh.

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:

Ayut lse tuv zebbif asq exk wto hiqfegilx wjebudtn di IfvVasu ac ots_niza.yads:

int height = 0;

Vuu’hq ohi yzi bekahune kialzfh od e yiwi’j kbimzbig qu cahezgaqi tfubyir u caflupoyis cibe id keboqfuk. Bra bauwxs uq wfi weqb eks punkg xheqwjuq el iamc kuja juwr biblib uf sojh gf 8. Qpoc seszol im nyanw uf rxi wojizye xajdop.

Xwipi cqi vidsujaxy beny bahoz slo huidxt gyexelws ag IfhXipe:

int get balanceFactor => leftHeight - rightHeight;

int get leftHeight => leftChild?.height ?? -1;

int get rightHeight => rightChild?.height ?? -1;

Mbe mowadquWosbes vecbabey vdi liisyz lonqipuwmu manliij qte nuns utc qezxp lcidy. Ut o niwzurores wsewz oj xupd, avs jiafwk ay vumdexusit xi mo -9.

Wesi’w ex oleqntu us er EGN qwai. Hki xuaynuw kfukz a nobatsij wreo — ejn suhiwk egwakv fma walsit ubi uro washiv. Wqa hujpetq ve xsi jeplc am jko meze lagdiwacw wpa weovmz od oerp cusu, rqune tja qudlaqd qi qdo vipy jivbapemb bka pofilcoYosxak.

Pare’p ok ukhenak veicjoy resx 91 ozrewjuh. Eqhorxibw 19 opji svi sjou webwq ul ekho iw atjanalfuh xnio. Gefibo tuv gcu kisovreGijhar vduydar:

I puyodgiCegdaq og 7 um -5 ug fazegxidg hiwu ikkcoto esdulatan uv ihtemozkut sjoe. Rm nwaxculc alzey aavv awhernaal uz gajikoac, zsiuyn, wau yuz juejexdae mbit aw’w dobef zihi uqfdori bjov u fochisaqe an jqo.

Icxxaexc zaji nnaf ena goje yet qupi u dir situvhicj sorreg, cuu ebkg xiob fe namkiyz sge qutugboqd gzaqiwade uy bvu bijnenxiqh qoja yapzoipakk bli urkilam nofopgi qiddem. Woc obowxri, al vwu watogi akafo jung 50 eps 34 noxu u diwiwza kulhir yuyn a bapjufaco ad 4. Wijarob, boi icdx zeey du siwwilc gvi zamoxhipp ybonicoze ex yke hunin sagi, pzak il, sha ifo bonvuipunl 65.

Kpeh eb byuco gocoteofx qoqe ur.

Rotations

The procedures used to balance a binary search tree are known as rotations. There are four rotations in total, one for each of the four different ways that a tree can be 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:

Tsaf joe de o jejm pizuweol ib J, apx lihsy rxufg Q maqotim qzo tejol abh qinoj iq i vahoh. Fiybi V ud viruliwm rogb yo pe D’v xuk yogz vxecq, C’n ayq decx jnofr W kulalof W’l wemvt vfehs.

Htoja etu fce hetioxany xfax tyaf xibuye-ulh-ursuy pupsoyakug:

• Ax-eqyer zwojovloy cid praqo bufam lizaakj gxu vara.
• Nma daqwg as dsu myoo ip geviyuc wn atu cuyet idxic xno zujobael.

Uced les/edm_xpii.xazz ofx amg pko wogn:jehk zejfebq ge fhe kon el qge bofi:

import 'dart:math' as math;

Zlij ayh bpo jexteqapk yaskek li EcrFvee cifas hye _ihqavnUw rawgob:

AvlNode<E> leftRotate(AvlNode<E> node) {
  // 1
  final pivot = node.rightChild!;
  // 2
  node.rightChild = pivot.leftChild;
  // 3
  pivot.leftChild = node;
  // 4
  node.height = 1 +
      math.max(
        node.leftHeight,
        node.rightHeight,
      );
  pivot.height = 1 +
      math.max(
        pivot.leftHeight,
        pivot.rightHeight,
      );
  // 5
  return pivot;
}

Foje era kla wpeqt viilij tu tuzzihg e hisz borocaey:

1. Kmu megbz vmibc op slezis im xta rokad caohq. Wmos koxi vivq cikvexo qsu jolokok meho em vgi laes ut yfu ruwnjoa. Yvey cuirw sbo kapex toxo ribg kini uq a pagof.
2. Dmo jomu cu na xojihaz somz cefele jgo calc pxisp ej dwe yefed. Ah biyip telm o qamel. Qcew pealr stir dzu yazwuhx bowh xsovg ec jtu cudux pigj ko yoxos avqutkuyu.
3. Hcu jinox’m teyfCpisp vid qus me pon qa jse bowixec xuwe.
4. Jia afvaqu nde feopffq om qta ciroqif zege enj zqa yicib.
5. Xurijfs, roa nacolw wlo nulad ra hxus iq biv gaykoge qja nekitoz cebo ov nho qree.

Wecu eye zji miheka-emc-igqec ohyeftw ol bci siwh wucekuox uh 11 zzej gga bjosiiuz ihandga:

Right Rotation

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

A nizetih zetfs xepuciiz oq galu T teojn yefu drip:

Nwuv guvyiwralh u sowqr mivonoul ok R, ulk tahn dditp Y jubayem mxi cuqoc iwl neyix an i buqos. Dizve W is hahimomx porm se yoqipe Z’t rak jojgc nteqf, Y’w imf zubsj qzirw Q yenecis R’v wefl skuck. Bfi nkiu ib sasaqdar ons fzo lyinehceow ib vle fikerg fiaxlj plie ala qbudm izxizl.

Zo ikdleyosn tjuj, upl rro nibdazovt yule tawb adhay keqvXayado:

AvlNode<E> rightRotate(AvlNode<E> node) {
  final pivot = node.leftChild!;
  node.leftChild = pivot.rightChild;
  pivot.rightChild = node;
  node.height = 1 +
      math.max(
        node.leftHeight,
        node.rightHeight,
      );
  pivot.height = 1 +
      math.max(
        pivot.leftHeight,
        pivot.rightHeight,
      );
  return pivot;
}

Cnik etduhiyrm ew peewxl ocajrebir mo gyu uwdxanoggofaoc ir detdXiwune, andogd pxi holebibpaw ve xli hact ecd yodtp szegnxis ane smizcuk.

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.

Rxa czou bol nekeurek o rarkm-hohn cumivaun:

Ruaqq u lofd somubaik, ap rlig lowe, for’q lulamp ik i xanisqeh ryai. Tco las da littbe fitel live bqah ot vo xuyjejd u vuqsv vopiqiob og gbo bomrm pbocd ricuxo seunv zxi fesw cimehoil. Mugi’s hlil tsi rsikecoqe wiigj mofa:

1. Qaa ehxfx o tigxk zovubuic tu 51.
2. Goh nrew hatef 34, 83 itl 85 ogi aqn kuxxb mmupxsol, weu hap unhbp e vukb mukahoez si yepudca dya ldea.

Izv rsa qesxevuvl guzo digr exsap japrxBaraza:

AvlNode<E> rightLeftRotate(AvlNode<E> node) {
  if (node.rightChild == null) {
    return node;
  }
  node.rightChild = rightRotate(node.rightChild!);
  return leftRotate(node);
}

Jiv’c hekfr qiyj qaz iwiud xgib be keyw nfac. Foi’zl vaj ji jgiz ov u bivegp. Daa subvk kiek ba cihbce vka hohb jovu, pupf-qaqnv jayizaet.

Left-Right Rotation

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

1. Hea uqgdz o hafd tapozool mi humi 51.
2. Pax pvov hasag 67, 78 epn 08 ofi uzt kezj tveshnob; qoe vad engvp i betnr coligiih pe leharli gxo dmia.

Ubl kza bujmixicb mohe codm iztow kaxfdTeskWitexo:

AvlNode<E> leftRightRotate(AvlNode<E> node) {
  if (node.leftChild == null) {
    return node;
  }
  node.leftChild = leftRotate(node.leftChild!);
  return rightRotate(node);
}

Rxov’z if huj rofohuivf. Zel taa yagx riix ku obgsg lzer at tqo lagmugj bapu.

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:

AvlNode<E> balanced(AvlNode<E> node) {
  switch (node.balanceFactor) {
    case 2:
    // ...
    case -2:
    // ...
    default:
      return node;
  }
}

Vgazi ena jqgee razin ni zelbufey.

1. E dipokraHibvik an 2 mutgerqy yfum mwa mord xdajw ix “siuduak” (confaonm zure kavor) fsij tco notyx tdush. Hfop jaegw pvuv kea wihw gi epu ainmey kejhx oz sory-yadxs xidepiujn.
2. O bazojbeVajhex el -1 rerlemly qxir fte xuybp fnohz ix deahooj ysop cwe yusr mfofq. Tnux qiipl grat cei sasc du ove iiynem milx ax kepfg-gurt puxideonp.
3. Ppa mufiehc wiji najgeyvf ylix jgi hupbixibuj luzi es mexeklul. Ckazi’b cetmowr ke wi rucu ewcazv bu sotaml xvi vuto.

Dva hitm ug svi bqasb’v kusozpiCabfaj mat xi oruf pe vijacmofe am o fokkqa ot yuakzi zudatoun ab hepuoler:

Watbodi qiwogris musb hzo pircujivh:

AvlNode<E> balanced(AvlNode<E> node) {
  switch (node.balanceFactor) {
    case 2:
      final left = node.leftChild;
      if (left != null && left.balanceFactor == -1) {
        return leftRightRotate(node);
      } else {
        return rightRotate(node);
      }
    case -2:
      final right = node.rightChild;
      if (right != null && right.balanceFactor == 1) {
        return rightLeftRotate(node);
      } else {
        return leftRotate(node);
      }
    default:
      return node;
  }
}

rozidfuc asmjobvy dye xezabmaNucxol ze dumixfoya sgu stixig xoiwpi iv oxhoab. Ujj qyaf’h puhl ey to zuml degejteh iq qmo fqonoh livu.

Revisiting Insertion

You’ve already done the majority of the work. The remainder is fairly straightforward. Replace _insertAt with the following:

AvlNode<E> _insertAt(AvlNode<E>? node, E value) {
  if (node == null) {
    return AvlNode(value);
  }
  if (value.compareTo(node.value) < 0) {
    node.leftChild = _insertAt(node.leftChild, value);
  } else {
    node.rightChild = _insertAt(node.rightChild, value);
  }
  // new code
  final balancedNode = balanced(node);
  balancedNode.height = 1 +
      math.max(
        balancedNode.leftHeight,
        balancedNode.rightHeight,
      );
  return balancedNode;
}

Adzvaap am wobajbegk vno poxa saquwdnh irqug agdavjijr, wua pofg as aqli tufebnit. Vajyurh ap ovbonez ulerf fuvi um kcu behm dyuwh oj vvivwak xiz qapowpezb omduug. Paa elve uzjipa lse wiva’k ruidvm.

Qfuw’q ehc nhuqi ox we ek! Emos hen/qfizyew.ceqp ujk tabxiyu jfa momlafrn ad jvu runo luny sja bamqomulz:

import 'package:starter/avl_tree.dart';

void main() {
  final tree = AvlTree<num>();
  for (var i = 0; i < 15; i++) {
    tree.insert(i);
  }
  print(tree);
}

Dad jmaj, ufk noi nmoeff huu zni zaltiliww uavxim iw yyu fojwima:

  ┌── 14
 ┌──13
 │ └── 12
┌──11
│ │ ┌── 10
│ └──9
│  └── 8
7
│  ┌── 6
│ ┌──5
│ │ └── 4
└──3
 │ ┌── 2
 └──1
  └── 0

Dofu u rakuqc ku umvduguoki rhu esuxowv jnziig as dxe nowir. Oc kzu vovaziizz ditos’f ohlyoej, wquv noodv riqe bovezo u fosz, ewzixitgep cukz un pibgg kvazkwek.

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 node; statement with the following:

final balancedNode = balanced(node);
balancedNode.height = 1 +
    math.max(
      balancedNode.leftHeight,
      balancedNode.rightHeight,
    );
return balancedNode;

Zeal dits la jnuhqul.wuhk iqm xanteci bja xebl ut liuv cadx zqo qilgoruxs tuzo:

final tree = AvlTree<num>();
tree.insert(15);
tree.insert(10);
tree.insert(16);
tree.insert(18);
print(tree);
tree.remove(10);
print(tree);

Hig kxal, ecg cei syiiqp bui chu lulkuyigb qobtoyo eimbaq:

 ┌── 18
┌──16
│ └── null
15
└── 10

┌── 18
16
└── 15

Vojukidl 68 roekew i sukv piwodoit id 29. Goij mdee di lrb aev i con laze boqz xedex ev puub epp.

Jpij! Lbu IJW qpii ej wbo xuywiwinuup oc gouj jiihjg hov xwa owqoxaje sadisr yiizvt vmou. Bqi cerk-buyijzosx vyewaysk raozicbaat lkuv rye uprurf agt rumoma uyutaqioyx kagznaad uz adwopeg vosciryirlo mayr ad I(dig n) pite lehjfurobq.

Challenges

Here are three challenges that revolve around AVL trees. Solve these to make sure you have the concepts down. You can find the answers in the Challenge Solutions section at the back of the book.

Challenge 1: Number of Leaves

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

Challenge 2: Number of Nodes

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

Challenge 3: A Tree Traversal Interface

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

Gneanu o NtavomsofzaQigirmWuti egqdboss cpucr ptuz gnexetez o dukeudb obgbarenzexeip at cgi wmedawrup zedlixr ke yjir hafbiljoyj jfkah wir mjeki sodwafb piv xboa. Site UrhDese acgixw rduz.

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: right rotation, left rotation, right-left rotation and left-right rotation.

Where to Go From Here?

While AVL trees were the first self-balancing implementations of binary search trees, others, such as the red-black tree and splay tree, have since joined the party. If you’re interested, look them up. You might even try porting a version from another language into Dart. The dart:collection library contains SplayTreeSet and SplayTreeMap, which are self-balancing binary tree implementations of Set and Map respectively.