Computer Programming

Computer Programming 2
College of Science and Engineering
BST
The ubiquitous Binary Search Tree
Flinders University / Computer Programming 2
Binary Search Tree
2
23
? ?
? ? ?
? ?
23 13 42 27 17 4 14 33
Flinders University / Computer Programming 2
Binary Search Tree
3
23
13 42
4 17 27
14 33
smaller values larger values
Flinders University / Computer Programming 2
Root rotation
4
B
small mid large
A
small mid large
? rotation
? rotation
A B
Flinders University / Computer Programming 2
Root rotation
5
B
A
small mid large
B
A
small mid large
right rotation
left rotation
Flinders University / Computer Programming 2
Min and max?
6
5
5
9
9
2
1 4 7 2
3 6 8 4 7
3
6
1
8

Flinders University / Computer Programming 2
Min and max
7
5
5
9
9
2
1 4 7 2
3 6 8 4 7
3
6
1
8
Flinders University / Computer Programming 2
Min and max of BST
8
TreeNode* min(TreeNode* root) {
if (root == 0) {
return 0;
} else if (root->left == 0) {
return root;
} else {
return min(root->left);
}
}
TreeNode* max(TreeNode* root) {
if (root == 0) {
return 0;
} else if (root->right == 0) {
return root;
} else {
return max(root->right);
}
}
Flinders University / Computer Programming 2
Min and max of BST
9
TreeNode* min(TreeNode* root) {
if (root == 0) {
return 0;
// nullptr
} else if (root->left == 0) {
return root;
} else {
return min(root->left);
}
}
TreeNode* max(TreeNode* root) {
if (root == 0) {
return 0;
} else if (root->right == 0) {
return root;
} else {
return max(root->right);
}
}
Follow left branches to the end
Follow right branches to the end
Flinders University / Computer Programming 2
Rotate min to root
10
5
9
2
4
7
1
6
3
8
5
9
2
4
7
1
6
3
8
5
9
2
4
7
1
6
3
8

Flinders University / Computer Programming 2
Rotate max to root
11
5
9
2
4
7
1
6
3
8
?
Flinders University / Computer Programming 2
Rotate max to root
12
5
9
2
4
7
1
6
3
8
5
9
2
4 7
1
3 6 8
?
Flinders University / Computer Programming 2
Rotate max to root
13
5
9
2
4
7
1
6
3
8
5
9
2
4 7
1
3 6 8
9 5
2
4 7
1
3 6 8
Flinders University / Computer Programming 2
TreeNode* minRoot(TreeNode* root) {
if (root == 0) {
return 0;
} else if (root->left == 0) {
return root;
} else {
root->left = min
Root(root->left);
return rotateRight(root);
}
}
TreeNode* max
Root(TreeNode* root) {
if (root == 0) {
return 0;
} else if (root->right == 0) {
return root;
} else {
root->right = max
Root(root->right);
return rotateLeft(root);
}
}
Rotate min or max to root
14
Flinders University / Computer Programming 2
TreeNode* minRoot(TreeNode* root) {
if (root == 0) {
return 0;
} else if (root->left == 0) {
return root;
} else {
root->left = min
Root(root->left);
return rotateRight(root);
}
}
TreeNode* max
Root(TreeNode* root) {
if (root == 0) {
return 0;
} else if (root->right == 0) {
return root;
} else {
root->right = max
Root(root->right);
return rotateLeft(root);
}
}
Rotate min or max to root
15
Flinders University / Computer Programming 2
Joining non-overlapping BST (on the right)
16
5
2 9
4
1 7
3 6 8 15
19
12
14 17
16
11
13
18
left right
Flinders University / Computer Programming 2
Join on the right
17
5
2 9
4
1 7
3 6 8 15
19
12
14 17
16
11
13
18
left right
Flinders University / Computer Programming 2
Join on the right
18
15
19
12
14 17
16
11
13
18
15
19
12
14 17
16
11
13
18
RotateMin
5
2 9
4
1 7
3 6 8
left right
Flinders University / Computer Programming 2
Join on the right
19
5
2 9
4
7
1
3 6 8
joined tree
15
19
12
14 17
16
11
13
18
Flinders University / Computer Programming 2
TreeNode* joinR(TreeNode* left, TreeNode* right) {
if (right == 0) {
return left;
} else {
right = rotateMin(right);
right->left = left;
return right;
}
}
Joining non-overlapping BSTs
20
Get the smallest right node to the top
And attach the left to its empty left branch

