Spring 2006

Lecture #24 - Binary Tree Structure and Binary Search Tree

• Discussion of the binary tree structure.

• Discussion of binary search trees.

Binary Search Tree

1. Binary Search Tree Property (BSTP)

Consider the following binary tree of Integer objects.

-7
|_ -55
| |_ []
| |_ -16
|    |_ -20
|    | |_ []
|    | |_ []
|    |_ -9
|      |_ []
|      |_ []
|_ 0
|_ -4
| |_ []
| |_ []
|_ 23
|_ []
|_ []

Notice the following property:

• all elements in the left subtree are less than the root element,
• and the root element is less than all elements in the right subtree.

Moreover, this property holds recursively for all subtrees.  It is called the binary search tree (BST) property.

In general, instead of Integer objects, suppose we have a set of objects that can be compared for equality with "equal to" and "totally ordered" with an order relation called "less or equal to" .  Define "less than" to mean "less or equal to" AND "not equal to".  Let T be a BiTree structure that stores such totally ordered objects.

Definition

The binary search tree property (BSTP) is defined on the binary tree structure as follows.

• An empty binary tree satisfies the BSTP.
• A non-empty binary tree T satisfies the BSTP if and only if
• the left and right subtrees of T both satisfy BSTP, and
• all elements in the left subtree of T are less than the root of T, and
• the root of T is less than all elements in the right subtree of T.

We can take advantage of this property when looking up for a particular ordered object in the tree.  Instead of scanning the whole tree for the search target, we can compare the search target against the root element and narrow the search to the left subtree or the right subtree if necessary.  So in the worst possible case, the number of comparisons is proportional to the height of the binary tree.  This is a big win if the tree is balanced.  It can be proven that when a tree containing N elements is balanced, its height is at most a constant multiple of logN.  For example, the height of a balanced tree containing 106 elements is at most a fixed multiple of 6.  Here is the definition of what a balanced tree is.

Definition

• An empty tree is balanced.
• A non-empty tree is balanced if and only if
•  its subtrees are balanced and
• the heights of the subtrees differ by a fixed constant or by a fixed constant factor.

A binary tree with  the BST property is called a binary search tree.  It can serve as an efficient way for storage/retrieval of data.  We are lead to the following question: how to create and maintain a binary search tree?

2. Binary Search Tree Insertion

Suppose we start with an empty binary tree T and  a  Comparator that models a total ordering in a given set of objects S.  Then T clearly has the BST property with respect the Comparator ordering of S.  The following algorithm (visitor on binary trees) will allow us to insert elements of S into T and at the same time maintain the BST property for T.  This algorithm also works for binary search tree containing Comparable objects.

```

```
 BSTInserter.java
```package brs.visitor;

import brs.*;
import java.util.*;

/**
* Inserts an Object into the host maintaining the host's binary search tree
* property via a given Comparator.
* Can also be used for Comparable objects.
* Duplication is not allowed: replaces old data object with the new one.
* @since 04/09/2004
*/
public class BSTInserter implements IVisitor {
private Comparator _order;

/**
* Used when the items in the tree are Comparable objects.
*/
public BSTInserter() {
_order = new Comparator() {
public int compare(Object x, Object y) {
return ((Comparable)x).compareTo(y);
}
};
}

/**
* Used when we want to order the items according to a given Comparator.
* @param order a total ordering on the items to be stored in the tree.
*/
public  BSTInserter (Comparator order) {
_order = order;
}

/**
* Returns the host tree where the input is inserted as the root.
* @param host an empty binary tree, which obviously satisfies BSTP.
* @param input[0] new data to be inserted.
* @return host (which is no longer empty).
*/
public Object emptyCase(BiTree host, Object... input) {
host.insertRoot (input[0]);
return host;
}

/**
* If the input is equal to host.getRootDat) then the old root data is
* replaced by input.  Equality here is implicitly defined by the total
* ordering represented by the Comparator _order.
* @param host non-empty and satisfies BSTP.
* @param input[0] new data to be inserted.
* @return the tree where input[0] is inserted as the root.
*/
public Object nonEmptyCase(BiTree host, Object... input) {
Object root = host.getRootDat();
if (_order.compare(input[0], root) < 0) {
return host.getLeftSubTree().execute(this, input[0]);
}
if (_order.compare(input[0], root) > 0) {
return host.getRightSubTree().execute(this, input[0]);
}
host.setRootDat(input[0]);
return host;
}
}```

3. Binary Search Tree Lookup

Suppose we have a binary search tree based on a given Comparator ordering.  The following algorithm will allow us to lookup and retrieve a particular data object from the tree.  This algorithm also works for binary search tree containing Comparable objects.

 BSTFinder.java
```

package brs.visitor;
import brs.*;
import java.util.*;

/**
* Finds a data object in a binary host tree that satisfies the
* Binary Search Tree Property.
* The algorithm is similar to that of insertion.
* @since 04/09/2004
*/
public class BSTFinder implements IVisitor {
private Comparator _order;
/**
* Used when the items in the tree are Comparable objects.
*/
public BSTFinder() {
_order = new Comparator() {
public int compare(Object x, Object y) {
return ((Comparable)x).compareTo(y);
}
};
}

/**
* Used when the items are ordered according to a given Comparator.
* @param order a total ordering on the items stored in the tree.
*/
public BSTFinder(Comparator order) {
_order = order;
}

/**
* Returns the empty host tree itself.
* @param host an empty binary (which obviously satisfies the
* Binary Search Tree Property).
* @param nu not used
* @return BiTree the empty host tree.
*/
public Object emptyCase(BiTree host, Object... nu) {
return host;
}

/**
* Returns the tree such that whose root, if it exists,  is equal to input
* via the given Comparator _order.
* @param host non empty and satisfies BSTP.
* @param input[0] object to be looked up.
* @return BiTree
*/
public Object nonEmptyCase(BiTree host, Object... input) {
Object root = host.getRootDat();
if (_order.compare(input[0], root) < 0) {
return host.getLeftSubTree().execute(this, input[0]);
}
if (_order.compare(input[0], root) > 0) {
return host.getRightSubTree().execute(this, input[0]);
}
return host;
}
}

```

