## Data Structures and Algorithms part 2

#### Andy Novocin

## Daily Problem

Suppose you want to design a dictionary class, `D`

, using a stack class, `S`

, as your underlying structure. (Perhaps you are working in a restricted environment.)

You may assume `S.push(pointer)`

, `S.pop()`

, and `S.isEmpty()`

in \( \mathcal{O}(1) \) time, you may make \( \mathcal{O}(1) \) stacks, and you need not worry about overflow.

What would be the asymptotic worst-case complexity of your `D.Search(key)`

, `D.Insert(pointer)`

, `D.Delete(pointer)`

, `D.Successor(pointer)`

, `D.Predecessor(pointer)`

, `D.Minimum()`

, and `D.Maximum()`

?

### Remember Sorted Linked Lists?

#### Really wanted to do Binary Search.

#### No access to medians.

#### Let's try anyway.

### Start with a sorted doubly-linked list

### Point `HEAD`

to median, point `PREV`

and `NEXT`

to sub-medians

### You've created a Binary Search Tree!

## Graph Theory Tree

**Tree:** Undirected graph in which any two vertices are connected by one (and only one) simple path.

#### (No cycles!)

## Computer Science Version

### Technically our 'trees' will be directed and rooted.

#### A directed graph with special vertex, root, so that there is a unique directed path from the root to any other vertex.

## Binary Tree

**Binary Tree:** A tree data structure in which each node has \( \leq 2 \) children, one left, one right.

#### Recursively, A Binary Tree is either empty or a triple (L, N, R) where L, R are binary trees and N is a **node** / data set.

## Binary Search Tree

### A Binary Tree with sortable nodes and the magic property:

#### All nodes in the left subtree have smaller value than the nodes in the right subtree.

#### The left and right subtrees contain smaller and larger (resp) values than the root node.

## Binary vs Binary Search

## They can be unbalanced!

## Define the Class

#### This code on IDEONE

```
template<class T>
class Tree {
public:
T data;
Tree* left;
Tree* right;
Tree* parent;
Tree(T);
}
```

## Search

```
template <class T>
Tree<T>* Tree<T>::search(string fname){
if (data.name == fname){
return this;
}
if (data.name < fname){
if (right == NULL){
return right;
}
return right->search(fname);
}
if (data.name > fname){
if (left == NULL){
return left;
}
return left->search(fname);
}
}
```

## A New Challenge(r) Appears

## Challenge Problem 1:

Suppose 1 to 1000 are nodes in a binary search tree. We are searching for 363.

Which of the following sequences can NOT be our path?

- A) 2, 252, 401, 398, 330, 344, 397, 363
- B) 924, 220, 911, 244, 898, 258, 362, 363
- C) 925, 202, 911, 240, 912, 245, 363
- D) 2, 399, 387, 219, 266, 382, 381, 278, 363
- E) 935, 278, 347, 621, 299, 392, 358, 363

## Challenge Problem 2:

Professor Bunyan proposes the following property of BSTs:

Suppose that the search for \( k \) ends in a leaf.

Consider three sets

\( A \), the keys to the left of the search path,

\( B \), the keys on the search path,

and \( C \), the keys to the right of the search path.

He claims that any \( a \in A, b \in B, c \in C \) must satisfy \( a \leq b \leq c \).

Give the smallest possible counter example to the professor's claim.

## Min (Max)

```
template <class T>
Tree<T>* Tree<T>::max(){
if (right == NULL){
return this;
}
return right->max();
}
```

## Insert (standard)

```
template <class T>
void Tree<T>::insert(T node_data, Tree * t_parent){
if (data.name < node_data.name){
if (right == NULL){
right = new Tree<T> (node_data);
right->parent = this;
return;
}
right->insert(node_data, this);
return;
};
if (left == NULL){
left = new Tree<T> (node_data);
left->parent = this;
return;
};
left->insert(node_data, this);
return;
};
```

## Insertion Order Matters!

## Traversal

```
template <class T>
Tree<T>* Tree<T>::traverse(){
if (left != NULL){
left->traverse();
}
cout << "Data: " << data.name << " : " << data.phone_number << endl;
if (right != NULL){
right->traverse();
}
}
```

## In-Order Traversal

## Successor (Predecessor)

```
template <class T>
Tree<T>* Tree<T>::successor(){
if (right != NULL){
return right->min();
}
Tree<T>* up_one = parent;
Tree<T>* proxy = this;
while ((up_one != NULL) and (proxy == up_one->right)){
proxy = up_one;
up_one = up_one->parent;
}
return up_one;
}
```

## Who is next?

## Delete (Not coded here)

#### Requires Transplanting within the Tree

- Case 1) Doomed node has no children (EASY, NULL the parent's pointer)
- Case 2) Doomed node has 1 child (MEDIUM, Point Parent to Child)
- Case 3) Doomed node has 2 children (HARD, Transplant the successor)