Flinders University / Computer Programming 2
TreeNode* joinR(TreeNode* left, TreeNode* right) {
if (right == 0) {
return left;
} else {
right =
minRoot(right);
right->left = left;
return right;
}
}
TreeNode* joinL(TreeNode* left, TreeNode* right) {
if (left == 0) {
return right;
} else {
left =
maxRoot(left);
left->right = right;
return left;
}
}
Joining non-overlapping BSTs
21
Get the smallest right node to the top
And attach the left to its empty left branch
Flinders University / Computer Programming 2
Removing from a BST (on the right)
22
5
2 9
4
7
1
3 6 8
15
19
12
14 17
16
11
13
18
5
2 9
4
7
1
3 6 8
15
19
12
14 17
16
13
18

Flinders University / Computer Programming 2
Remove on the right
23
5
2 9
4
7
1
3 6 8
15
19
12
14 17
16
11
13
18
Rotate smallest right node to top
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
11
13
18
Flinders University / Computer Programming 2
Remove on the right
24
5
2 9
4
7
1
3 6 8
15
19
12
14 17
16
11
13
18
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
11
13
18
Join left to empty rightleft
Flinders University / Computer Programming 2
Remove on the right
25
5
2 9
4
7
1
3 6 8
15
19
12
14 17
16
11
13
18
Delete the node
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
Flinders University / Computer Programming 2
TreeNode* removeR(TreeNode* root, int value) {
if (root == 0) {
return 0;
} else if (value < root->value) {
root->left = removeR(root->left, value);
} else if (value > root->value) {
root->right = removeR(root->right, value);
} else {
Node* n = root;
root = joinR(root->left, root->right);
delete n;
}
return root;
}
Removing from a BST
26
Node to remove is root
Flinders University / Computer Programming 2
TreeNode* removeR(TreeNode* root, int value) {
if (root == 0) {
return 0;
} else if (value < root->value) {
root->left = removeR(root->left, value);
} else if (value > root->value) {
root->right = removeR(root->right, value);
} else {
Node* n = root;
root =
joinR(root->left, root->right);
delete n;
}
return root;
}
TreeNode* removeL(…) {

… = joinL(…);

}
Removing from a BST
27
Left and right subtrees are non-overlapping
Node to remove is root
Delete the root
Computer Programming 2
College of Science and Engineering
Balanced Trees
Striving for optimal performance
Flinders University / Computer Programming 2
Keeping the tree balanced
29
•Balance is important!
•Balanced: as good as O(log n)
•Unbalanced: as bad as O(n)
•Maintaining balance
•While building the tree: avoid bad cases
•When needed: transform to reduce imbalance
•During use: self-balancing trees
A tree of 1,000,000 nodes:
balanced: depth = 20
unbalanced: depth = 1,000,000
Flinders University / Computer Programming 2
‘Pseudo’ balance
•Imbalance arises from ‘bad’ sequences
•ordered, reverse, alternating, repeated
•Random is (usually) fine
•On average, no more than twice optimum depth
•No guarantee, but a very good chance!
•Randomise the sequence
•Explicitly: shuffle the list — impractical, expensive, does not work for repeats
•Implicitly: insert in ‘random’ place
30
Flinders University / Computer Programming 2
Node* insertRandomised(Node* root, int value) {
if (root == 0 ||
rand() % (size(root) + 1) == 0) {
root = insertRoot(root, value);
} else if (value < root->value) {
root->left = insertRandomised(root->left, value);
} else {
root->right = insertRandomised(root->right, value);
}
return root;
}
Randomised insert
31
•Need to know size of (sub)trees
•Compute as needed? — expensive (in time)
•Cost of random number generator?
•Does not need to be very good
A 1-in-(n+1) chance…
…of inserting it
here as the root
Otherwise, go
elsewhere: left/right branch
n = number of nodes
Flinders University / Computer Programming 2
int size(Node* root) {
if (root == 0) {
return 0;
} else {
return 1 + size(root->left) + size(root->right);
}
}
int depth(Node* root) {
if (root == 0) {
return 0;
} else {
return 1 + max(depth(root->left), depth(root->right));
}
}
Computing tree attributes
32
•Expensive
•Not practical if needed frequently
Cost is O(n)
Flinders University / Computer Programming 2
struct Node {
int value;
int size; // number of nodes in this (sub)tree
TreeNode* left;
TreeNode* right;
};
Node* insert(Node* root, int value) {
if (root == 0) {
root = new Node;
root->value = value;
root->size = 1;
} else if (value < root->value) {
root->left = insert(root->left, value);
root->size += 1;
} else if (value >= root->value) {
root->right = insert(root->right, value);
root->size += 1;
}
return root;
}
int size(Node* root) {
return root == 0 ? 0 : root->size;
}
Adding a size attribute
33
Cost is O(1)
Trade space for time
Flinders University / Computer Programming 2
struct Node {
int value;
int depth; // of deepest node in this tree
TreeNode* left;
TreeNode* right;
};
Node* insert(Node* root, int value) {
if (root == 0) {
root = new Node;
root->value = value;
} else if (value < root->value) {
root->left = insert(root->left, value);
} else if (value >= root->value) {
root->right = insert(root->right, value);
}
return root;
}
int depth(Node* root) {
return root == 0 ? 0 : root->depth;
}
Adding a depth attribute
34
Trade space for time
Flinders University / Computer Programming 2
struct Node {
int value;
int depth; // of deepest node in this tree
TreeNode* left;
TreeNode* right;
};
Node* insert(Node* root, int value) {
if (root == 0) {
root = new Node;
root->value = value;
root->depth = 1;
} else if (value < root->value) {
root->left = insert(root->left, value);
root->depth = 1 + max(depth(root->left), depth(root->right));
} else if (value >= root->value) {
root->right = insert(root->right, value);
root->depth = 1 + max(depth(root->left), depth(root->right));
}
return root;
}
int depth(Node* root) {
return root == 0 ? 0 : root->depth;
}
Adding a depth attribute
35
Trade space for time
Flinders University / Computer Programming 2
AVL trees
•Adelson-Velskii and Landis (1962)
•The first and best-known — still one of the best
•Height-balanced tree (or depth-balanced)
•Difference in height between left and right branches must be <= 1
•After every insertion and deletion…
•Rebalance (using rotations) to keep depth of left/right within 1
•Depth will be (very) close to optimum
•Small (and fixed) cost on every insert and remove
•Guarantees O(log n) cost for insert, remove, and search
36
Flinders University / Computer Programming 2
AVL trees
37
13
13, 4, 23, 42, 19, 59
0 0
Flinders University / Computer Programming 2
AVL trees
38
13
13, 4, 23, 42, 19, 59
1 0
4
0 0
Balanced
Difference between left and right <= 1
Flinders University / Computer Programming 2
AVL trees
39
13
13, 4, 23, 42, 19, 59
1 1
4
0 0
23
0 0
Balanced
Difference between left and right <= 1
Flinders University / Computer Programming 2
AVL trees
40
13
13, 4, 23, 42, 19, 59
1 2
4
0 0
23
0 1
42
0 0
Balanced
Difference between left and right <= 1
Flinders University / Computer Programming 2
AVL trees
41
13
13, 4, 23, 42, 19, 59
1 2
4
0 0
23
1 1
42
0 0
19
0 0
Balanced
Difference between left and right <= 1
Flinders University / Computer Programming 2
AVL trees
42
13
13, 4, 23, 42, 19, 59
1 3
4
0 0
23
1 2
42
0 1
19
0 0
Unbalanced
Difference between left and right > 1
59
0 0
Difference > 1
Flinders University / Computer Programming 2
AVL trees: rebalancing
43
13
13, 4, 23, 42, 19, 59
1 3
4
0 0
23
1 2
42
0 1
19
0 0
59
0 0
Left rotate
•If left is too deep
•Rotate to the right
•If right is too deep
•Rotate to the left
Flinders University / Computer Programming 2
AVL trees: rebalancing
44
•If left is too deep 13, 4, 23, 42, 19, 59
•Rotate to the right
•If right is too deep
•Rotate to the left
42
23
59
13
1 1
2
0 0
19
0
4
Rebalanced
Difference between left and right <= 1
2
0 0 0
1 0

