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)

# 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