CSC 378 tutorial: Searching in a BST
To search for a key k in a BST, we start at the root node:
- If k is less than the root's key, we descend to
the left.
- If k is greater than the root's key, we descend to
the right.
Then we repeat the procedure from our new location and continue to
descend through the tree. We finally stop when either
- we find k in a node, or
- we can't go down any farther, in which case k is not
in the tree.
Example
To search in this BST, type a number in the box and press ``Enter''.
The nodes are highlighted as they are inspected during the search.
The last node traversed is coloured green if the search was successful
and red if it was not successful. Of course, a computer program would
be much, much faster than this example.
Balanced trees
Note that, in the worst case, a search will follow the longest path
from the root to a leaf. A tree is balanced if all
root-to-leaf paths are short. Balanced trees are usually short and
wide. We'll see balanced trees in the discussion on rotations.
Click here to return to rotations.