Flinders University / Computer Programming 2
AVL trees: rebalancing (oops!)
45
0
42
23
21
13
2 0
1
0
19
1
4
23
13
42
4
0 1
3
0
21
0
19
1
1 3
Still unbalanced!
0 2
0
0
0
1
0 0
0
0
Flinders University / Computer Programming 2
AVL trees: rebalancing
46
23
13
42
4
1
3
21
19
1
19
13
23
4
2
1
3
1
21 42
19
13 23
4
2
1 1
21
1
42
Inner branch is deeper
Perform a pre-rotate…
•Every time you make a change to the tree…
•For each node changed to the root node: if branch depths differ by more than 1:
•Maybe pre-rotate? If inner subbranch is deeper, rotate outwards
•Rotate away from deep side so out-of-balance subtree is on the ‘outside’
2
1 1 2

Flinders University / Computer Programming 2
Node* rebalanceAVL(Node* root) {
if (root == 0) {
return 0;
} else {
if (
depth(root->right) – depth(root->left) > 1) {
if (depth(root->right->left) > depth(root->right->right)) {
root->right =
rotateRight(root->right);
}
root = rotateLeft(root);
} else if (
depth(root->left) – depth(root->right) > 1) {
if (depth(root->left->right) > depth(root->left->left)) {
root->left =
rotateLeft(root->left);
}
root = rotateRight(root);
}
return root;
}
}
AVL rebalancing
47
Right too heavy, rotate left
pre-rotate:
inner branch heavy, rotate right
Left too heavy, rotate right
pre-rotate:
inner branch heavy, rotate left
Flinders University / Computer Programming 2
BST animations
48
•Basic BST and several self-balancing variants
•https://people.ksp.sk/~kuko/gnarley-trees/
•Visualisations
•https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
•BST Visualiser
•http://www.btv.melezinek.cz/binary-search-tree.html
•Good for understanding rotation (Java applet)
•http://research.cs.queensu.ca/~jstewart/applets/bst/bst-rotation.html
Computer Programming 2
College of Science and Engineering
Tree Manipulations
Practice makes perfect!
Flinders University / Computer Programming 2
Joining non-overlapping BST (on the left)
50
5
2 9
4
1 7
3 6 8 15
19
12
14 17
16
11
13
18
left right
Flinders University / Computer Programming 2
Join on the left
51
5
2 9
4
1 7
3 6 8 15
19
12
14 17
16
11
13
18
left right
RotateMax
5
9
2
4
7
1
6
3
8
Flinders University / Computer Programming 2
5
9
2
4
7
1
6
3
8
Join on the left
52
15
19
12
14 17
16
11
13
18
joined tree
Flinders University / Computer Programming 2
TreeNode* joinL(TreeNode* left, TreeNode* right) {
if (left == 0) {
return right;
} else {
left = rotateMax(left);
left->right = right;
return left;
}
}
Joining non-overlapping BSTs
53
Get the largest left node to the top
And attach the right to its empty right branch
Flinders University / Computer Programming 2
Delete the highlighted node
54
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
?
remove on the right
Flinders University / Computer Programming 2
Delete the highlighted node
55
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
remove on the right
Flinders University / Computer Programming 2
Delete the highlighted node
56
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
join on the left

