|
A binary search tree is a binary tree with the following property.
If a given node v has item k, then all nodes in the left subtree of v have items that are less than k, and all nodes in the right subtree of v have items that are greater than k.For example, the following is a binary search tree.
30
/ \
/ \
18 50
/ \ / \
5 24 36 51
A binary search tree can have any shape, as long as
it obeys the ordering requirement. The following
is a binary search tree.
10
\
\
20
\
\
30
(The left subtree of each node is an empty tree.)
Our intent is to use a binary search tree as an implementation of a set of integers, namely, the set of integers that occur in the tree. An empty tree represents an empty set.
Functions can take advantage of the ordering requirement in a way that is similar to what binary search does. The membership testing function can be defined as follows, using the following facts.
An empty tree has no members.
If the root of T contains x, then tree T clearly contains x.
If the root of T contains k and x < k then, if x occurs in T at all, it must occur in T's left subtree, by the ordering requirement for binary search trees. After all, everything in T's right subtree is larger than k, and k is larger than x.
Similarly, if the root of T contains k and x > k, then x occurs in T if and only if x occurs in T's right subtree.
//==========================================
// member
//==========================================
// member(x,T) returns true if x is in binary
// search tree T.
//==========================================
bool member(int x, const Tree T)
{
if(T == NULL)
{
return false;
}
else if(x == T->item)
{
return true;
}
else if(x < T->item)
{
return member(x, T->left);
}
else
{
return member(x, T->right);
}
}
Notice that the two recursive calls to member use tail-recursion, which an optimizing compiler can turn into a loop. If you prefer to write a loop yourself, the following works.
//==========================================
// member
//==========================================
// member(x,T) returns true if x is in binary
// search tree T.
//==========================================
bool member(int x, const Tree T)
{
const Tree sub = T;
while(sub != NULL)
{
if(x == T->item)
{
return true;
}
else if(x < T->item)
{
sub = sub->left;
}
else
{
sub = sub->right;
}
}
return false;
}
Not surprisingly, this is a search algorithm. It stops when it finds what it is looking for or when it has exhausted the candidates.
To insert a value, just find where that value would have been, had it already been in the tree, then add the value as a new leaf. For example, inserting 13 as shown below would result in the following change.
10 10
/ \ / \
/ \ insert 13 / \
5 15 ------------> 5 15
/ / \ / / \
/ / \ / / \
2 12 20 2 12 20
\
\
13
The actual insertion takes place when a null tree is
encountered. The null tree is replaced by a leaf. If the
value to be inserted is already in the tree, nothing is done.
//==========================================
// insert
//==========================================
// insert(x,T) inserts x into binary search tree T.
// If x is already a member of T, it does nothing.
//==========================================
void insert(int x, Tree& T)
{
if(T == NULL)
{
T = new Node(x, NULL, NULL);
}
else if(x < T->item)
{
insert(x, T->left);
}
else if(x > T->item)
{
insert(x, T->right);
}
}
Notice that parameter T is passed by reference.
The first case needs to change the pointer that is stored
in T. Also notice that there is no case for
x = T->item since insert is not supposed to do anything
when x already occurs in the tree.
If x occurs at the root of T and one of the subtrees of the root is empty, then removing x is easy. Just replace the tree by the one that is not empty.
10 15
\ / \
\ remove 10 / \
15 ------------> 12 20
/ \
/ \
12 20
The same idea works even if both subtrees are empty.
After finding that the left subtree is empty, replace T
by its right subtree, whether that is empty or not. Also,
a similar idea works even when the value to be removed is not
at the root, as long as at least one of its subtrees is empty.
For example, here is how to remove a value from a subtree, where
the left subtree of that subtree is empty.
7 7
/ \ / \
/ \ / \
4 10 4 15
\ / \
\ remove 10 / \
15 ------------> 12 20
/ \
/ \
12 20
Removing a value where both subtrees are nonempty is
more involved. First, we remove the smallest value s from the
right subtree, then replace the value that is supposed to removed
by s.
10 12
/ \ / \
/ \ remove 10 / \
5 15 ------------> 5 15
/ / \ / \
/ / \ / \
2 12 20 2 20
Removing the smallest value is a matter of going to the
left as far as possible. Then remove the node that is
found there, replacing it by its right subtree. Here is
an example.
20 20
/ \ remove smallest / \
/ \ ------------------> / \
10 30 15 30
\ / \ / \ / \
15 25 35 12 15 25 35
/ \
12 16
Here are definitions of remove and removeSmallest.
//====================================================
// removeSmallest
//====================================================
// removeSmallest(T) removes the smallest value from
// binary search tree T and returns the value that
// was removed.
//
// Requirement: T must not be an empty tree.
//====================================================
int removeSmallest(Tree& T)
{
if(T->left == NULL)
{
int result = T->item;
Tree p = T;
T = T->right;
delete p;
return result;
}
else
{
return removeSmallest(T->left);
}
}
//====================================================
// remove
//====================================================
// remove(x,T) removes x from binary search tree T.
// If x is not in T, it does nothing.
//====================================================
void remove(int x, Tree& T)
{
if(T != NULL)
{
if(x < T->item)
{
remove(x, T->left);
}
else if(x > T->item)
{
remove(x, T->right);
}
else if(T->left == NULL)
{
Tree p = T;
T = T->right;
delete p;
}
else if(T->right == NULL)
{
Tree p = T;
T = T->left;
delete p;
}
else {
T->item = removeSmallest(T->right);
}
}
}
What tree do you get if you insert 25 into the following binary search tree?
10
/ \
/ \
5 15
/ / \
/ / \
2 12 20
Answer
What tree do you get if you insert 7 into the following binary search tree?
10
/ \
/ \
5 15
/ / \
/ / \
2 12 20
Answer
What tree do you get if you insert 11 into the following binary search tree?
10
/ \
/ \
5 15
/ / \
/ / \
2 12 20
Answer
What tree do you get if your remove 5 from the following binary search tree, using the algorithm described above?
10
/ \
/ \
5 15
/ / \
/ / \
2 12 20
Answer
What tree do you get if you remove 15 from the following binary search tree, using the algorithm described above?
10
/ \
/ \
5 15
/ / \
/ / \
2 12 20
Answer
What tree do you get if you remove 10 from the following binary search tree, using the algorithm described above?
10
/ \
/ \
/ \
5 20
/ \ / \
/ \ / \
2 8 14 26
/ \
/ \
/ \
11 18
\ / \
\ / \
13 15 19
/
/
12
Answer
|