BinarySearchTree.java.html

  1  /**
  2     This class implements a binary search tree whose
  3     nodes hold objects that implement the Comparable
  4     interface.
  5  */
  6  public class BinarySearchTree
  7  {  
  8     private Node root;
  9  
 10     /**
 11        Constructs an empty tree.
 12     */
 13     public BinarySearchTree()
 14     {  
 15        root = null;
 16     }
 17     
 18     /**
 19        Inserts a new node into the tree.
 20        @param obj the object to insert
 21     */
 22     public void add(Comparable obj) 
 23     {  
 24        Node newNode = new Node();
 25        newNode.data = obj;
 26        newNode.left = null;
 27        newNode.right = null;
 28        if (root == null) { root = newNode; }
 29        else { root.addNode(newNode); }
 30     }
 31  
 32     /**
 33        Tries to find an object in the tree.
 34        @param obj the object to find
 35        @return true if the object is contained in the tree
 36     */
 37     public boolean find(Comparable obj)
 38     {
 39        Node current = root;
 40        while (current != null)
 41        {
 42           int d = current.data.compareTo(obj);
 43           if (d == 0) { return true; }
 44           else if (d > 0) { current = current.left; }
 45           else { current = current.right; }
 46        }
 47        return false;
 48     }
 49     
 50     /**
 51        Tries to remove an object from the tree. Does nothing
 52        if the object is not contained in the tree.
 53        @param obj the object to remove
 54     */
 55     public void remove(Comparable obj)
 56     {
 57        // Find node to be removed
 58  
 59        Node toBeRemoved = root;
 60        Node parent = null;
 61        boolean found = false;
 62        while (!found && toBeRemoved != null)
 63        {
 64           int d = toBeRemoved.data.compareTo(obj);
 65           if (d == 0) { found = true; }
 66           else 
 67           {
 68              parent = toBeRemoved;
 69              if (d > 0) { toBeRemoved = toBeRemoved.left; }
 70              else { toBeRemoved = toBeRemoved.right; }
 71           }
 72        }
 73  
 74        if (!found) { return; }
 75  
 76        // toBeRemoved contains obj
 77  
 78        // If one of the children is empty, use the other
 79  
 80        if (toBeRemoved.left == null || toBeRemoved.right == null)
 81        {
 82           Node newChild;
 83           if (toBeRemoved.left == null) 
 84           {
 85              newChild = toBeRemoved.right;
 86           }
 87           else 
 88           {
 89              newChild = toBeRemoved.left;
 90           }
 91  
 92           if (parent == null) // Found in root
 93           {
 94              root = newChild;
 95           }
 96           else if (parent.left == toBeRemoved)
 97           {
 98              parent.left = newChild;
 99           }
100           else 
101           {
102              parent.right = newChild;
103           }
104           return;
105        }
106        
107        // Neither subtree is empty
108  
109        // Find smallest element of the right subtree
110  
111        Node smallestParent = toBeRemoved;
112        Node smallest = toBeRemoved.right;
113        while (smallest.left != null)
114        {
115           smallestParent = smallest;
116           smallest = smallest.left;
117        }
118  
119        // smallest contains smallest child in right subtree
120           
121        // Move contents, unlink child
122  
123        toBeRemoved.data = smallest.data;
124        if (smallestParent == toBeRemoved) 
125        {
126           smallestParent.right = smallest.right; 
127        }
128        else 
129        {
130           smallestParent.left = smallest.right; 
131        }
132     }
133     
134     /**
135        Prints the contents of the tree in sorted order.
136     */
137     public void print()
138     {  
139        print(root);
140        System.out.println();
141     }  
142  
143     /**
144        Prints a node and all of its descendants in sorted order.
145        @param parent the root of the subtree to print
146     */
147     private static void print(Node parent)
148     {  
149        if (parent == null) { return; }
150        print(parent.left);
151        System.out.print(parent.data + " ");
152        print(parent.right);
153     }
154  
155     /**
156        A node of a tree stores a data item and references
157        to the left and right child nodes.
158     */
159     class Node
160     {  
161        public Comparable data;
162        public Node left;
163        public Node right;
164  
165        /**
166           Inserts a new node as a descendant of this node.
167           @param newNode the node to insert
168        */
169        public void addNode(Node newNode)
170        {  
171           int comp = newNode.data.compareTo(data);
172           if (comp < 0)
173           {  
174              if (left == null) { left = newNode; }
175              else { left.addNode(newNode); }
176           }
177           else if (comp > 0)
178           {  
179              if (right == null) { right = newNode; }
180              else { right.addNode(newNode); }
181           }
182        }
183     }
184  }
185  
186  
187