The following algorithm traverses an AVL tree to find a node with a given key. The AVL tree is the oldest and most well-known data structure for balanced trees, which has the property that the heights of the two subtrees of each node differ by at most one.
This traversal can be used both in the insertion and in the searching function. By inserting a new node, the AVL condition can be violated, in which case we have to fix the heights of some nodes using rotations. These rotations are not implemented in the code fragment below because they would not make use of discrete loops.
1 function avl_search (root: node_type; key: key_type) return node_type 2 is 3 node_pointer: node_type; 4 5 function max_height_avl (N: natural) return natural 6 is 7 begin 8 return floor (1.44 * ld (N)) + 1; 9 end max_height_avl; 10 11 begin 12 discrete node_pointer := root 13 new node_pointer := node_pointer.left | node_pointer.right 14 with h := max_height_avl (N) + 1 15 -- for null-case 16 new h = h - 1 17 loop 18 if node_pointer = NULL then 19 return NULL; 20 elsif key (node_pointer) = key_to_search then 21 return node_pointer; 22 elsif key (node_pointer) < key_to_search then 23 node_pointer := node_pointer.left; 24 else 25 node_pointer := node_pointer.right; 26 end if; 27 end loop; 28 end avl_search;
The implementation is nearly identical to the (natural) binary tree with the exception that the remainder function is bound by a lower value (implicated by the strict AVL tree condition).
For a binary tree that fullfills the AVL condition, the following condition holds:
height <= 1.44 * ld (N) + 1.
This upper bound is used for the remainder function of the discrete loop (lines 8 and 14, respectively). As with the (natural) binary tree, we had to add 1 to support also empty trees, in wich case the loop body is executed exactly once.
The following figure shows minimal binary trees which fullfill the AVL condition for height 2, 3 and 4, respectively.
Because of the AVL condition, the trees keep balanced even in the case of inserting nodes with ascending or descending keys. We can again make use of the condition
height <= 1.44 * ld (N) + 1 where ld e = 1/(ln 2) = 1.44
which yields to predicted (worst case) executions of the loop body of our sample trees of 2 (N = 2), 3 (N = 4), and 5 (N = 7) respectively.
So only by imposing the AVL condition, we get
O( ld N )
for the worst case of searching an element in a binary tree, instead of O(N) without balancing condition.
[AHU83, p. 196] [Meh84, p. 309] [Ott93, p. 298] [Sed88, p. 229] [Wyk88, p. 195]
[ Samples Overview | Bibliography | WOOP Project ]