The following algorithm traverses a binary tree to find a node with a given key. This traversal can be used both in the insertion and in the seraching function.
1 function bintree_search (root: node_type; key: key_type) return node_type 2 is 3 node_pointer: node_type; 4 5 function max_height_binary (N: natural) return natural 6 is 7 begin 8 return N; 9 end max_height_binary; 10 11 begin 12 discrete node_pointer := root 13 new node_pointer := node_pointer.left | node_pointer.right 14 with h := max_height_binary (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 bintree_search;
[ Sourcefile ]
The original implementation in traditional high-level-languages like Pascal or C uses a repeat (or while) construct, which we replaced by a discrete loop with a remainder function.
The remainder function variable is initialized with the maximum height of the tree (line 14) and decremented by 1 (line 16) for every node traversed. We had to add 1 to the maximum height for the case of an empty binary tree (root = NULL).
The defining property of a binary tree is that for each node all nodes with smaller keys are in the left subtree and all nodes in the right subtree have larger (or equal) keys.
The following binary tree is built by inserting 4 nodes in reverse order refering to their keys (i.e., 4 - 3 - 2 - 1).
In this instance, to find the node with key 1, every node has to be traversed and the traversal degrades to a linear traversal with N comparisons in the worst case!
[Meh84, p. 152] [Ott93, p. 275] [Sed88, p. 37] [Wyk88, p. 164]
[ Samples Overview | Bibliography | WOOP Project ]