Each node of a Binary Search Tree (BST) stores a piece of data.
Part of that data is the key by which the BST is organized.
Each node in the BST has below it a left subtree and a right
subtree. The topmost node is called the root and a node
with no subtrees is called a leaf.
The most important property of a BST is:
For a node, x, with key, k, every key in x's left
subtree is less than or equal to k, and every key in x's right subtree
is greater than or equal to k.
Note that the definition permits duplicate keys. Some BSTs don't
permit duplicate keys. Whether to permit duplicate keys depends upon
the application that uses the BST.
Example
In the tree below, the root contains key 35, every key in the left
subtree of the root is less than 35 (these are 11, 20, and 29), and
every key in the right subtree is greater than 35 (these are 40, 43,
47, 50, 60, 65, and 72).
This property is true of every node in the tree. For
example, the node containing key 50 has 40, 43, and 47 in its left
subtree, and has 60, 65, and 72 in its right subtree.
Tree Walks
To "touch" every tree node in order from least to greatest in a tree rooted at x:
InorderWalk(x)
if x != NULL
InorderWalk( left(x) )
print key(x)
InorderWalk( right(x) )
Tree Search
To find the node containing a key, k, in a tree rooted at x:
Search(x,k)
if x == NULL
return NULL
else if k == key(x)
return x
else if k < key(x)
return Search( left(x) )
else
return Search( right(x) )
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, or red if it wasn't successful.
Minimum / Maximum
To find the minimum key in a tree rooted at x:
Minimum(x)
while left(x) != NULL
x = left(x)
return key(x)
Similarly, the maximum key is found in the rightmost node.
Successor / Predecessor
The successor of a node, x, is the node, y, that has the smallest
key greater than that of x.
The predecessor is the node that has the largest key smaller
than that of x.
Where's is x's successor?
- If x has a right subtree, succ( x ) is the leftmost element in that subtree.
- If x has no right subtree, succ( x ) is the lowest ancestor of x (above x
on the path to the root) that has x in its left subtree.
Succ(x)
if right(x) != NULL
return Minimum( right(x) )
else
y = parent(x)
while y != NULL and x == right(y)
x = parent(x)
y = parent(y)
return y
[ CLR 13.3 ]
Inutition: Move the element down through the tree, as though
searching for it, until we find an empty space (below a leaf).
Insert(x,T)
if T == NULL
T = makeNode(x) // Create a singleton tree
else
p = T
while p != NULL // Search for leaf
q = p
if key(x) == key(p) // ignore duplicate insertions
return
else if key(x) > key(p)
p = right(p)
else
p = left(p)
if key(x) > key(q) // q points to leaf
right(q) = makeNode(x)
else
left(q) = makeNode(x)
There's also a recursive version of insertion. Note that
Insert ignores duplicates; it could be modified to
maintain duplicates.
[ CLR 13.3 ]
Inutition: Get a pointer to the node first, then delete it:
Delete(k)
x = Search(k)
DeleteNode(x)
So how does DeleteNode work? There are several case
to consider when deleting node x:
DeleteNode(x)
execute one of the following three cases:
- x is a leaf.
In this case, point the parent to NULL:
if x == left(parent(x))
left(parent(x)) = NULL
else
right(parent(x)) = NULL
- x has one child, y.
In this case, point x's parent to x's child:
parent(y) = parent(x)
if x == left(parent(x))
left(parent(x)) = y
else
right(parent(x)) = y
- x has two children.
In this case, replace x's data with the successor's data and delete
the successor:
s = Succ(x)
data(x) = data(s)
DeleteNode(s)