Binary Search TreeSimplified
By: Nicholas Duchon. |
Outline:
|
Next Page: |
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!
// 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
// 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; // justcauses 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.