A binary search tree is a recursively defined data structure that simplifies the process of conducting binary searches by marking appropriate bisection points structurally instead of requiring them to be computed. Unlike an array, it also allows for the efficient insertion of new items in the data structure during program execution.
Here's the recursive definition: A binary search tree B either is empty or consists of a datum (typically a record that includes a key field) and two binary search trees L and R, called the left and right subtrees of B. Either or both of these subtrees may of course be empty. An invariant condition of every non-empty binary search tree B is that if its left subtree L is not empty, the key of the record stored at L is less than the key of the record stored at B (or precedes it in some conventional ordering of the key data type), and similarly that if B's right subtree R is not empty, the key of the datum stored at R is greater than the key of the record stored at B. This invariant must be preserved whenever the contents of a binary search tree are changed.
In Pascal, one can use pointers to implement this data type, as follows:
type
Element = record
Key: KeyType;
{ and presumably other fields }
end;
BinarySearchTree = ^Component;
Component = record
Datum: Element;
Left, Right: BinarySearchTree
end;
An empty binary search tree is represented by a nil pointer, a non-empty one by a pointer to a component containing the datum and two binary search trees.
Creating an empty binary search tree, or one that contains just one datum, is trivial, as is testing whether a given binary search tree is empty:
function MakeEmptyBinarySearchTree: BinarySearchTree;
begin
MakeEmptyBinarySearchTree := nil
end;
function MakeSingletonBinarySearchTree (Elm: Element): BinarySearchTree;
var
Result: BinarySearchTree;
begin
New (Result);
Result^.Datum := Elm;
Result^.Left := MakeEmptyBinarySearchTree;
Result^.Right := MakeEmptyBinarySearchTree;
MakeSingletonBinarySearchTree := Result
end;
function EmptyBinarySearchTree (B: BinarySearchTree): Boolean;
begin
EmptyBinarySearchTree := (B = nil)
end;
Suppose, however, that one wants to add a datum to an existing binary search tree B. This is again trivial if B is empty; one simply replaces B with the singleton binary search tree containing just the new datum. But if B is non-empty one must be careful to preserve the invariant stated above. Recursion provides a simple way to do this: Compare the datum to be inserted with the one stored at B. If the datum to be inserted is less than B, insert it into B's left subtree; otherwise, insert it into B's right subtree. In either case, perform the replacement by making a recursive call to the insertion procedure. The recursion will bottom out when one reaches a subtree of a subtree of a subtree, etc., that is empty. Replace this one with the singleton binary search tree containing just the new datum.
Or in Pascal:
procedure InsertIntoBinarySearchTree (Elm: Element; var B: BinarySearchTree);
begin
if EmptyBinarySearchTree (B) then
B := MakeSingletonBinarySearchTree (Elm)
else if Elm.Key < B^.Datum.Key then
InsertIntoBinarySearchTree (Elm, B^.Left)
else
InsertIntoBinarySearchTree (Elm, B^.Right)
end;
Recursion is also the appropriate tool when one wants to search a binary search tree, perhaps to recover a record containing a specified key:
function SearchBinarySearchTree (Sought: KeyType; B: BinarySearchTree;
var Found: Element): Boolean;
begin
if EmptyBinarySearchTree (B) then
SearchBinarySearchTree := False
else if Sought < B^.Datum.Key then
SearchBinarySearchTree := SearchBinarySearchTree (Sought, B^.Left, Found)
else if B^.Datum.Key < Sought then
SearchBinarySearchTree := SearchBinarySearchTree (Sought, B^.Right, Found)
else begin
SearchBinarySearchTree := True; { because Sought = B^.Datum.Key }
Found := B^.Datum
end
end;
In procedure InsertIntoBinarySearchTree and function SearchBinarySearchTree, only one branch of the tree is explored. Subtrees that contain elements that can't possibly be relevant to the insertion or to the search are bypassed. Occasionally, however, one wants to perform some operation on each of the data stored in a tree, specifically in ascending order. For instance, one might want to write out an index of the collection of records stored in the tree -- a list of the keys, in ascending order, one to a line. Recursion can be used for this purpose, too, but there will be two recursive calls rather than one, corresponding to the fact that each non-empty binary search tree contains two subtrees:
procedure PrintBinarySearchTreeData (B: BinarySearchTree);
begin
if not EmptyBinarySearchTree (B) then begin
PrintBinarySearchTreeData (B^.Left);
writeln (B^.Datum.Key);
PrintBinarySearchTreeData (B^.Right)
end
end;
Notice that the keys for all of the data stored in B's left subtree will be printed out before the key for the datum actually stored at B (since, under the invariant, all those keys will precede the one stored at B in the desired ordering), while all those stored in the right subtree will be printed only after the key for the datum stored at B. This technique for traversing a binary tree is called an inorder traversal. One can generalize it by abstracting the procedure to be performed on each datum:
procedure ApplyThroughoutBinarySearchTree (var B: BinarySearchTree;
procedure P (var Elm: Element));
begin
if not EmptyBinarySearchTree (B) then begin
ApplyThroughoutBinarySearchTree (B^.Left, P);
P (B^.Datum);
ApplyThroughoutBinarySearchTree (B^.Right, P)
end
end;
It would alternatively be possible to perform some operation on the datum at each non-empty binary tree before proceeding to its left and right subtrees; a traversal that is arranged in this way is called a preorder traversal. Still another arrangement is to defer the processing of the datum at each non-empty binary tree until after the data in both of its subtrees have been dealt with; this is a postorder traversal. A postorder traversal is used, for instance, when deallocating a binary tree:
procedure DeallocateBinarySearchTree (var B: BinarySearchTree);
begin
if not EmptyBinarySearchTree (B) then begin
DeallocateBinarySearchTree (B^.Left);
DeallocateBinarySearchTree (B^.Right);
Dispose (B)
end
end;
A postorder traversal is necessary in this case because after the storage at the other end of the pointer B has been recycled, there would be no way to reach B^.Left or B^.Right.
Deleting a single datum from a binary search tree is in some cases a rather delicate operation. If the datum is stored at a position where both the left and right subtrees are empty, the binary search tree can be treated as a singleton and simply replaced with an empty BinarySearchTree. If one of the subtrees is empty and the other is not, the non-empty subtree can simply be promoted into the position occupied by its parent; this will not affect the truth of the invariant, since all of the elements in that subtree will still be in the same order relative to everything outside that subtree.
The most difficult case arises, then, when the datum to be deleted is at a position where both of the subtrees are non-empty. The solution is to find one of the two data that is adjacent, in preorder, to the one to be deleted -- either the element in the left subtree that has the largest key, or the element in the right subtree that has the smallest key. (The choice between these alternatives is arbitrary, so in this implementation I've arranged for the selection of the former.) It is impossible for this adjacent element to be at a position where both of its subtrees are non-empty (otherwise one of its subtrees would contain an element still closer to the datum to be deleted). So this adjacent element can be copied up into the record containing the datum to be deleted, overwriting it, and then the adjacent element can itself be deleted by one of the relatively easy methods described in the previous paragraph.
Here's how it looks in Pascal. In this version, the deletion procedure has no effect if the caller specifies a key that does not correspond to any of the elements of the binary search tree.
procedure DeleteFromBinarySearchTree (Sought: KeyType;
var B: BinarySearchTree);
var
Delend: BinarySearchTree;
{ a spare pointer to the component to be recycled }
{ The DeleteLargest function finds and returns the largest element in
a given binary search tree and simultaneously deletes it from that
binary search tree. It presupposes that the binary search tree is not
empty. }
function DeleteLargest (var Site: BinarySearchTree): Element;
var
Delend: BinarySearchTree;
{ a spare pointer to the Component to be recycled }
begin
if EmptyBinarySearchTree (Site^.Right) then begin
DeleteLargest := Site^.Datum;
Delend := Site;
Site := Site^.Left;
Dispose (Delend)
end
else
DeleteLargest := DeleteLargest (Site^.Right)
end;
begin { procedure DeleteFromBinarySearchTree }
if B <> nil then begin
if Sought < B^.Datum.Key then
DeleteFromBinarySearchTree (Sought, B^.Left)
else if B^.Datum.Key < Sought then
DeleteFromBinarySearchTree (Sought, B^.Right)
else begin { we've found the datum to be deleted }
if EmptyBinarySearchTree (B^.Left) then begin
Delend := B;
B := B^.Right;
Dispose (Delend)
end
else if EmptyBinarySearchTree (B^.Right) then begin
Delend := B;
B := B^.Left;
Dispose (Delend)
end
else
B^.Datum := DeleteLargest (B^.Left)
end
end
end;
Given an array of records of type Element, here's a procedure that will sort them by inserting them into a binary search tree and then copying them back out again:
type
ElementArray = array [1 .. ArraySize] of Element;
procedure BinarySearchTreeSort (var Arr: ElementArray);
var
Container: BinarySearchTree;
Index: integer;
procedure Restore (var Elm: Element);
begin
Index := Index + 1;
Arr[Index] := Elm
end;
begin
Container := MakeEmptyBinarySearchTree;
for Index := 1 to ArraySize do
InsertIntoBinarySearchTree (Arr[Index], Container);
Index := 0;
ApplyThroughoutBinarySearchTree (Container, Restore);
DeallocateBinarySearchTree (Container)
end;
Alternatively, one might read the elements in from a file of records of type Element and write them back out to the same file in sorted order:
type
ElementFile = file of Element;
procedure BinarySearchTreeSortFile (var F: ElementFile);
var
Container: BinarySearchTree;
procedure WriteToFile (var Elm: Element);
begin
Write (F, Elm)
end;
begin
Reset (F);
Container := MakeEmptyBinarySearchTree;
while not EOF (F) do begin
InsertIntoBinarySearchTree (F^, Container);
Get (F)
end;
Rewrite (F);
ApplyThroughoutBinarySearchTree (Container, WriteToFile);
DeallocateBinarySearchTree (Container)
end;