Flinders University / Computer Programming 2
Delete the highlighted node
57
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
?
remove on the left
Flinders University / Computer Programming 2
Delete the highlighted node
58
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
remove on the left
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18

Flinders University / Computer Programming 2
Delete the highlighted node
59
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
remove on the left
5
9
2
4
1 7
6
3
8
15
19
12
14
17
16
13
18
Flinders University / Computer Programming 2
Delete the highlighted node
60
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
remove on the left
5
9
2
4
1 7
6
3
8
15
19
12
14
17
16
13
18

Flinders University / Computer Programming 2
Delete the highlighted node
61
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
remove on the left
5
9
2
4
1 7
6
3
8
15
19
12
14
17
16
13
18
Flinders University / Computer Programming 2
Delete the highlighted node
62
5
9
2
4
1 7
6
3
8
15
19
12
14 17
16
13
18
join on the left
5
9
2
4
1 7
6
3
8
15
19
12
14
17
16
13

Flinders University / Computer Programming 2
Delete root (removeR) and rebalance
63
13 23
4
17
14
1
1
?
2
1
Flinders University / Computer Programming 2
Delete root and rebalance
64
13 23
4
17
14
1
1 1
23
13
4
17
14
2 1
1 1
23
13
4 14
2
1
?
unbalanced
0
2
1
removeR
Flinders University / Computer Programming 2
Delete root and rebalance
65
23
13
4 14
0
1 1
23
13
4 14
1
2
removeR
rebalanceAVL
13 23
4
17
14
1
1 1
23
13
4
17
14
2 1
1 1
23
13
4 14
2
1
0
2
1
2
1
Flinders University / Computer Programming 2
Insert 17 and rebalance
66
23
13
4
14
?
Flinders University / Computer Programming 2
Insert 17 and rebalance
67
23
13
4
14
23
13
4
14
17
23
13
4
14
17
23
13
4
14
17
new node
balanced
unbalanced
pre-rotate needed
Flinders University / Computer Programming 2
Insert 17 and rebalance
68
23
13
4
14
23
13
4
14
17
23
13
4
14
17
23
13
4
14
17
23
13
4
14
17
23
13
4
14
17
new node
balanced
unbalanced
pre-rotate needed
balanced
after pre-rotate