CP2001 Data Structures and
Algorithms Balanced Search Trees Page 2 of 6 |
|
AVL Trees | Not in Book |
An AVL tree (also called an "admissible tree") is a tree in which the height of the left and right subtrees of every node differ by at most one - referred to as "height-balanced".
Example AVL trees:
3 6 5 / \ / \ / \ 2 5 4 7 2 9 / / \ / \ 3 1 4 7 12 / \ / \ 3 8 11 14 / 10Example non-AVL trees:
5 6 5 / / \ / \ 3 3 10 2 9 / / \ / / \ / \ 2 1 4 7 1 4 7 12 \ / / \ 8 3 11 14 / 10
In order to indicate the differences between the heights of the right and left subtrees of a given (root) node, a balance factor is defined for that node of the subtree.
We define the balance factor, BF:
BF = (height of right subtree - height of left subtree)
So, BF = -1, 0 or +1 for an AVL tree.
Balance factors for example AVL trees (node key values not shown):
0 -1 +1 / \ / \ / \ 0 0 -1 0 -1 -1 / / / \ 0 0 +1 0 \ 0
Balance factors for an example non-AVL tree (node key values not shown):
+1 / \ -1 -2 / / 0 +1 \ 0
When the AVL property is lost we can rebalance the tree via one of four rotations:
A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the left (the left subtree is 2 higher than the right subtree) and B is left-heavy (the left subtree of B is 1 higher than the right subtree of B). T1, T2 and T3 represent subtrees (a node was added to T1 which made B leftheavy and unbalanced A).
A SRR at A B / \ ----------> / \ B T3 T1 A / \ / \ T1 T2 T2 T3
A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the right (the right subtree is 2 higher than the left subtree) and B is right-heavy (the right subtree of B is 1 higher than the left subtree of B). T1, T2 and T3 represent subtrees (a node was added to T3 which made B right-heavy and unbalanced A).
A SLR at A B / \ ----------> / \ T1 B A T3 / \ / \ T2 T3 T1 T2
C is the node that the rotation is performed on. This rotation is performed when C is unbalanced to the left (the left subtree is 2 higher than the right subtree), A is right-heavy (the right subtree of A is 1 higher than the left subtree of A) and B is left-heavy. T1, T2, T3, and T4 represent subtrees (a node was added to T2 which made B left-heavy, made A right-heavy and unbalanced C). This consists of a single left rotation at node A, followed by a single right at node C.
C SLR at A C SRR at C B / \ ----------> / \ ---------> / \ A T4 B T4 A C / \ / \ / \ / \ T1 B A T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2
That is,
DLR = SLR + SRR
A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the right (the right subtree is 2 higher than the left subtree), C is leftheavy (the left subtree of A is 1 higher than the right subtree of A) and B is right-heavy. T1, T2, T3, and T4 represent subtrees (a node was added to T3 which made B right-heavy, made C left-heavy and unbalanced A). This consists of a single right at node C, followed by a single left at node A.
A SRR at C A SLR at A B / \ ----------> / \ ----------> / \ T1 C T1 B A C / \ / \ / \ / \ B T4 T2 C T1 T2 T3 T4 / \ / \ T2 T3 T3 T4That is,
DRR = SRR + SLR
Insertion in a AVL-tree
An AVL tree may become out of balance in two basic situations:
Insertion of a node in the right subtree of the right child:
This involves a SLR about node P:
Insertion of a node in the left subtree of the right child:
This involves a DRR:
In each case the tree is rebalanced locally (since there is no need to modify the balance factors higher in the tree).
Since rebalancing is local, insertion requires one single or one double
rotation, ie O(constant) for rebalancing.
Of course, there is still the cost
of search for insertion (see below).
Experiments have shown that 53% of insertions do not bring the tree out of balance.
Example: Given the following AVL tree, insert the node with value 9:
6 / \ 3 12 \ / \ 4 7 13 \ 10
Deletion in a AVL-tree
Not covered here.
It can be shown that deletion requires O(log N) rotations in the worst-case.
However, experiments show that 78% of deletions do not require rebalancing.
Implementation of an AVL tree and Rotation Algorithms
Each node of an AVL tree has to store a value for the balance factor.
We
can implement a AVL tree in C++:
Implementation of rotation algorithms will be covered in the tutorials.
Performance for Searching in an AVL tree
We can show that the maximum number of comparisons in an optimum shaped tree is:
C > 2 ceiling[log(N + 1)] + 1
The number of comparisons for a worst-case AVL tree is obtained by evaluating an AVL tree with the greatest possible height and minimum number of nodes.
This type of AVL tree is called a Fibonacci AVL trees.
The maximum number of comparisons in the deepest possible Fibonacci AVL tree is
C' = 2h + 1 < 2.88*log(N + 2) - 1.66That is, AVL searches can require no more than about 44% more comparisons than required in the most costly search of an optimum shaped AVL tree!
Also, much better than the O(N) worst-case result for a normal (non-AVL) binary search tree!
Copyright © 1998 Olivier de Vel and Curtis Dyreson. All rights reserved. |
|