BINARY SEARCH TREES

Definition: A binary search tree is a binary tree. It may be empty. If it is not empty then it satisfies the following properties:

• Every element has a key and no other elements have the same key (i.e., the keys are distinct)
• The keys (if any) in the left subtree are smaller than the key in the root
• The keys in the right subtree are larger than the key in the root.
• The left and right subtrees are also binary search trees

Chapter 15 in text (page 568)

Since the definition of binary seach trees is recursive, it is easy to describe recursive methods.

There are always many ways to implement something (even binary trees). An alternate implementation is on my web page [compliments of Jake {insert, delete, display (private find)}].
The text provides non-recursive methods get(Object theKey) (Program 15.4), put(Object theKey, Object theElement) (Program 15.5), remove(Object theKey) (Program 15.6), and ascend()

The book uses Object as the Node, and theKey is also an Object. In the following example, I am just using Node and using "theKey" to be a String with variable name word.

Class Structure: Node, BinTree

class BinTree{
	private Node root;
        private Node curNode;  // depends on implementation

	  // preconditions:  true (user calls correctly)
	  // postconditions: bt = #bt and if n is in bt the value returned is an instance of Node (n) where n.word = x  else value returned is null


	public Node search(String x){}
}

Search/Find/Get

A recursive search method:

public Node search(String x){ if (this.root != null) search (root, x); // initial call to search calls private recursive method else return null; } private Node search(Node curNode, String x){ if (curNode == null) return null; // String x not in tree else if (x.compareTo(curNode.word)==0) return curNode; else if (x.compareTo(curNode.word) < 0) return search(curNode.left, x); else return search(curNode.right, x); }

Why the public and private? (depends on what you want user to be able to do)

This could be done iteratively:

public Node search(String x){ Node curNode = root; // start with binary trees' root while(curNode!=null){ if (x.compareTo(curNode.word)==0) return curNode; if (x.compareTo(curNode.word) < 0) curNode=curNode.left; else curNode=curNode.right; } return null; }

Consider doing a search with Java threads (thread for left subtree, thread for right subtree). (Binary Tree vs Binary Search Tree) Code?

Insert/Put

public boolean insert(String x){ insert (root, x); } //why not do a search here and see if there? // could but I want the parent of the new node // notice how Jay's code differs (findPred() method) private boolean insert(Node curNode, String x){ Node q = root; while(curNode!=null){ q = curNode; //q will soon be the parent of newNode if (x.compareTo(curNode.word)==0) return false; // key value is already there if (x.compareTo(curNode.word) < 0) curNode=curNode.left; else curNode=curNode.right; } // Perform insertion Node newNode=new Node(x); // newnode.left = newnode.right = null; // depends on if constructor does this already // now, was this an empty tree? if (curNode==q) this.root = newNode; else if (x.compareTo(q.word) < 0) q.left = newNode; else q.right = newNode; return true; }

Figure 15.4
Here is code to get started:

public boolean delete(String x){ delete (root, x); } private boolean delete(Node curNode, String x){ Node p = null; // keeps track of parent Node temp1 = null; boolean found = false; while((curNode!=null) && (found == false)) { if (x.compareTo(curNode.word)==0) found = true ; // key value is found at curNode if (x.compareTo(curNode.word) &lt; 0) { p = curNode; //p is the parent of the Node to delete curNode=curNode.left; } else { p = curNode; //p is the parent of the Node to delete curNode=curNode.right; } } if (found == false) { // ERROR MESSAGE node is not in the tree return false; } // Perform deletion if (p == null) // delete root node (curNode) {if (curNode.right != null) { // replace with right child p = curNode; curNode = curNode.right temp1 = p.left ... // replace with left child

Here is more to help consider.