COMP90038 Algorithms and Complexity
Balanced Trees
Olya Ohrimenko
(Slides from Harald Søndergaard)
Lecture 15
Semester 2, 2021
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021) Balanced Trees © University of Melbourne 1 / 1
Weekly update
Assignment 2 out during week 9
Olya’s consultation this week: see LMS for details Non-teaching period next week
Piazza
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 2 / 1
Last Lecture
Correction on the question in the poll:
“Heaps can be used to quickly find an item with lowest priority”. True/False.
“Heaps can be used to quickly find an item with lowest key”. True/False.
Transform and conquer:
Pre-sort
Binary Search Trees
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 3 / 1
Approaches to Balanced Binary Search Trees
To optimise the performance of BST search, it is important to keep trees (reasonably) balanced.
Instance simplification approaches: Self-balancing trees
AVL trees
Red-black trees Splay trees
Representational changes:
2–3 trees
2–3–4 trees B-trees
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 4 / 1
AVL Trees
Named after Adelson-Velsky and Landis.
Recall that we defined the height of the empty tree as -1.
For a binary (sub-) tree, let the balance factor be the difference between the height of its left sub-tree and that of its right sub-tree.
An AVL tree is a BST in which the balance factor is -1, 0, or 1, for every sub-tree.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 5 / 1
AVL Trees: Examples and Counter-Examples
Which of these are AVL trees?
10 10 10 10
5 20 5 20 520 5 20 3 7 12 25 3 7 12 3 7 3 7 25
282 24829
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 6 / 1
Building an AVL Tree
As with standard BSTs, insertion of a new node always takes place at the fringe of the tree.
If insertion of the new node makes the AVL tree unbalanced (some nodes get balance factors of 2 or -2), transform the tree to regain its balance.
Regaining balance can be achieved with one or two simple, local transformations, so-called rotations.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 7 / 1
AVL Trees: R-Rotation
20
32 1⇒00 213
0 1
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021) Balanced Trees © University of Melbourne 8 / 1
AVL Trees: L-Rotation
-2 0 12
-1 ⇒0 0 213
0 3
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021)
Balanced Trees © University of Melbourne 9 / 1
AVL Trees: LR-Rotation
20
32
-1 ⇒0 0 113
0 2
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021)
Balanced Trees © University of Melbourne 10 / 1
AVL Trees: RL-Rotation
-2 0 12
1⇒00
313 0
2
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021)
Balanced Trees © University of Melbourne 11 / 1
AVL Trees: Where to Perform the Rotation
Along an unbalanced path, we may have several nodes with balance factor 2 (or -2):
2
4 20 35
1
2 0
1
It is always the lowest unbalanced subtree that is re-balanced. …………… . ….
…………….. …
⇒
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 12 / 1
AVL Trees: Where to Perform the Rotation
Along an unbalanced path, we may have several nodes with balance factor 2 (or -2):
21
44 20⇒00 3525
100
213 0
1
It is always the lowest unbalanced subtree that is re-balanced. …………… . ….
…………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 13 / 1
AVL Trees: The Single Rotation, Generally
20 rc
10 cr
T3 ⇒ T1
T1 T2 T2 T3
This shows an R-rotation; an L-rotation is similar.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 14 / 1
AVL Trees: The Double Rotation, Generally
20
g
-1 10 c cr
r -1
g
T4
⇒
T2 T3 T1TTT1 T4
23
This shows an LR-rotation; an RL-rotation is similar.
…………… . ….
…………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 15 / 1
Properties of AVL Trees
The notion of “balance” that is implied by the AVL condition is sufficient to guarantee that the depth of an AVL tree with n nodes is Θ(log n).
For random data, the depth is very close to log2 n, the optimum. Deletion is harder to implement than insertion, but also Θ(log n).
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 16 / 1
Other Kinds of Balanced Trees
A red-black tree is a BSTs with a slightly different concept of “balanced”. Its nodes are coloured red or black, so that
1 No red node has a red child.
12
9 15
6 10
4
A worst-case red-black tree (the longest path is twice as long as the shortest path).
2 Every path from the root to the fringe has the same number of black nodes.
A splay tree is a BST which is not only self-adjusting, but also adaptive. Frequently accessed items are brought closer to the root, so their access becomes cheaper.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 17 / 1
2–3 Trees
2–3 trees and 2–3–4 trees are search trees that allow more than one item to be stored in a tree node.
A node that holds a single item has two children (or none, if it is a leaf ).
A node that holds two items (a so-called 3-node) has three children (or none, if it is a leaf).
And for 2–3–4 trees, a node that holds three items (a 4-node) has four children (or none, if it is a leaf).
This allows for a simple way of keeping search trees perfectly balanced.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 18 / 1
2-Nodes and 3-Nodes
2-node 3-node
n m,n
smaller than n
greater than n
smaller than m
between greater m and n than n
…………… . …. …………….. …
Algorithms and Complexity
(Sem 2, 2021)
Balanced Trees
© University of Melbourne 19 / 1
Insertion in a 2–3 Tree
To insert a key k, pretend that we are searching for k.
This will take us to a leaf node in the tree, where k should now be inserted; if the node we find there is a 2-node, k can be inserted without further ado.
Otherwise we had a 3-node, and the two inhabitants, together with k, momentarily form a node with three elements; in sorted order, call them k1, k2, and k3.
We now split the node, so that k1 and k3 form their own individual 2-nodes. The middle key, k2 is promoted to the parent node.
The promotion may cause the parent node to overflow, in which case it gets split the same way. The only time the tree’s height changes is
when the root overflows.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 20 / 1
Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Balanced Trees © University of Melbourne 21 / 1
Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
88
9 ⇒ 5,9 ⇒ 5,8,9 ⇒ 5 9 ⇒ 3,5 9 ⇒
8 ⇒ 3,8 ⇒ 3,8 ⇒
2,3,5 9
2 5 9 2 4,5 9
3,8
2 4,5,7 9
⇒ 3,5,8
2 4 7 9
⇒
5
38
2 4 7 9
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021)
Balanced Trees
© University of Melbourne 22 / 1
Exercise: 2–3 Tree Construction
Build the 2–3 tree that results from inserting these keys, in the given order, into an initially empty tree:
C, O, M, P, U, T, I, N, G (Hint: C