Binary Search Trees

A binary search tree is a special case of a binary tree

• all the descendants ( the child node and all its children) to the left of each node have smaller data values than the node itself.
• And the descendants to the right have larger data values.

Binary Search Tree

We can only create a binary search tree of objects that are comparable in some fashion.

Here is a diagram of a binary search tree of integers.

Binary Search Tree

 

Here is a diagram of a binary search tree of Strings.

 

Binary Search Tree

This diagram has more detail

Not a Binary Search Tree

This is not a binary search tree

 

Romeo could be the left child

 

Implementing a Binary Search Tree

• Implement a class for the tree containing a reference to the root node
• Implement an inner class for the nodes
  • A node contains two references (to left and right child nodes)
  • A node contains a data field
  • The data field must be of type Comparable, so that you can compare the values in order to place them in the correct position in the binary search tree

Implementing a Binary Search Tree

public class BinarySearchTree 
{  
   private Node root; 
  
   public BinarySearchTree() { . . . } 
   public void add(Comparable obj) { . . . } 
   . . . 
   class Node 
   {  
      public Comparable data; 
      public Node left; 
      public Node right;

      public void addNode(Node newNode) { . . . } 
      . . . 
   } 
}

Insertion

• Use a recursive algorithm
• If you encounter a non-null node reference, look at its data value
  • If the data value of that node is larger than the one you want to insert,
    continue the process with the left subtree
  • If the existing data value is smaller, continue the process with the right subtree
• If you encounter a null node pointer, replace it with the new node

Insersion Example

BinarySearchTree tree = new BinarySearchTree();
tree.add("Juliet"); 
tree.add("Tom"); 
tree.add("Diana"); 
tree.add("Harry"); 
tree.add("Romeo"); 

Class Question 1

Which tree is the result of inserting F R E D into an empty binary search tree

1.    F
     / \
    D   R
     \
      E

2.    F
       \ 
        R
       / 
      E
     /
    D

3.     F
      / \
     E   R
    /  
   D   

4. Something else

Implementing Insertion

add method in the BinarySearchTree Class

public void add(Comparable obj) 
{  
   Node newNode = new Node(); 
   newNode.data = obj; 
   newNode.left = null; 
   newNode.right = null; 
   if (root == null) root = newNode; 
   else root.addNode(newNode); 
}

Implementing Insertion

addNode method of the Node class

class Node
{
   . . .
   public void addNode(Node newNode)
   {
      int comp = newNode.data.compareTo(data);
      if (comp < 0)
      {
         if (left == null) { left = newNode; }
         else { left.addNode(newNode); }
      }
      else if (comp > 0)
      {
         if (right == null) { right = newNode; }
         else { right.addNode(newNode); }
      }
   }
   . . .
}

Searching for an Element

• If the target equals the root element
  • you found it
• Else if target is less than root
  • search the left subtree
• Otherwise, search the right subtree

Searching

• Similar to a binary search
  • The amount left to search is cut in half each time
• O(log n) provided the tree is balanced

Class Question 2

Assume 1000 random integers were inserted into a BST. What is the maximum comparisons needed to find whether the integer 42 is among them?

1. 1000
2. 512
3. 10
4. 1

Removal

• First find the element to remove
  • remember its parent
• If the element to be removed is leaf, just remove it
• If the element to be removed has only one child, that child replaces the node to be removed. (That's why you need ot remember the parent)

Removal

• Hard part: Removing node with two children
• Find smallest child in right subtree
• That node has at most one child (a right child)
  • Copy the value of that node to the node to be removed
  • Remove that node (as in the previous slide)

 

Class Question 3

Consider this BST:

          C
         /  \
        A   G
           / \
          D   K

What is the result of removing C?

1.      G
       / \
      A   K
         /
        D

2.      A
         \
          G
         / \
        D   K

3.      D
       / \
      A   G
           \
            K

4. Someting else

Efficiency

• Assumption: Balanced tree
• Finding an element: O(log n)
• Adding an element
  • First find the element: O(log n)
  • The a few fixed steps
  • So it is O(log n)
• Removing an element
  • Finding node to be removed: O(log n)
  • Finding smallest child in right subtree: O(log n)
  • O(log n) (if tree is balanced)

Class Question 4

You need to keep a set of lots of objects of class X. You don't care about traversal in sorted order, but you want maximum efficiency. What should you choose, and why?

1. A hash table because its add/remove/find operations are O(1)+
2. A re-balancing BST because its add/remove/find operations are guaranteed to be O(log n)
3. A hash table because it is easier to come up with a hashCode method for X than a compareTo method
4. A re-balancing BST because it is easier to come up with a compareTo method for X than a hashCode method