last updated 3/28/07
Common parent-child traversals
| Inorder: visit left subtree, visit root, visit right subtree | Preorder: visit root, visit left, visit right | Postorder: visit left, visit right, visit root |
| private void Inorder(BSTNode root) { if(root != null) { Inorder(root.left); Process(root.value); Inorder(root.right); } } public void Inorder(){ |
private void Preorder(BSTNode root) { if(root != null) { Process(root.value); Preorder(root.left); Preorder(root.right); } } public void Preorder(){ |
private void Postorder(BTSNode root) { if(root != null) { Postorder(root.left); Postorder(root.right); Process(root.value); } } public void Postorder(){ |
Level order traversal: starting with the root, process all nodes at each level left to right before proceeding to the next level. What data structure will you need to accomplish this?
Deletion of an entire tree (post order traversal)
void DeleteAll(BSTNode cur)
{
if(cur != NULL) {
DeleteAll(cur.getLeft());
DeleteAll(cur.getRight());
cur = null; //now delete node
}
}
Why wouldn't we want to do a preorder traversal for deletion?
public boolean isEmpty()
// Determines whether this BST is empty
{
return (root == null);
}
public boolean isFull()
// Determines whether this BST is full
{
return false;
}
Note difference in code complexity for recursive and nonrecursive solutions. Of course if we tracked the number of nodes through insertion and deletion operations, this routine would trivially return the count.
private int recSize(BSTNode tree)
// Determines the number of nodes in tree recursively
{
if (tree == null)
return 0;
else
return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;
}
public int Size()
// Determines the number of nodes in this BST
{
return recSize(root);
}
public int Size2()
// Determines the number of nodes in this BST non-recursively {
int count = 0;
if (root != null)
{
LinkedStack hold = new LinkedStack();
BSTNode currNode;
hold.push(root);
while (!hold.isEmpty())
{
currNode = (BSTNode) hold.top();
hold.pop();
count++;
if (currNode.getLeft() != null)
hold.push(currNode.getLeft());
if (currNode.getRight() != null)
hold.push(currNode.getRight());
}
}
return count;
}
private boolean recContains(Comparable item, BSTNode tree)
// returns true if item is in tree, false otherwise
{
if (tree == null)
return false; // item is not found
else if (item.compareTo(tree.getInfo()) < 0)
return recIsThere(item, tree.getLeft()); // Search left subtree
else if (item.compareTo(tree.getInfo()) > 0)
return recIsThere(item, tree.getRight()); // Search right subtree
else
return true; // item is found
}
public boolean contains (Comparable item)
// Determines if element matching item is in this BST.
{
return reContains(item, root);
}
private Comparable recGet(Comparable item, BSTNode tree)
// Returns the element in tree with the same key as item.
// Pre: isThere(item)==true
{
if (item.compareTo(tree.getInfo()) < 0)
return recRetrieve(item, tree.getLeft()); // retrieve from left subtree
else
if (item.compareTo(tree.getInfo()) > 0)
return recRetrieve(item, tree.getRight()); // retrieve from right subtree
else
return tree.getInfo();
}
public Comparable get(Comparable item)
// Returns the BST element with the same key as item.
// Pre: isThere(item)==true
{
return recGet(item, root);
}
These two operations can be expressed as non-recursive routines.
public boolean contains (Comparable item)
// Determines if element matching item is in this BST.
{
BSTNode temp = root;
while(temp != null){
int comp = item.compareTo(temp.getInfo());
if(comp==0)
return true;
else if (comp<0)
temp = temp.getLeft();
else
temp = temp.getRight();
}
return false;
}
public Comparable get(Comparable item)
// Returns the BST element with the same key as item.
// Pre: isThere(item)==true
{
BSTNode temp = root;
while(temp != null){
int comp = item.compareTo(temp.getInfo());
if(comp==0)
return temp.getInfo();
else if (comp<0)
temp = temp.getLeft();
else
temp = temp.getRight();
}
return null;
}
private BSTNode recAdd(Comparable item, BSTNode tree)
// Inserts item into the tree
{
if (tree == null)
{// Insertion place found
tree = new BSTNode(item);
}
else if (item.compareTo(tree.getInfo()) <= 0)
tree.setLeft(recAdd(item, tree.getLeft())); // Insert in left subtree
else
tree.setRight(recAdd(item, tree.right())); // Insert in right subtree
return tree;
}
public void insert (Comparable item)
// Adds item to this BST.
{
root = recAdd(item, root);
}
Insertion order has an effect on the tree structure
Three cases:
private BSTNode removeNode(BSTNode tree)
// Deletes the node referenced by tree
// Post: The user's data in the node referenced to by tree is no
// longer in the tree. If tree is a leaf node or has only
// a non-null child pointer, the node pointed to by tree is
// deleted; otherwise, the user's data is replaced by its
// logical predecessor and the predecessor's node is deleted
{
Comparable data;
if (tree.getLeft() == null)
return tree.getRight();
else if (tree.getRight() == null)
return tree.getLeft();
else
{
data = getPredecessor(tree.getLeft());
tree.setInfo(data);
tree.setLeft(recDelete(data, tree.getLeft())); // Delete predecessor node
return tree;
}
}
private Comparable getPredecessor(BSTNode tree)
// Returns the info member of the rightmost node n tree
{
while (tree.getRight() != null)
tree = tree.getRight();
return tree.getInfo();
}
private BSTNode recRemove(Comparable item, BSTNode tree)
// Deletes item from the tree
{
if(tree==null)
found = false;
else if (item.compareTo(tree.getInfo()) < 0)
tree.setLeft(recRemove(item, tree.getLeft()));
else if (item.compareTo(tree.getInfo()) > 0)
tree.setRight(recRemove(item, tree.getRight()));
else {
tree = removeNode(tree);
found = true;
}
return tree;
}
public boolean remove (Comparable item)
// Delete the element of this BST whose key matches item’s key.
{
root = recDelete(item, root);
return found;
}
public int reset(int orderType)
// Initializes current position for an iteration through this BST in orderType order
{
int numNodes = numberOfNodes();
if (orderType == INORDER)
{
inOrderQueue = new ArrayQueue(numNodes);
inOrder(root);
}
else
if (orderType == PREORDER)
{
preOrderQueue = new ArrayQueue(numNodes);
preOrder(root);
}
if (orderType == POSTORDER)
{
postOrderQueue = new ArrayQueue(numNodes);
postOrder(root);
}
return numNodes;
}
public Comparable getNextItem (int orderType)
// Returns a copy of the element at the current position in this BST and advances
// the value of the current position based on the orderType set through reset
{
if (orderType == INORDER)
return (Comparable)inOrderQueue.dequeue();
else if (orderType == PREORDER)
return (Comparable)preOrderQueue.dequeue();
else if (orderType == POSTORDER)
return (Comparable)postOrderQueue.dequeue();
else return null;
}
private void inOrder(BSTNode tree)
// initializes inOrderQueue with tree elements in inOrder order
{
if (tree != null)
{
inOrder(tree.left);
inOrderQueue.enqueue(tree.getInfo());
inOrder(tree.right);
}
}
private void preOrder(BSTNode tree)
// initializes preOrderQueue with tree elements in preOrder order
{
if (tree != null)
{
preOrderQueue.enqueue(tree.getInfo());
preOrder(tree.left);
preOrder(tree.right);
}
}
private void postOrder(BSTNode tree)
// initializes postOrderQueue with tree elements in postOrder order
{
if (tree != null)
{
postOrder(tree.left);
postOrder(tree.right);
postOrderQueue.enqueue(tree.getInfo());
}
}
| Operation | BST | Array List | Linked List |
|---|---|---|---|
| Class constructor | O(1) |
O(1) |
O(1) |
| isFull | O(1) |
O(1) |
O(1) |
| isEmpty | O(1) |
O(1) |
O(1) |
| reset | O(N) |
O(1) |
O(1) |
| getNextItem | O(1) |
O(1) |
O(1) |
| isThere | O(log N) |
O(log N) |
O(N) |
| retrieve (find +process =total |
O(log N) +O(1) =O(log N) |
O(log N) +O(1) =O(log N) |
O(N) +O(1) =O(N) |
| insert (find +process =total |
O(log N) +O(1) =O(log N) |
O(log N) +O(N) =O(N) |
O(N) +O(1) =O(N) |
| delete (find +process =total |
O(log N) +O(1) =O(log N) |
O(log N) +O(N) =O(N) |
O(N) +O(1) =O(N) |
The BST in the above analysis is assumed to be rather balanced. Algorithms are studied in A&A to ensure that a tree is maintained in a balanced state. These algorithms do not affect the complexity cost, i.e., they remain logarithmic.
A variation on the BST is a B-tree (the "B" is for the creator, Bayer) which shortens the height of the tree for even faster operations. B-trees are balanced by definition and are one of the popular data structures for use in a database.