CE204
Data Structures and Algorithms
Part 8
08/03/2020 CE204 Part 8
1
Balancing Binary Search Trees 1
We saw in part 4 that the average times for binary search tree operations are O(log n), but in the worst case the times are O(n).
To obtain optimum performance we would like to ensure that binary search trees are always balanced. We cannot insist that trees will be perfectly balanced since such a tree must have an odd number of nodes (the root and two children each with the same number of nodes). Hence we use the following definition.
A binary tree is balanced if for every non-leaf node the number of nodes in its left child and the number of nodes in its right child differ by no more than one.
08/03/2020 CE204 Part 8
2
Balancing Binary Search Trees 2
It can be shown that the depth of a balanced binary tree containing n nodes is exactly floor(log2n)+1 (where floor(x) is the largest integer less than or equal to x).
If a binary search tree will be searched frequently but changed only occasionally, then ensuring that the tree remains balanced after each change would be worthwhile. However, if insertions and deletions will be performed frequently rebalancing would be cost-effective only if the rebalancing of a tree containing n items could be done in O(log n) time.
08/03/2020 CE204 Part 8
3
Balancing Binary Search Trees 3
Consider the following balanced binary search tree
3 15
246
08/03/2020 CE204 Part 8
4
Balancing Binary Search Trees 4
Suppose we wish to insert the value 7 into the tree on the previous slide and maintain the balanced property. There is only one possible balanced binary search tree containing the values 1, 2, 3, 4, 5, 6 and 7 (and no other values) and none of its elements are in the same position as in the original tree. Furthermore no value has the same parent in this tree as in the original. Hence to rebalance the tree after the insertion all of the elements have to be moved individually. Similar situations can arise with larger trees and consequently rebalancing takes at least O(n) time in the worst case. Hence it is not reasonable to maintain balanced trees if insertions and deletions are to be performed frequently.
08/03/2020 CE204 Part 8
5
AVL Trees 1
Although it is not cost-effective to ensure that binary search trees are always balanced, it is still desirable in many cases to ensure that they are reasonably well balanced. One way of doing this is to use the concept of being depth-balanced.
A binary tree is depth-balanced (or AVL-balanced) if for every non-leaf node the depth of its left child and the depth of its right child differ by no more than one.
It is not difficult to see that any balanced tree is AVL-balanced (using the depth property from slide 3), but the converse is not true.
It can be shown that the depth of any AVL-balanced tree containing n nodes is no more than 2log2n (as long as n>1).
08/03/2020 CE204 Part 8
6
AVL Trees 2
An AVL tree is a depth-balanced binary search tree. The use of such trees was first suggested by Adel¡¯son-Velskii and Landis in 1962. They showed that the rebalancing of an AVL tree after an insertion can be performed in constant time (that is, the time taken does not depend on the size of the tree) and that the rebalancing after a deletion can be performed in time proportional to the depth. Furthermore the time taken to determine whether rebalancing is needed is at most proportional to the depth, as long as a small amount of extra information is stored in each node.
Hence searching, insertion and deletion for AVL trees can all be performed in O(log n) time.
08/03/2020 CE204 Part 8
7
AVL Trees 3
We will consider only the rebalancing algorithm for insertion (the algorithm for deletion is similar). Hence we assume that the insertion of a value into a tree that was AVL-balanced has resulted in a tree that is no longer AVL-balanced.
The first step is to find the smallest sub-tree, A, whose children have depths differing by more than one (this is unique since its root must lie on the path from the root to the new leaf). A must have children of depth n and n+2 for some n; before the insertion the tree was AVL-balanced so the children must have had depths of n and n+1, so A¡¯s original depth was n+2.
08/03/2020 CE204 Part 8
8
AVL Trees 4
We now let B be A¡¯s deeper child. We assume that B is A¡¯s left child; if instead it is A¡¯s right child all references to left and right on subsequent slides need to be exchanged.
B has depth n+2 so one of its children must have depth n+1. The other child cannot also have depth n+1. (If it did, then B would have had depth n+2 before the insertion, which we know is not the case since B¡¯s parent, A, had an original depth of n+2). Since A is the smallest unbalanced sub-tree B must be AVL-balanced, so this other child cannot have depth less than n and hence must have depth n.
08/03/2020 CE204 Part 8
9
AVL Trees 5
There are two cases to consider, dependent upon which of B¡¯s children is the deeper:
Case 1: B¡¯s left child is deeper than B¡¯s right child
Case 2: B¡¯s right child is deeper than B¡¯s left child
The diagrams on the following slides show how the tree A is rebalanced in each of the two cases. (The nodes labelled a and b denote the roots of A and B respectively.)
Remember that we assumed that B (A¡¯s deeper child) is A¡¯s left child; if B is A¡¯s right child we need to reflect the trees in the diagrams to swap the roles of left and right.
08/03/2020 CE204 Part 8
10
Case 1:
AVL Trees 6
a
bT3 T1
b
a
T1 T2 T2
T3
08/03/2020
CE204 Part 8
11
AVL Trees 7
The depths of T2 and T3 are both n, and T2 and T3 must be AVL-balanced (since they are smaller than the smallest unbalanced sub-tree, A). Hence the right child of the new sub- tree is AVL-balanced and has depth n+1. The depth of T1 is also n+1 and T1 is AVL-balanced, so the whole sub-tree is also AVL-balanced. Furthermore it is easy to see that it is a binary search tree.
The depth of the new sub-tree is n+2 which is the same as the original depth of A so replacing A with the new sub-tree will preserve the AVL-balanced status of the rest of the tree and no further rebalancing needs to be performed.
08/03/2020 CE204 Part 8
12
AVL Trees 8
Case 2:
a b
c
c
T4 ba
T1
T1 T2 T3 T4
T2
T3
08/03/2020
CE204 Part 8
13
AVL Trees 9
Again it can be seen that the new sub-tree is a binary search tree, is AVL-balanced and has depth n+2, equal to the original depth of A.
The rebalancing in both cases can be performed by changing a small number of left and right child references and hence the time taken is independent of the size of the tree.
It is important to be able to detect the smallest unbalanced sub- tree without searching the whole tree. To enable this we need to store in each node additional information about depths and update this information after each insertion or deletion. The most efficient way of doing this is to simply store details of which, if either, child is the deeper.
08/03/2020 CE204 Part 8
14