4. Binary Search Tree Deletion

The algorithm to remove a particular data object from a binary search tree is more involved.  When the element to be removed is not at a leaf node, we can replace it with the largest element of the left subtree (if it's not empty) or the smallest element of the right subtree (if it's not empty).  In preparation, we write a visitor to find the subtree containing the largest element at the root.

 MaxTreeFinder.java
```

package brs.visitor;
import brs.*;
import ordering.*;

/**
* Returns the subtree of the host with the max value in the root if the tree
* is not empty, otherwise returns the host itself, assuming the tree satisfies
* the BST property.
* @author DXN
*/
public class MaxTreeFinder implements IVisitor {
public static final MaxTreeFinder Singleton = new MaxTreeFinder ();
private MaxTreeFinder ()  {
}

/**
* The host tree is empty: the tree containing the max is the host itself.
* @param host satisfies the binary search tree property.
* @param nu not used.
* @return BiTree the empty host itself.
*/
public Object emptyCase(BiTree host, Object... nu) {
return host;
}

/**
* Asks the right subtree of the host to find the max via an anomymous
* helper, passing to it the host as a parameter.
* @param host satisfies the binary search tree property.
* @param nu not used.
* @return BiTree the subtree with maximum root.
*/
public Object nonEmptyCase (BiTree host, Object... nu)  {
return host.getRightSubTree().execute (new IVisitor () {
/**
* The BST parent of an empty right subtree contains the max at the
* root.
* @param hp[0] a Bitree, the parent of h.
*/
public Object emptyCase (BiTree h, Object... hp) {
return hp[0];
}

/**
* Keep going to the right looking for the max.
* @param hp[0] a Bitree, the parent of h.
*/
public Object nonEmptyCase (BiTree h, Object... hp) {
return h.getRightSubTree ().execute (this, h);
}
}, host);
}
}```

We are now ready to write the deletion algorithm for a binary search tree ordered according to a given Comparator.  This algorithm also works for binary search tree containing Comparable objects.

 BSTDeleter.java
```

package brs.visitor;
import brs.*;
import java.util.*;

/**
* Deletes the given input from the host tree.  Returns TRUE if the input is in
* the host tree, otherwise return FALSE.
Invariant: host contains unique objects and satisfies the BST property.
Post: host does not contains the input.
Algorithm:
Case host is empty:
returns FALSE because there is nothing to remove.
Case host is not empty:
if input < root
return the result of asking the left subtree to delete the input;
else if root < input
return the result of asking the right subtree to delete the input;
else if host's left subtree is empty  (at this point, input == root)
ask host to remove its root (and become its right subtree)
returns TRUE
else {
ask host to replace the root with the maximum value of its left subtree;
the subtree that contains the maximum must have an empty right subtree;
thus it is safe to ask this subtree to remove its root;
return TRUE
}

NOTE:

As you have been indoctrinated, it is "uncouth" do ask something for what it
is. Instead of checking a subtree for emptiness, we should ask the subtree to
help carry out the deletion.
* @author Dung X. Nguyen
* @since 04/09/2004
*/
public class BSTDeleter implements IVisitor {
private Comparator _order;

/**
* Used when the items in the tree are Comparable objects.
*/
public BSTDeleter() {
_order = new Comparator() {
public int compare(Object x, Object y) {
return ((Comparable)x).compareTo(y);
}
};
}

/**
* Used when the items are ordered according to a given Comparator.
* @param order a total ordering on the items stored in the tree.
*/
public BSTDeleter (Comparator order) {
_order = order;
}

/**
* There is nothing to delete.
* @param host is empty and obviously satisfies the BST Property.
* @param nu not used
* @return Boolean.FALSE
*/
public Object emptyCase(BiTree host, Object... nu) {
return Boolean.FALSE;
}

/**
if input < root
ask the host's left subtree to delete the input;
else if root < input
ask the host's right subtree to delete the input
else (at this point, input == root)
ask the left subtree for help to remove the host's root using an
anonymous helper.
* @param host non-empty and satifies BST property
* @param input[0] object to be deleted from the host.
* @return Boolean.
*/
public Object nonEmptyCase(final BiTree host, Object... input) {
Object root = host.getRootDat();
if (_order.compare(input[0], root) < 0) {
return host.getLeftSubTree().execute (this, input[0]);
}
if (_order.compare(input[0], root) > 0) {
return host.getRightSubTree().execute (this, input[0]);
}
// At this point:  input is equal to root.
return host.getLeftSubTree().execute(new IVisitor() {
/**
* The outer host can safely remove its root and becomes its right subtree.
* @param h the left subtree of the outer host.
*/
public Object emptyCase (BiTree h, Object notUsed) {
host.remRoot();
return Boolean.TRUE;
}

/**
* Finds the maximum value in the h paramter.
* Asks the outer host parameter to set its root to this maximum
* value, and removes this maximum value from the subtree containing
* this maximum value.
* @param h the left subtree of the outer host.
*/
public Object nonEmptyCase (BiTree h, Object notUsed) {
BiTree maxTree = (BiTree)h.execute(MaxTreeFinder.Singleton);
host.setRootDat(maxTree.remRoot());
return Boolean.TRUE;
}
});
}
}```

We now have all the needed ingredient to implement an efficient container for storage/retrieval/lookup, using the BiTree framework together with the above visitors!