COMP20007 Design of Algorithms
Binary Search Trees and their Extensions
Daniel Beck
Lecture 14
Semester 1, 2020
1
Dictionaries
2
Dictionaries
• Abstract Data Structure
2
Dictionaries
• Abstract Data Structure
• Collection of (key, value) pairs
2
Dictionaries
• Abstract Data Structure
• Collection of (key, value) pairs
• Values are usually records, such as my videogames or the Unimelb students.
2
Dictionaries
• Abstract Data Structure
• Collection of (key, value) pairs
• Values are usually records, such as my videogames or the Unimelb students.
• Keys are (unique) identifiers, such as the name of a game or the student ID.
2
Dictionaries
• Abstract Data Structure
• Collection of (key, value) pairs
• Values are usually records, such as my videogames or the Unimelb students.
• Keys are (unique) identifiers, such as the name of a game or the student ID.
• Required operations:
• Search for a value (given a key)
• Insert a new pair
• Delete an existent pair (given a key)
2
Dictionaries – Implementations
3
Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
3
Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
Sorted array
• Search: Θ(log n) comparisons;
3
Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
Sorted array
• Search: Θ(log n) comparisons;
• Insert/Delete: Θ(n) record swaps;
3
Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
Sorted array
• Search: Θ(log n) comparisons;
• Insert/Delete: Θ(n) record swaps; This lecture: a better data structure
3
Dictionaries – Implementations
Unsorted array / Linked list
• Search: Θ(n) comparisons;
Sorted array
• Search: Θ(log n) comparisons;
• Insert/Delete: Θ(n) record swaps; This lecture: a better data structure
• Search: Θ(log n) comparisons;
• Insert/Delete: Θ(log n) record swaps;
3
Binary Search Tree
10
5 20
3 7 12 25
4
Binary Search Tree – Worst Case
25 20
12 10
7 5
3
5
BST – How to avoid degeneracy?
Two options:
6
BST – How to avoid degeneracy?
Two options:
• Self-balancing
• AVL trees
• Red-black trees • Splay trees
6
BST – How to avoid degeneracy?
Two options:
• Self-balancing
• AVL trees
• Red-black trees • Splay trees
• Change the representation
• 2-3 trees • 2-3-4 trees • B-trees
6
AVL trees
7
AVL trees
• Named after Adelson-Velsky and Landis.
7
AVL trees
• Named after Adelson-Velsky and Landis.
• A BST where each node has a balance factor: the difference in height between the left and right subtrees.
7
AVL trees
• Named after Adelson-Velsky and Landis.
• A BST where each node has a balance factor: the difference in height between the left and right subtrees.
• When the balance factor becomes 2 or -2, rotate the tree to adjust them.
7
AVL Trees: Examples and Counter-Examples
Which of these are AVL trees? ✎
10 10 10
5 20 5 20 520
3 7 12 25 3 7 12 2108 2
5 20 3 7 25
24 8 29
3 7
8
AVL Trees – Rotations
• Search is done as in BSTs.
9
AVL Trees – Rotations
• Search is done as in BSTs.
• Insertion and Deletion also done as in BSTs, with additional steps at the end.
9
AVL Trees – Rotations
• Search is done as in BSTs.
• Insertion and Deletion also done as in BSTs, with additional steps at the end.
• Update balance factors.
• If the tree becomes unbalanced, perform rotations to
rebalance it.
9
AVL Trees: R-Rotation
2
3 1
2 0
1
10
AVL Trees: R-Rotation
20
32 1⇒00 213
0 1
10
AVL Trees: L-Rotation
-2 1
-1 2
0 3
11
AVL Trees: L-Rotation
-2 0 12
-1 ⇒0 0 213
0 3
11
AVL Trees: LR-Rotation
2
3 -1
1
0
2
12
AVL Trees: LR-Rotation
20
32
-1 ⇒0 0 113
0 2
12
AVL Trees: RL-Rotation
-2 1
1
3 0
2
13
AVL Trees: RL-Rotation
-2 0 12
1⇒00
313 0
2
13
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.
14
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.
15
�� ��
��
AVL Trees: The Double Rotation, Generally
2r 0g
-1 10 c-1 cr
g
T4
T1T2T3 T1 T4
⇒
T2 T3
This shows an LR-rotation; an RL-rotation is similar.
16
���� �
�
��
Properties of AVL Trees
• Rotations ensure that an AVL tree is always balanced.
17
Properties of AVL Trees
• Rotations ensure that an AVL tree is always balanced. • An AVL tree with n nodes has depth Θ(log n).
17
Properties of AVL Trees
• Rotations ensure that an AVL tree is always balanced. • An AVL tree with n nodes has depth Θ(log n).
• This ensures all three operations are Θ(log n).
17
Red-black Trees
• A red-black tree is another self-balancing BST. • Its nodes are coloured red or black, so that:
1. No red node has a red child.
2. Every path from the root to the leaves has the same number of black nodes.
12
9 15
6 10
A worst-case red-black tree (the longest path is twice as long as the shortest path).
4
18
Self-balancing trees – In practice
AVL trees vs. red-black trees
19
Self-balancing trees – In practice
AVL trees vs. red-black trees
• AVL trees are “more balanced” but require more frequent rotations.
• Better if searches are more frequent than insertions/deletions.
19
Self-balancing trees – In practice
AVL trees vs. red-black trees
• AVL trees are “more balanced” but require more frequent rotations.
• Better if searches are more frequent than insertions/deletions.
• Red-black trees are “less balanced” but require less rotations.
• Better if insertions/deletions are more frequent than searches.
19
Self-balancing trees – In practice
AVL trees vs. red-black trees
• AVL trees are “more balanced” but require more frequent rotations.
• Better if searches are more frequent than insertions/deletions.
• Red-black trees are “less balanced” but require less rotations.
• Better if insertions/deletions are more frequent than searches.
Key property: rotations keep trees in a shape that guarantees Θ(log n) operations.
19
Representational Changes
20
Representational Changes
• Goal is the same: keep the tree balanced.
20
Representational Changes
• Goal is the same: keep the tree balanced.
• But instead of relying on rotations, we will allow multiple elements per node and multiple children per node.
20
Representational Changes
• Goal is the same: keep the tree balanced.
• But instead of relying on rotations, we will allow multiple elements per node and multiple children per node.
• 2–3 trees: contains only 2-nodes and 3-nodes.
20
Representational Changes
• Goal is the same: keep the tree balanced.
• But instead of relying on rotations, we will allow multiple elements per node and multiple children per node.
• 2–3 trees: contains only 2-nodes and 3-nodes.
• A 2-node contains one element and at most two children (as in BSTs)
• A 3-node contains two elements and at most three children.
20
Representational Changes
• Goal is the same: keep the tree balanced.
• But instead of relying on rotations, we will allow multiple elements per node and multiple children per node.
• 2–3 trees: contains only 2-nodes and 3-nodes.
• A 2-node contains one element and at most two children (as in BSTs)
• A 3-node contains two elements and at most three children.
• Easy way to keep the tree balanced.
20
Representational Changes
• Goal is the same: keep the tree balanced.
• But instead of relying on rotations, we will allow multiple elements per node and multiple children per node.
• 2–3 trees: contains only 2-nodes and 3-nodes.
• A 2-node contains one element and at most two children (as in BSTs)
• A 3-node contains two elements and at most three children.
• Easy way to keep the tree balanced.
• Can be extended in many ways: 2–3–4 trees, B-trees, etc.
20
2-Nodes and 3-Nodes
21
2-Nodes and 3-Nodes
2-node
n
smaller than n
greater than n
21
��
2-Nodes and 3-Nodes
2-node 3-node
n m,n
smaller greater smaller between greater than n than n than m m and n than n
21
�����
Insertion in a 2–3 Tree
22
Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
22
Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
• If the leaf node is a 2-node, insert k, becoming a 3-node.
22
Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
• If the leaf node is a 2-node, insert k, becoming a 3-node. • Otherwise, momentarily form a node with three elements:
• In sorted order, call them k1, k2, and k3.
22
Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
• If the leaf node is a 2-node, insert k, becoming a 3-node. • Otherwise, momentarily form a node with three elements:
• In sorted order, call them k1, k2, and k3.
• Split the node, so that k1 and k3 form their own
individual 2-nodes, and k2 is promoted to the parent node.
22
Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
• If the leaf node is a 2-node, insert k, becoming a 3-node. • Otherwise, momentarily form a node with three elements:
• In sorted order, call them k1, k2, and k3.
• Split the node, so that k1 and k3 form their own
individual 2-nodes, and k2 is promoted to the parent
node.
• If the parent node was a 3-node, repeat.
22
Insertion in a 2–3 Tree
• As in a BST, pretend that we are searching for k.
• If the leaf node is a 2-node, insert k, becoming a 3-node. • Otherwise, momentarily form a node with three elements:
• In sorted order, call them k1, k2, and k3.
• Split the node, so that k1 and k3 form their own
individual 2-nodes, and k2 is promoted to the parent
node.
• If the parent node was a 3-node, repeat.
22
Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9
23
Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9 ⇒ 5,9
23
Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9 ⇒ 5,9 ⇒ 5,8,9
23
Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
8 9 ⇒ 5,9 ⇒ 5,8,9 ⇒
59
23
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
23
Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
9 ⇒ 5,9 ⇒ 5,8,9 ⇒ 8
88
⇒ ⇒
5 9 3,5 9
2,3,5
9
23
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
2,3,5 9 2 5 9
23
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
23
Example: Build a 2–3 Tree from 9, 5, 8, 3, 2, 4, 7
2
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
4,5,7 9
23
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 ⇒ 3,5,8
2 4,5,7 92 4 7 9
23
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
5
3,8 ⇒ 3,5,8 ⇒ 2 4,5,7 92 4 7 9
38 2479
23
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 ✎
24
Extensions
• 2–3–4 trees: includes 4-nodes.
25
Extensions
• 2–3–4 trees: includes 4-nodes.
• B-trees: a generalisation. (2–3 trees are B-trees of order 3)
25
Extensions
• 2–3–4 trees: includes 4-nodes.
• B-trees: a generalisation. (2–3 trees are B-trees of order 3)
• B+-trees: internal nodes only contain keys, values are all in the leaves (plus a bunch of optimisations)
25
Extensions
• 2–3–4 trees: includes 4-nodes.
• B-trees: a generalisation. (2–3 trees are B-trees of order 3)
• B+-trees: internal nodes only contain keys, values are all in the leaves (plus a bunch of optimisations)
Key property: balance is achieved by allowing multiple elements per node.
25