Binary Search Trees, Part 2: Find Min, Find Max, and Deletion.

Binary Search Trees Part 2

In Part One of this series, i covered Insertion, Searching, and Traversal of Binary Search Trees. No that we can create and add to a tree, as well as display its contents and retrieve contents, It’s time to implement three more fundamental functions of a BST: Find the minimum value, find the maximum value, and deletion from  a BST.

Once we have implemented these features we have a full implementation of a binary search tree data structure, which can be used for implementing maps, sets, dictionaries, or any other ADT that requires items be kept in sorted order or fast efficient searching – two things BST’s excel at.

While it might seem odd to switch up implementations in the middle, i’m also going to use take this opportunity to show a second way of constructing BST’s. In Part One we pursued a nullpointer based implementation using std::shared_pointer. In this article, we will use raw pointers, but will be using dummy nodes instead of null pointers.

Why implement a BST with dummy nodes?

There are two schools of thought when it comes to pointer based data structure convention, be them linked lists or tree structures. The use of “dummy” nodes, or the use of “null pointers”. By far the more popular implementation method is the use of null pointers: they have less memory overhead, and it leads to a leaner code base. On the other hand, dummy nodes guarentee that there is starting and stopping point that cant be overrun during search and traversal, greatly reducing on out of bounds errors, and all the headaches that can arise while trying to keep track of having null pointers on the stack.

If it helps sway your mind in either direction, think about this: The inventor of the concept of a “null pointer”, Tony Hoare (who invented Quicksort) profusely apologized for introducing it during a speech at a computer conference, referring to it as his “billion dollar mistake.” yikes.

Because of the change in structuring Here is the class outline, along with modified insertion function for a dummy node based BST.

class BST {
  private:
   class node {
    public:
     int v;
     int d;
     node* r;
     node* l;
     node(int k, node* ll, node* rr) : v(k), l(ll), r(rr) { }
     node() { }
     ~node() { }
   };
 public:
  node *head;
  node *z;
  node *root;
  BST()
  {
    z = new node (INT32_MAX, NULL, NULL);
    head = new node(INT32_MIN, NULL, z);
    head->r = z;
    z->l = z->r = z;
  }
  ~BST()
  {
    delete head;
    delete z;
  }
  void insert(int v);
  void remove(int v);
  int search(int v);
  int findMin();
  int findMax();
};


void BST::insert(int v)
{
  node *t = new node(v, z, z);
  node *x = head;
  node *p = x;
  while (x != z)
  {
    p = x;
    //no duplicate entries
    if (v == x->v)
      return;
    x = (v < x->v) ? x->l:x->r;
  }
  if (v < p->v) p->l = t;
  else p->r = t;
}

Finding the Maximum Value

Since we know that a BST keeps its data in a sorted order, we can exploit this property to quickly retrieve the maximum value by accessing the value stored at the right most node of the tree:

int BST::findMax()
{
  node* x = head->r;
  node* p = x;
  while (x != z)
  {
    p = x;
    x = x->r;
  }
  return p->v;
}

Note that we are keeping track of a parent pointer, as we are using dummy nodes instead of null pointers to denote an empty child link.

Finding the Minimum Value

Just as we did for finding the maximum value, we iterate down the appropriate side of the tree, in this case, the left side until we reach the last node (the left most node), again keeping track with a parent pointer.

int BST::findMin()
{
  node *x = head->r;
  node *p = x;
  while (x != z)
  {
    p = x;
    x = x->l;
  }
  return p->v;
}

Deleting nodes in a Binary Search Tree

While most algorithms relating to BST’s are relatively simple, the one part that requires a bit more thought is the removal of a node from the tree. We will once again make use of “relative” pointers to track not only just parent nodes, but grand parent nodes, great grand parent nodes, and child pointers as well.

There are three cases we need to account for when removing a node from the tree:

1. The node has no children
2. the node has only one child node
3. the node has both left and right child nodes

With that being said, lets take a look:

void BST::remove(int v)
{
  node *c, *p, *x, *t;
  z->key = v;
  p = head; x = head->r;
  //find the parent of the node to be deleted
  while (v != x->key)
  {
    p = x;
    x = (v < x->key) ? x->l:x->r;
  }
  //assign the node to be deleted to t
  t = x;
  //case 1: t has no right child
  if (t->r == z) {
    x = x->l;
  //case 2: t has a child node
  } else if (t->r->l == z) {
    x = x->r;
    x->l = t->l;
  } else {
  //case 3: t has right and left child
    c = x->r;
    while (c->l->l != z) c = c->l;
    x = c->l; c->l = x->r;
    x->l = t->l; x->r = t->r;
  }
  delete t;
  if (v < p->key) p->l = x;
  else p->r = x;
}