COMP251: Binary search trees, AVL trees & AVL sort
Jérôme Waldispühl School of Computer Science
McGill University
From Lecture notes by E. Demaine (2009)
Midterm #1
• Wednesday September 30.
• Duration of the exam:
o Theory: 1h30
o In practice: 3h30. The latter accounts for technical issues
(i.e. internet) and barrier of learning.
• When? We will open a timeframe of 24h during which you can take the exam. WARNING: submissions will start on Sep. 30 at 9:00am (EDT) and close on Oct. 1 at 9:00am (EDT). If you start later than 5h30am (EDT) on Oct 1, you will have less than 3h30 to complete the exam. Submit early!
• How? We will use crowdmark.
• We will send a list of problems and will implement a practice question on crowdmark to allow you to test the platform.
Outline
• Review of binary search trees • AVL-trees
• Rotations
• BST & AVL sort
Binary search trees (BSTs)
x
≤x ≥x
• Tisarootedbinarytree
• Key of a node x ≥ keys in its left subtree. • Key of a node x ≤ keys in its right subtree.
Operations on BSTs
• Search(T,k): Θ(h) • Insert(T,k): Θ(h) • Delete(T,k): Θ(h)
Where h is the height of the BST.
Height of a tree
Height(n): length (#edges) of longest downward path from node n to a leaf.
x
Height(x) = 1 + max( height(left(x)), height(right(x)) )
Height(right(x))
Height(left(x))
a bg
Example
h(a) = ?
= 1+max( h(b) , h(g) )
= 1+max(1+max(h(c),h(d)),1+h(h)) = 1+max(1+max(0,h(d)),1+0)
= 1+max(1+max(0,1+h(e)),1)
= 1+max(1+max(0,1+(1+h(f)))),1) = 1+max(1+max(0,1+(1+0))),1)
= 1+max(3,1)
=4
c
d h
e f
Height vs. Depth
https://stackoverflow.com/questions/29326512/what-is-the-difference-between-the-height-of-a-tree-and-depth-of-a-tree
Good vs. Bad BSTs
56
18
26
28
h
26
18 28
200
190 213
56
190
h
200
213
Balanced h=Θ( log n )
Unbalanced h=Θ( n )
AVL trees
Definition: BST such that the heights of the two child subtrees of any node differ by at most one.
x
|hleft-hright|≤1
• Invented by G. Adelson-Velsky and E.M. Landis in 1962.
• AVL trees are self-balanced binary search trees.
• Insert, Delete & Search take O(log n) in average and worst cases.
• To satisfy the definition, the height of an empty subtree is -1
Height of a AVL tree Nh = minimum #nodes in an AVL tree of height h.
x
Nh-2
Larger height when tree is unbalanced.
𝑁! > 2″ $ 𝑁 !#$” 𝐿𝑒𝑡 𝑘 = h⁄2 − 1:
𝑁!>2!⁄$#& $𝑁& 𝑁! >2!⁄$#&
Nh-1
Nh= 1+Nh-1 +Nh-2 > 2⋅Nh-2
⇒ Nh>Θ(2h/2)
⇒ h< 2⋅LogNh
⇒ h= O(logn)
(Note: a tighter bound can found using Fibonacci numbers)
Balance factor
xx
=ß
Nh-1 Nh-1
Nh-1
Nh-2
x
è
Nh-1
Violate AVL property
x
à
Nh-3
>1
Nh-2
Nh-1
ß: Left tree is higher (left-heavy) = : Balanced
à: Right tree is higher (right-heavy)
Insert in AVL trees
1.Insert as in standard BST 2.Restore AVL tree properties
x insert(y) x restoreAVL() x àèà
y
Insert in AVL trees
36
ß àß
12
57
8
= 20ß
27 43
= =
Insert(T, 15)
Insert in AVL trees
36
12 ç 57
ß
8
= 20ç
ß
15
=
=
27 43
Insert(T, 15)
How to restore AVL property?
ç
Rotations
y Right rotation x xCAy
AB BC Left rotation
Rotations change the tree structure & preserve the BST property. Proof: elements in B are ≥ x and ≤ y…
Example (right rotation)
y x
y x
C
AB AB
xx
AyAy BCB
C
C
Example: Insert in AVL trees
36 Right rotation at 27 36
ß
ß
12 57 12 57
àß
àß
8 27 43 8 20 43
= ==
=
15
=
20ç= = 15 =27 ß
Example: Insert in AVL trees
36 Right rotation at 57 36 =
12 57 12 43
àçè
8 20 43 8 20 57
=à
15 27 50 15 27 50
ß
=
===
Insert(T, 50) RotateRight(T,57)
How to restore AVL property?
Example: Insert in AVL trees
36 Left rotation at 43 36
12 57 12 57
ç
ç
50
ß
We remove the zig-zag pattern
RotateLeft(T,43)
8 20 43 8 20
15 27à 50 15 27 43
Example: Insert in AVL trees
36
Right rotation at 57
36
12
50 8 20 43 57
50
=
15 27
AVL property restored!
RotateRight(T,57)
12
57
ç
ß
8
20
15 27 43
Algorithm: Insert in AVL trees
1. Suppose x is lowest node violating AVL
2. If x is right-heavy:
• If x’s right child is right-heavy or balanced: Left
rotation (case A)
• Else: Right followed by left rotation (case B)
3. If x is left-heavy:
• If x’s left child is left-heavy or balanced: Right rotation
(symmetric of case A)
• Else: Left followed by right rotation (sym. of case B)
4. then continue up to x’s ancestors.
è
Left rotation
=
Proof: Case A
y
A yh+1 hx Ch
x
à
=
h-1
h-1B Ch h-1A Bh-1
è
x
A
h B
Left rotation
ß
y
C h B h
h-1
=à y h+1 h+1 x
C h h-1 A
Proof: Case B
Right rotation at y &
Left rotation at x =
ßàzß
A
z Dh-1h-1A B C D
BC
è
h-1
h
x
y h+1 h x y h
h-1
è
Right rotation at y
ß
x
z h+1
y h
D Left rotation at x
Proof: Case B
x
y h+1 h-1
z
BC
è
h-1
à
A
A
h-1 B
h
D h-1 àzß
=
C
h-1
h-1
hx yh ABCD
Running time AVL insertion
• Insertion in O(h)
• At most 2 rotations in O(1)
• Running time is O(h) + O(1) = O(h) = O(log n) in AVL trees.
Sorting with BSTs
1. BSTsort
• Simple method using BSTs
• Problem: Worst case Ο 𝑛!
2. AVLsort
• UseAVLtreestogetΟ 𝑛#log𝑛
In-order traversal & BST
inorderTraversal(treeNode x) inorderTraversal(x.leftChild); print x.value; inorderTraversal(x.rightChild);
x
AB
• Print the nodes in the left subtree (A), then node x, and then the nodes in the right subtree (B)
• InaBST,keysinA≤x,andkeysinB≥x.
• InaBST,itprintsfirstkeys≤x,thenx,andthenkeys≥x.
In-order traversal & BST
36
12
27
57 43
8
20
15
8, 12, 15, 20, 27, 36, 43, 57 All keys come out sorted!
BST sort
1. Build a BST from the list of keys (unsorted)
2. Use in-order traversal on the BST to print the keys.
36
12
8
57
43
27
36
12
57
27
Running time of BST sort: insertion of n keys + tree traversal.
8
43
à8, 12, 27, 36, 43, 57
Running time of BST sort
• In-order traversal is Θ(n)
• Running time of insertion is O(h)
Best case: The BST is always balanced for every insertion.
Ω(n log(n))
Worst case: The BST is always un-balanced. All insertions on
same side.
∑n n ⋅ ( n − 1 ) 2
i= 2 =O(n ) i=1
AVL sort
Same as BST sort but use AVL trees and AVL insertion instead.
• Worst case running time can be brought to O(n log n) if the tree is always balanced.
• Use AVL trees (trees are balanced).
• Insertion in AVL trees are O(h) = O(log n) for balanced trees.