AVL Trees
K08 Δομές Δεδομένων και Τεχνικές Προγραμματισμού
Κώστας Χατζηκοκολάκης
Balanced trees
 We saw that most of the algorithms in BSTs are $O(h)$
 But $h = O(n)$ in the worstcase
 So it makes sense to keep trees “balanced”
 Many different ways to define what “balanced” means
 In all of them: $h = O(\log n)$
 Eg. complete are one type of balanced tree (see Heaps)
 But it's hard to maintain both BST and complete properties together
 AVL: a different type of balanced trees
AVL Trees

An AVL tree is a BST with an extra property:
For all nodes: $ \text{height(leftsubtree)}  \text{height(rightsubtree)} \le 1 $

In other words, no subtree can be much shorter/taller than the other

Recall: height is the longest path from the root to some leaf
 tree with only a root: height 0
 empty tree: height 1

Named after Russian mathematicians AdelsonVelskii and Landis
Example – AVL tree
Example – AVL tree
Example – AVL tree
Example – NonAVL tree
Example – NonAVL tree
Example – Non AVL tree
The desired property
 In an AVL tree: $h = O(\log n)$
 $n(h)$: minimum number of nodes of an AVL tree with height $h$
 We show that $ h \le 2 \log n(h)$
 by induction on $h$
 induction works very well on recursive structures!
 The base cases hold trivially (why?)
The desired property
 Inductive step
 Assume $\frac{h}{2} \le \log n(h)$ for all $h < k$
 Show that it holds for an AVL tree of height $h=k$
 Both subtrees of the root have height at least $h2$
 because of the AVL property!
 So $n(k) \ge 2n(k2) \qquad\qquad(1)$
 Induction hypothesis for $h=k2$
 $\frac{k2}{2} \le \log n(k2)$
 From $(1)$ we take $\log$ on both sides and apply the ind. hypothesis
 $\log n(k) \ge 1 + \log n(k2) \ge 1 + \frac{k2}{2} = \frac{k}{2}$
Balance factor
A node can have one of the following “balance factors”
Balance factor 
Meaning 
 
Subtrees have equal heights 
/ 
Left subtree is $1$ higher 
// 
Left subtree is $>1$ higher 
\ 
Right subtree is $1$ higher 
\\ 
Right subtree is $>1$ higher 
Nodes 
, /
, \
are AVL.
Nodes //
, \\
are not AVL.
Example AVL Tree
Example AVL Tree
Example AVL Tree
Example AVL Tree
Example AVL Tree
Example nonAVL Tree
Example nonAVL Tree
Example nonAVL Tree
Example nonAVL Tree
Operations in an AVL Tree
 Same as those of a BST
 Except that we need to restore the AVL property
 after inserting a node
 or deleting a node
 We do this using rotations
Recursive AVL restore
 Restoring the AVL property is a recursive operation
 It happens during an insert or delete
 Which are both recursive
 When their recursive calls are unwinding towards the root
 So when we restore a node $r$, its children are already restored AVL trees
AVL restore after insert

Assume $r$ became \\
after an insert (the case //
is symmetric)

Let $x$ be the root of the right subtree
 The new value was inserted under $x$ (since $r$ is
\\
)

What can be the balance factor of $x$?
\\
and //
are not possible since the child $x$ is already restored

Case 1: $x$ is \
 A leftrotation on $r$ restores the property!
 Both $r$ and $x$ become

(easily seen in a drawing)
Insert: single left rotation at r
AVL restore after insert
 Case 2: $x$ is
/
 This is more tricky
 A leftrotation on $r$ (as before) might cause $x$ to become
//
 We need to do a double rightleft rotation
 First rightrotation on $x$
 Then leftrotation on $r$
 The leftchild $w$ of $x$ becomes the new root
 $w$ becomes

 $r$ becomes

or /
 $x$ becomes

or \
Insert: double rightleft rotation at x and r
AVL restore after insert
 Case 3: $x$ is

 This in fact cannot happen!
 Assume both subtrees of $x$ have height $h$
 Then the left subtree of $r$ also must have height ($h$)
 Otherwise AVL would be violated before the insert (see the drawings)
Symmetric case
 The case when $x$ becomes
//
is symmetric
 We need to consider the BF of its leftchild $x$
 $x$ is
/
: we do a single right rotation at $r$
 $x$ is
\
: we do a double leftright rotation at $x$ and $r$
 $x$ is

: impossible
Insert: single right rotation at r
Insert: double leftright rotation at x and r
Insert example
Inserting BRU, causes single rightrotate at ORY
Inserting DUS
Inserting ZRH
Inserting MEX
Inserting ORD
Inserting NRT, causes double rightleft rotation at ORD and MEX
AVL restore after delete
 Assume $r$ became
\\
after an insert (the case //
is symmetric)
 Let $x$ be the root of the rightsubtree
 The value was deleted from the left subtree (since $r$ is
\\
)
 What can be the balance factor of $x$?
\\
and //
are not possible since the child $x$ is already restored
 Case 1: $x$ is
\
 A leftrotation on $r$ restores the property!
 Both $r$ and $x$ become

(easily seen in a drawing)
Delete: single leftrotation at r
AVL restore after delete
 Case 2: $x$ is

 After a delete this is possible!
 A leftrotation on $r$ again restores the property
 $r$ becomes
\
, $x$ becomes /
Delete: single leftrotation at r
AVL restore after delete
 Case 3: $x$ is
/
 This is more tricky
 A leftrotation on $r$ (as before) might cause $x$ to become
//
 We need to do a double rightleft rotation
 First rightrotation on $x$
 Then leftrotation on $r$
 The leftchild $w$ of $x$ becomes the new root
 $w$ becomes

 $r$ becomes

or /
 $x$ becomes

or \
Delete: double rightleft rotation at r
Delete example
Deleting a, causes single leftrotate at d
Deleting m, causes double leftright rotation at d and h
Complexity of operations on AVL trees
 Search on BST is $O(h)$
 So $O(\log n)$ for AVL, since $h \le 2\log n$
 Insert/delete on BST is $O(h)$
 We add at most on rotation at each step, each rotation is $O(1)$
 So also $O(\log n)$
 Interesting fact
 During insert at most one rotation will be performed!
 Because both rotations we saw decrease the height of the subtree
Implementation details
 We need to keep the height of each subtree
 to compute the balance factors
 If we need to save memory we can store only the balance factors
 Restoring after both insert and delete are similar
 We can treat them together
Readings
 T. A. Standish. Data Structures, Algorithms and Software Principles in C.
Chapter 9. Section 9.8.
 R. Kruse, C.L. Tondo and B.Leung. Data Structures and Program Design in C.
Chapter 9. Section 9.4.
 M.T. Goodrich, R. Tamassia and D. Mount. Data Structures and Algorithms in C++. 2nd edition.
Section 10.2