****************************************************************
Labelled binary trees.
Recursive definition of a labelled binary tree: A labelled binary
tree is either
1. NIL; or
2. a node consisting of a label and two immediate subtrees t1
and t2, where t1 and t2 are binary search trees.
Labelled binary trees as an abstract data type: Let Z be a data
type that is totally ordered by < and =.
NIL: tree
MakeTree: Z x tree x tree -> tree
Nil?: tree -> boolean
Key: tree -> Z
Left: tree -> tree
Right: tree -> tree
I am aware that Nil? is not a legal identifier in Pascal, C, or
C++, but I will use it as if it were.
****************************************************************
Binary search trees.
Persistent dynamic sets.
A binary search tree has an additional operation for obtaining
the parent of a node. This operation is seldom needed. (If it
were needed, we could define a data type of binary search trees
using the data type of labelled binary trees.) Most of the operations
on binary search trees can be defined on labelled binary trees
that satisfy the binary-search-tree property.
The binary-search-tree property: If x is a labelled binary tree,
and y is a node in the left subtree of x, then Key(y) <= Key(x).
If y is a node in the right subtree of x, then Key(x) <= Key(y).
// Given a labelled binary tree x, returns true if x has
// the binary search tree property; otherwise returns false.
bool BSTproperty (tree x) {
if (Nil? (x))
return true;
else return BSTproperty (Left(x), Key(x))
&& BSTproperty (Key(x), Right(x));
}
// Returns true iff every label in y is <= x.
bool BSTpropertyLeft (tree y, Z k) {
if (Nil? (y))
return true;
else if (Key(y) <= k)
return BSTpropertyLeft (Left(y), k)
&& BSTpropertyLeft (Right(y), k);
else return false;
}
// Returns true iff x <= every label in y.
bool BSTpropertyRight (Z k, tree y) {
if (Nil? (y))
return true;
else if (k <= Key(y))
return BSTpropertyRight (k, Left(y))
&& BSTpropertyRight (k, Right(y));
else return false;
}
Definition: A persistent dynamic set is a labelled binary
tree that has the binary search tree property.
Note: A persistent dynamic set is almost exactly the same as
a binary search tree, as defined in Chapter 13. There are only
two differences:
1. We have defined persistent dynamic sets as an abstract
data type, whereas the book talks about the fields of
a binary search tree.
2. The parent operation is not defined on persistent
dynamic sets.
See Problem 14-1 on page 278.
****************************************************************
Tree walks.
// Given a persistent dynamic set,
// prints out all of its keys in order.
void InorderTreeWalk (tree x) {
if (! Nil? (x)) {
InorderTreeWalk (Left(x));
cout << Key(x); // or whatever
InorderTreeWalk (Right(x));
}
InorderTreeWalk runs in Theta(n) time, where n is the number of
nodes in the tree x.
void PreorderTreeWalk (tree x) {
if (! Nil? (x)) {
cout << Key(x); // or whatever
PreorderTreeWalk (Left(x));
PreorderTreeWalk (Right(x));
}
void PostorderTreeWalk (tree x) {
if (! Nil? (x)) {
PostorderTreeWalk (Left(x));
PostorderTreeWalk (Right(x));
cout << Key(x); // or whatever
}
****************************************************************
Searching.
// Given a persistent dynamic set and a key k, returns a subtree
// whose key is k if one exists; otherwise returns NIL.
tree TreeSearch (tree x, Z k) {
if (Nil? (x) || (k == Key(x)))
return x;
if (k < Key(x))
return TreeSearch (Left(x), k);
else
return TreeSearch (Right(x), k);
}
TreeSearch runs in O(h) time, where h is the height of the tree x.
There are some programming languages in which the kind of recursion
shown above, which is known as "tail recursion", is just as efficient
as iteration. On the other hand, there are some programming languages
in which tail recursion is likely to be less efficient than iteration.
C, C++, and Pascal happen to be among them.
This does not affect the asymptotic time complexity, but it may affect
the asymptotic space complexity of a program. We can always rewrite a
tail recursion using iteration:
tree IterativeTreeSearch (tree x, Z k) {
while (! (Nil? (x) || (k == Key(x)))) {
if (k < Key(x))
x = Left(x);
else
x = Right(x);
}
return x;
}
Rewriting tail recursion as iteration can be awkward, however.
Generally speaking, I will not bother to rewrite tail recursion as
iteration, because this is a course on algorithms, not a course on
how to deal with the inadequacies of any particular programming
language.
****************************************************************
Minimum and maximum.
// Given a persistent dynamic set with at least one node, returns
// the subtree with the least label.
// Since the argument x always has at least one node, the base
// case must have at least one node. This algorithm therefore
// requires an unnatural recursion. In fact, this algorithm is
// defined by induction on the length of the leftmost path in
// the tree minus 1.
tree TreeMinimum (tree x) {
if (Nil? (Left(x)))
return x;
else return TreeMinimum (Left(x));
}
TreeMinimum runs in O(h) time, where h is the height of the tree x.
****************************************************************
Tree successor.
We can't implement the TreeSuccessor operation as in the book,
because the book's algorithm uses the parent operation. We'll
return to TreeSuccessor later.
****************************************************************
Insertion and deletion.
// Given a persistent dynamic set t and a new value v to insert,
// returns a persistent dynamic set obtained from t by inserting v.
tree TreeInsert (tree t, Z v) {
// See Problem 14-1b.
}
TreeInsert runs in O(h) time, where h is the height of the tree t.
TreeInsert is simpler than TREE-INSERT, and its asymptotic
running time is the same, but it is not an exact equivalent of
TREE-INSERT because it has no side effects. Instead of changing
an existing tree, TreeInsert creates and returns a brand new tree.
Whether this is better or worse than TREE-INSERT depends on how
the trees are used in a program, but it is important to note that
TreeInsert and TREE-INSERT have different behaviors.
// Given a persistent dynamic set t and a key value v,
// returns the persistent dynamic set obtained from t by deleting
// a node labelled by v.
tree TreeDelete (tree t, Z v) {
if (Nil? (t))
return t;
else if (Key(t) == v) {
if (Nil? (Left(t)))
return Right(t);
else if (Nil? (Right(t)))
return Left(t);
else { // difficult case
tree t1 = Left(t);
tree t2 = TreeMinimum (Right(t));
Z k = Key(t2);
tree t3 = TreeDeleteMinimum (t2);
return MakeTree (k, t1, t3);
}
else if (Key(t) < v)
return MakeTree (Key(t), Left(t), TreeDelete (Right(t), v));
else
return MakeTree (Key(t), TreeDelete (Left(t), v), Right(t));
}
}
tree TreeDeleteMinimum (tree t) {
if (Nil? (Left(t)))
return Right(t);
else return MakeTree (Key(t), TreeDeleteMinimum(Left(t)), Right(t));
}
TreeDelete runs in O(h) time, where h is the height of the tree t.
Like TreeInsert, TreeDelete has no side effects so it is not an
exact equivalent of the book's TREE-DELETE.
Last revised 31 July 2001