Binary Search Tree

Simplified

By: Nicholas Duchon.

Outline:

Next Page:


Notes:

Here's a simplified version of a Binary Search Tree class.

It is still pretty complicated, but perhaps a little easier to follow. Not as functional as the one in DJW, but simpler is easier to follow the key issues.

Comparable is a generic class, so the correct invocation of it includes a class type parameter. < K > would be ok, which means that K (the left side of
< K extends Comparable < ? super K > >) may be compared ONLY to instances of K. The use of the < ? super K > is the way to tell the compiler that any child class of K is also ok. I know, painful, but that's what it takes to make the compiler happy, and finally, if you think about it (maybe after a few beers!), it really does make sense.

Yadah, yadah!

Well, by doing it this way, our BinarySearchTreeND can accept any class that extends the Comparable class K - which really does make sense, since this is a data structure that is supposed to insert elements (instances) in order, and that order really should come from the way K or its child classes implement Comparable.

Which classes do that already? The ones with which you are perhaps most familiar: String, Integer, and Double.

Any class that YOU define that implements Comparable is also ok.

What does this prevent? A moderately complicated situation: Say class A (think Apples) and class B (think Oranges) implement comparable and don't have anything to do with each other, but class C extends class A (think RedDeliciousApples). Using this data structure, the compiler will allow you to insert A and C elements into the same instance (of BinarySearchTreeND), but not B items (which the compiler will flag as type-mismatch errors). I hope you find this a compelling reason for all this complexity!


Code Version 1

// File: BinarySearchTreeND
// Author: Nicholas Duchon
// Date: July 31, 2008

// Simplified, linked version of a binary search tree
// uses generic class implementing Comparable
// no exceptions thrown
// This code implements the following operations:
// insert (Comparable< T >)
// remove (Comparable< T >)
// find (Comparable< T >)
// getSize ()
// max ()
// toString (int)

public class BinarySearchTreeND
< K extends Comparable< ? super K > > // ANY class that extends comparable is OK
{
static final int INORDER = 1;
static final int PREORDER = 2;
static final int POSTORDER = 3;
static int depth = 5;

BSTNodeND < K > root = null;

class BSTNodeND
< L extends Comparable< ? super L > >
{
L data;
BSTNodeND < L > left = null, right = null;

BSTNodeND (L d) {data = d;}

private void insertValue (L d) {
if (d.compareTo (data) > 0)
if (right == null) right = new BSTNodeND < L > (d);
else right.insertValue (d);
else
if (left == null) left = new BSTNodeND < L > (d);
else left.insertValue (d);
} // end method insertValue

private BSTNodeND < L > findValue (L d) {
if (data.compareTo(d) == 0)
return this;
if (data.compareTo (d) > 0)
return (left==null)?null:left.findValue (d);
return (right == null)?null:right.findValue(d);
} // end findValue

private BSTNodeND < L > findMax () {
if (right == null) return this;
return right.findMax();
} // end findValue

public String toString () {
return toString (INORDER);
} // end toString

public String toString (int order) {
String st = "";
switch (order) {
case INORDER:
st += (left == null)?"":left.toString(order);
st += data + "\n";
st += (right == null)?"":right.toString(order);
break;
case PREORDER:
st += String.format ("%" + depth + "s\n", data);
depth += 5;
st += (left == null)?"":String.format ("L%" + depth + "s", left.toString(order));
st += (right == null)?"":String.format ("R%" + depth + "s", right.toString(order));
depth -= 5;
break;
case POSTORDER:
st += (left == null)?"":left.toString(order);
st += (right == null)?"":right.toString(order);
st += data + "\n";
break;
} // end switch
return st;
} // end toString int

} // end class BSTNodeND

public void insert (K d) {
if (root == null) root = new BSTNodeND < K > (d);
else root.insertValue (d);
} // end insert, public version

public K find (K d) {
if (root == null)
return null;
BSTNodeND < K > t = root.findValue (d);
return (t==null)?null:t.data;
} // end find method

public K max () {
if (root == null) return null;
return root.findMax().data;
} // end max method

public int getSize () {
return getSize (root);
} // end getSize

private int getSize (BSTNodeND < K > t) {
if (t == null)
return 0;
return getSize (t.left) + getSize (t.right) + 1;
} // end getSize node

private BSTNodeND < K > removeRoot (BSTNodeND < K > t) {
if (t.left == null) return t.right;
if (t.right == null) return t.left;
BSTNodeND < K > newTop = t.left.findMax();
t = remove (newTop.data, t);
t.data = newTop.data;
return t;
} // end remove data, tree

private BSTNodeND < K > remove (K d, BSTNodeND < K > t) {
if (t == null) return null;
if (d.compareTo (t.data) < 0)
t.left = remove (d, t.left );
else
if (d.compareTo (t.data)> 0)
t.right = remove (d, t.right);
else // d equals t.data
t = removeRoot (t);
return t;
} // end remove data, tree

public void remove (K d) {
root = remove (d, root);
} // end remove data

public String toString () {
if (root == null) return null;
return root.toString();
} // end toString no parameters

public String toString (int ord) {
if (root == null) return null;
return root.toString(ord);
} // end toString int

public static void main (String args []) {
BinarySearchTreeND < Integer > x = new BinarySearchTreeND < Integer > ();
x.insert (40);
x.insert (20);
x.insert (60);
x.insert (10);
x.insert (30);
x.insert (50);
x.insert (70);
System.out.println ("X: >\n" + x + "< ");
System.out.println ("X inorder:\n" + x.toString(INORDER));
System.out.println ("X preorder:\n" + x.toString(PREORDER));
System.out.println ("X postorder:\n" + x.toString(POSTORDER));
Integer t = x.find(10);
System.out.println ("find: " + t);
System.out.println ("find: " + x.find(20));
System.out.println ("Size: " + x.getSize());
System.out.println ("MAX: " + x.max());
x.remove (15);
System.out.println ("X preorder:\n" + x.toString(PREORDER));
} // end main

} // end class BinarySearchTreeND

