ADT Binary Search Tree

Tom Kelliher, CS23

Apr. 21, 1996

Material through today on midterm.

Structural properties of binary search tree?

ADT Binary Search Tree Operations

• CreateSearchTree()
• DestroySearchTree()
• SearchTreeIsEmpty()
• SearchTreeInsert(NewItem, Success)
• SearchTreeDelete(SearchKey, Success)
• SearchTreeRetrieve(SearchKey, TreeItem, Success)
• PreorderTraverse(Visit)
• InorderTraverse(Visit)
• PostorderTraverse(Visit)

Example BST

Basic Algorithms

Assumed pointer implementation:

typedef int KeyType;

struct NodeItem
{
   NodeItem* left, right;
   KeyType key;
   // Other fields.
};

typedef NodeItem* Node;

Search

Private method.

Node* Search(Node T, KeyType key)
{
   if (T == NULL)
      return &T;   // For insert.
   else if (key == T->key)
      return &T;   // For retrieve, delete.
   else if (key < T->key)
      return Search(T->left, key);
   else
      return Search(T->right, key);
}

SearchTreeRetrieve

Implement yourself. Assume:

void SearchTreeRetrieve(KeyType SearchKey, NodeItem& TreeItem, 
                        int& Success)

Did you NULL TreeItem's pointers? Why or why not?

SearchTreeInsert

void SearchTreeInsert(NodeItem NewItem, int& Success)
{
   Node* nodePtr;
   Node tmp;

   nodePtr = Search(Root, NewItem.key);   // Find insertion point.
   if (*nodeptr != NULL)
   {
      Success = 0;
      return;
   }

   tmp = new NodeItem;   // Create new tree vertex.
   if (tmp == NULL)
   {
      Success = 0;
      return;
   }
   *tmp = NewItem;
   tmp->left = tmp->right = NULL;

   *nodePtr = tmp;
   Success = 1;
}

SearchTreeDelete

Slightly tricky: Suppose the target vertex has two children?

Don't delete the vertex --- change its label! To what?

Dealing with the ``duplicated'' vertex.

void SearchTreeDelete(KeyType SearchKey, int &Success)
{
   STDelete(Root, SearchKey, Success);
}

void STDelete(Node& T, KeyType SearchKey, int& Success)
{
   if (T == NULL)
   {
      Success = 0;
      return;
   }

   if (SearchKey == T->key)
      DeleteVertex(T, Success);
   else if (SearchKey < T->key)
      STDelete(T->left, SearchKey, Success);
   else
      STDelete(T->right, SearchKey, Success);
}

void DeleteVertex(Node& T, int& Success)
{
   if (T->left == NULL && T->right == NULL)
   {
      delete T;
      T = NULL;
      Success = 1;
   }
   else if (T->right == NULL)
   {
      Node tmp = T;
      T = T->left;
      delete tmp;
      Success = 1;
   }
   else if (T->left == NULL)
   {
      Node tmp = T;
      T = T->right;
      delete tmp;
      Success = 1;
   }
   else
      Rearrange(T, Success);
}

void Rearrange(Node& T, int& Success)
{
   Node* Successor;

   Successor = FindLeast(T->right);

   *T = **Successor;
   DeleteVertex(*Successor, Success);
}

Node* FindLeast(Node T)
{
   if (T->left == NULL);
      return &T;
   else
      return FindLeast(T->left);
}

What is the range of heights of a binary tree with n vertices?

Saving a BST for Later

Save and restore to original shape:

1. Save in preorder.
2. Call SearchTreeInsert (in preorder).

Save and restore to balanced shape:

1. Save number of vertices, save tree in inorder.
2. Recursively restore (keeping track of subtree size):
   1. Restore left subtree.
   2. Restore root.
   3. Restore right subtree.

Representing General Trees

Why can't we have m subtree pointers?

So what do we do?