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.

1functionavl_search (root: node_type; key: key_type)returnnode_type2is3node_pointer: node_type;45functionmax_height_avl (N: natural)returnnatural6is7begin8returnfloor (1.44 * ld (N)) + 1;9endmax_height_avl;1011begin12discretenode_pointer := root13newnode_pointer := node_pointer.left | node_pointer.right14withh := max_height_avl (N) + 115-- for null-case16newh = h - 117loop18ifnode_pointer = NULLthen19returnNULL;20elsifkey (node_pointer) = key_to_searchthen21returnnode_pointer;22elsifkey (node_pointer) < key_to_searchthen23node_pointer := node_pointer.left;24else25node_pointer := node_pointer.right;26endif;27endloop;28endavl_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 ]