Code Version 2

// File  : BinarySearchTreeND.java
// Author: Nicholas Duchon
// Date  : July 31, 2008
// updates: 
//        Nov 16, 2008
//        Nov 22, 2008
//        Apr 17, 2009 - fixed toTreeString
//        Apr 17, 2009 - added parents to nodes and \ and / to tree display.
//        Mar 18, 2012 - cleaned up some generic lint stuff in BSTNodeND declarations
//
// Simplified, linked version of a binary search tree
// uses generic class implementing Comparable
// no exceptions thrown
//   static fields
//       all associated with toString displays
//       .. DEPTHDELTA - used to present a tree-like display using spacing
//   This code implements the following public methods
//            T is a Comparable class
//       insert   (T)  : void
//       find     (T)  : T
//       max      ()   : T
//       getSize  ()   : int
//       remove   (T)  : void
//       toString ()   : String // to tree string
//
//    private mutator/accessor methods
//       insertValue (T, BSTNodeND < T >): void - uses comparator from T
//       findValue   (T, BSTNodeND < T >): T - finds an T, returns null if not found
//       findMax                       (): T - returns max value in this subtree
//       getSize        (BSTNodeND < T >): int
//       removeRoot     (BSTNodeND < T >): BSTNodeND < T >
//       remove      (T, BSTNodeND < T >): BSTNodeND < T >
//
//    private toString methods
//       toString            (BSTNodeND) : uses toTreeString (int) to create a tree-like display
//       toTreeString   (int, BSTNodeND) : recursive in-order traversal with depth offsets
//       toInOrderString     (BSTNodeND) : recursive in-order string
//       toPreOrderString    (BSTNodeND) : recursive pre-order string
//       toPostOrderString   (BSTNodeND) : recursive post-order string
//       toLevelOrderString  (BSTNodeND) : level-order string, uses a queue (ArrayDeque)
//
// Inside the BSTNodeND class:
//    Instace fields:
//       data  < L >   generic parameter of the BSTNodeND class, NOT the BinarySearchTreeND class
//       BSTNodeND left, right, parent - links to create the tree
//    constructors
//       < L > generic parameterized constructor, left and right are null
//       < L >, NSTNodeND - links to parent also, for tree display
//
//    import java.util.ArrayDeque;

   import java.util.Scanner;

   public class BinarySearchTreeND 
      < K extends Comparable < ? super K > > 
      // ANY class that extends the base comparable type (K)
      // of this data structure instance may be inserted
   {
      static final int DEPTHDELTA = 5; // used to create a text tree display
   
      BSTNodeND < K > root = null;
   
      public void insert (K d) {
         insertNode (new BSTNodeND < K > (d));
      } // end insert, public version
      
      public void insertNode (BSTNodeND < K > n) {
         if (root == null) root = n;
         else insertNode (n, root);
      } // end insert Node
   
      public K find (K d) {
         if (root == null) 
            return null;
         BSTNodeND < K > t = findValue (d, root);
         return (t==null)?null:t.data;
      } // end find method
      
      public K max () {
         if (root == null) 
            return null;
         return findMax(root).data;
      } // end max method
   
      public int getSize () {
         return getSize (root);
      } // end getSize method
   
      public void remove (K d) {
         root = remove (d, root);
      } // end remove data
   
      public String toString () {
         if (root == null) 
            return null;
         return toString(root);
      } // end toString
         
      private void insertNode (BSTNodeND < K > d, BSTNodeND < K > n) {
         d.parent = n;
         if (d.data.compareTo (n.data)  > 0) 
            if (n.right == null) n.right = d;
            else insertNode (d, n.right);
         else 
            if (n.left == null) n.left = d;
            else insertNode (d, n.left);
      } // end method insertNode
      
      private BSTNodeND < K > findValue (K d, BSTNodeND < K > n) {
         if (n.data.compareTo(d) == 0) 
            return n;
         if (n.data.compareTo (d) > 0) 
            return (n.left==null)?null:findValue (d, n.left);
         return (n.right == null)?null:findValue(d, n.right);
      } // end findValue
      
      private BSTNodeND < K > findMax (BSTNodeND < K > n) {
         if (n.right == null) 
            return n;
         return findMax(n.right);
      } // end findValue
      
      private int getSize (BSTNodeND < K > t) {
         if (t == null) 
            return 0;
         return getSize (t.left) + getSize (t.right) + 1;
      } // end getSize node
      
      private BSTNodeND < K > removeRoot (BSTNodeND < K > t) {
         if (t.left  == null) {
            if (t.right != null) 
               t.right.parent = t.parent;
            return t.right;
         }
         if (t.right == null) {
            t.left.parent = t.parent; // t.left != null because of earlier if test case
            return t.left;
         }
         BSTNodeND < K > newTop = findMax(t.left);
         remove (newTop.data, t); // lose the node instance, leave tree intact
         t.data = newTop.data;    // just replace the data at the internal node
         return t;
      } // end remove data, tree
   
      private BSTNodeND < K > remove (K d, BSTNodeND < K > t) {
         if (t == null) 
            return null;
         if (d.compareTo (t.data) < 0) 
            t.left  = remove (d, t.left );
         else 
            if (d.compareTo (t.data)> 0) 
               t.right = remove (d, t.right);
            else // d equals t.data
               t = removeRoot (t);
         return t;
      } // end remove data, tree
   
      private String toString (BSTNodeND < K > n) {
         return toTreeString (5, n); 
      } // end toString
         
      private String toTreeString (int depth, BSTNodeND < K > n) { // depth = 0 is bad
         char d = '\\';                         // default = this is right child
         if      (n.parent == null)   d = ' ';  // case of root
         else if (n == n.parent.left) d = '/';  // case that this is left child
         return
            ((n.left  == null)?"":toTreeString  (depth + DEPTHDELTA, n.left))
          + String.format ("%" + depth + "s%s\n", d, n) // ND: fixed 4/17/2009
          + ((n.right == null)?"":toTreeString (depth + DEPTHDELTA, n.right));
      } // end method toTreeString
         
      private String toInOrderString (BSTNodeND < K > n) {
         return
              ((n.left  == null)?"":toInOrderString(n.left ))
            +  n + " "
            + ((n.right == null)?"":toInOrderString(n.right));
      } // end toInOrderString
         
      private String toPreOrderString (BSTNodeND < K > n) {
         return 
             n + " "
           + ((n.left  == null)?"":toPreOrderString(n.left ))
           + ((n.right == null)?"":toPreOrderString(n.right));
      } // end toPreOrderString
         
      private String toPostOrderString (BSTNodeND < K > n) {
         return
              ((n.left  == null)?"":toPostOrderString(n.left ))
            + ((n.right == null)?"":toPostOrderString(n.right))
            + n + " ";
      } // end to PostOrderString
         
         // See: http://en.wikipedia.org/wiki/Tree_traversal
      private String toLevelOrderString (BSTNodeND < K > n) {
         String st = "";
         BSTNodeND < K > node;
         java.util.ArrayDeque < BSTNodeND < K > > q 
               = new java.util.ArrayDeque < BSTNodeND < K > > ();
         q.add (n);          // start queue by adding this (root?) to queue
         while (q.size() > 0) { 
            node = q.remove();                          // remove the head of queue
            st += (node.data + " ");                // process head data to String
            if (node.left != null) q.add (node.left);   // insert left child at end of queue
            if (node.right != null) q.add (node.right); // insert right child at end or queue
         } // end queue processing
         return st.toString();
      } // end to LevelOrderString
         
      // main and example methods follow
      public static void main (String args []) {
         integerExample ();
         stringExample ();
         Scanner st = new Scanner (System.in);
         while (menu(st));
         System.out.println ("...Bye");
      } // end main
   
      static boolean menu (Scanner st) {
         System.out.println ("enter integer values, q to quit:");
         String line = st.nextLine();
         if (line.length() == 0) 
            return true; // just  causes crash on next line
            
         Scanner tokens = new Scanner (line).useDelimiter ("[,\\s]+"); // allow comma+space separators
         if (! tokens.hasNextInt())
            if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q")) 
               return false;
            else 
               return true;
         
         BinarySearchTreeND  tree = new BinarySearchTreeND  ();
         while (tokens.hasNextInt()) tree.insert (tokens.nextInt());
         System.out.println ("Tree:\n" + tree);
         System.out.println ("Tree in-order:\n"    + tree.toInOrderString   (tree.root));
         System.out.println ("Tree pre-order:\n"   + tree.toPreOrderString  (tree.root));
         System.out.println ("Tree post-order:\n"  + tree.toPostOrderString (tree.root));
         System.out.println ("Tree level-order:\n" + tree.toLevelOrderString(tree.root));
      
         if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q"))
            return false;
      
         return true;
      } // end menu
      
      public static void integerExample () {
         BinarySearchTreeND < Integer > x = new BinarySearchTreeND < Integer > ();
         int arr [] = {
                       40, 20, 60, 10, 30, 50, 70, 5, 15, 25, 35, 45, 55, 65, 75,
                       60, 45, 50, 40, 55,
                       1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
                      };
         int rem [] = {};
         for (int y: arr) x.insert (y);
      
         System.out.println ("X:\n" + x);
         System.out.println ("X in-order:\n"    + x.toInOrderString(x.root));
         System.out.println ("X pre-order:\n"   + x.toPreOrderString(x.root));
         System.out.println ("X post-order:\n"  + x.toPostOrderString(x.root));
         System.out.println ("X level-order:\n" + x.toLevelOrderString(x.root));
      
         Integer t = x.find(10);
         System.out.println ("find: " + t);
         System.out.println ("find: " + x.find(20));
         System.out.println ("Size: " + x.getSize());
         System.out.println ("MAX: " + x.max());
         for (int y: rem) {
            System.out.println ("Removing: " + y);
            x.remove (y);
            System.out.println ("result:\n" + x);
         }
         System.out.println ("X:\n"  + x);
      } // end integerExample
       
      public static void stringExample () {
         // The following is an example using a user-defined class, see below
         // notice the use of the generic parameter Example
         String [] sa = {"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"};
         BinarySearchTreeND < Example > ex = new BinarySearchTreeND < Example > ();
         for (String s: sa) ex.insert (new Example (s));
         System.out.println ("Example using strings: \n" + ex);
      } // end stringExample
   
   } // end class BinarySearchTreeND

   class BSTNodeND < L extends Comparable< ? super L > > {
      L data;
      BSTNodeND < L > left, right, parent;
      
      BSTNodeND (L d)               {data = d;}             // end data constructor
      BSTNodeND (L d, BSTNodeND  p) {data = d; parent = p;} // end data,parent constructor
      public String toString () {return data.toString();}   // end toString method
   } // end class BSTNodeND
   
// A class that can be used with the BinarySearchTreeND data structure
// Notice the use of the generic parameter Example
// you, of course, will want a more interesting compareTo method
   class Example implements Comparable < Example > {
      String data;
    
      public Example (String d) {data = d;}                              // end String contructor    
      public int compareTo (Example e) {return data.compareTo (e.data);} // end compareTo method
      public String toString () {return data;}                           // end toString
   } // end class Example

ND.