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

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?



Thomas P. Kelliher
Sun Apr 21 14:41:14 EDT 1996
Tom Kelliher