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.

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.

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);
  }
}

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;
};

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();
  }
}

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;
}

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)

Draw Picture On Board