Page 132 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

Figure 6.8: A Binary Tree after Deletion of a Node Pointed to by x Notes

50

y
60
30
x 65
52

Nil
Nil Nil

Search for a key in a BST

To search the binary tree for a particular node, we use procedures similar to those we used when
adding to it. Beginning at the root node, the current node and the entered key are compared. If
the values are equal success is output. If the entered value is less than the value in the node, then
it must be in the left-child sub tree. If there is no left-child sub tree, the value is not in the tree i.e.
a failure is reported. If there is a left-child subtree, then it is examined the same way. Similarly,
it the entered value is greater than the value in the current node, the right child is. searched.
Figure 18 shows the path through the tree followed in the search for the key H.
Figure 6.9: Search for a Key In BST
E

G
B
F I
A D
H J

C

find-key (key value, node)
{
if (two values are same)
{
print value stored in node;
return (SUCCESS);
}
else if (key value value stored in current node)
{
if (left child exists)
{
find-key (key-value, left hand);
}

LOVELY PROFESSIONAL UNIVERSITY 127