MyBinarySearchTree.java (5398B)
1 package lab11; 2 3 public class MyBinarySearchTree<T extends KeyedItem<KT>, 4 KT extends Comparable<? super KT>> 5 extends BinaryTreeBasis<T> { 6 // inherits isEmpty(), makeEmpty(), getRootItem(), and 7 // the use of the constructors from BinaryTreeBasis 8 9 public MyBinarySearchTree() { 10 } // end default constructor 11 12 public MyBinarySearchTree(T rootItem) { 13 super(rootItem); 14 } // end constructor 15 16 public void setRootItem(T newItem) 17 throws UnsupportedOperationException { 18 throw new UnsupportedOperationException(); 19 } // end setRootItem 20 21 public void insert(T newItem) { 22 root = insertItem(root, newItem); 23 } // end insert 24 25 public T retrieve(KT searchKey) { 26 TreeNode<T> tempTree = root; 27 int compare; 28 while (tempTree != null) { 29 compare = searchKey.compareTo(tempTree.getItem().getKey()); 30 if (compare < 0) { 31 tempTree = tempTree.getLeftChild(); 32 } 33 else if (compare > 0) { 34 tempTree = tempTree.getRightChild(); 35 } 36 else { 37 return tempTree.getItem(); 38 } 39 } 40 return null; 41 } // end retrieve 42 43 public void delete(KT searchKey) throws TreeException { 44 root = deleteItem(root, searchKey); 45 } // end delete 46 47 public void delete(T item) throws TreeException { 48 root = deleteItem(root, item.getKey()); 49 } // end delete 50 51 protected TreeNode<T> insertItem(TreeNode<T> tNode, 52 T newItem) { 53 TreeNode<T> newSubtree; 54 if (tNode == null) { 55 // position of insertion found; insert after leaf 56 // create a new node 57 tNode = new TreeNode<T>(newItem, null, null); 58 return tNode; 59 } // end if 60 T nodeItem = tNode.getItem(); 61 62 // search for the insertion position 63 64 if (newItem.getKey().compareTo(nodeItem.getKey()) < 0) { 65 // search the left subtree 66 newSubtree = insertItem(tNode.getLeftChild(), newItem); 67 tNode.setLeftChild(newSubtree); 68 return tNode; 69 } 70 else { // search the right subtree 71 newSubtree = insertItem(tNode.getRightChild(), newItem); 72 tNode.setRightChild(newSubtree); 73 return tNode; 74 } // end if 75 } // end insertItem 76 77 78 protected TreeNode<T> deleteItem(TreeNode<T> tNode, 79 KT searchKey) { 80 // Calls: deleteNode. 81 TreeNode<T> newSubtree; 82 if (tNode == null) { 83 throw new TreeException("TreeException: Item not found"); 84 } 85 else { 86 T nodeItem = tNode.getItem(); 87 if (searchKey.compareTo(nodeItem.getKey()) == 0) { 88 // item is in the root of some subtree 89 tNode = deleteNode(tNode); // delete the item 90 } 91 // else search for the item 92 else if (searchKey.compareTo(nodeItem.getKey()) < 0) { 93 // search the left subtree 94 newSubtree = deleteItem(tNode.getLeftChild(), searchKey); 95 tNode.setLeftChild(newSubtree); 96 } 97 else { // search the right subtree 98 newSubtree = deleteItem(tNode.getRightChild(), searchKey); 99 tNode.setRightChild(newSubtree); 100 } // end if 101 } // end if 102 return tNode; 103 } // end deleteItem 104 105 protected TreeNode<T> deleteNode(TreeNode<T> tNode) { 106 // Algorithm note: There are four cases to consider: 107 // 1. The tNode is a leaf. 108 // 2. The tNode has no left child. 109 // 3. The tNode has no right child. 110 // 4. The tNode has two children. 111 // Calls: findLeftmost and deleteLeftmost 112 T replacementItem; 113 114 // test for a leaf 115 if ( (tNode.getLeftChild() == null) && 116 (tNode.getRightChild() == null) ) { 117 return null; 118 } // end if leaf 119 120 // test for no left child 121 else if (tNode.getLeftChild() == null) { 122 return tNode.getRightChild(); 123 } // end if no left child 124 125 // test for no right child 126 else if (tNode.getRightChild() == null) { 127 return tNode.getLeftChild(); 128 } // end if no right child 129 130 // there are two children: 131 // retrieve and delete the inorder successor 132 else { 133 replacementItem = findLeftmost(tNode.getRightChild()); 134 tNode.setItem(replacementItem); 135 tNode.setRightChild(deleteLeftmost(tNode.getRightChild())); 136 return tNode; 137 } // end if 138 } // end deleteNode 139 140 protected T findLeftmost(TreeNode<T> tNode) { 141 TreeNode<T> tempNode = tNode; 142 if (tempNode != null) { 143 while (tempNode.getLeftChild() != null) { 144 tempNode = tNode.getLeftChild(); 145 } 146 } 147 return tempNode.getItem(); 148 } // end findLeftmost 149 150 protected TreeNode<T> deleteLeftmost(TreeNode<T> tNode) { 151 if (tNode.getLeftChild() == null) { 152 return tNode.getRightChild(); 153 } 154 else { 155 tNode.setLeftChild(deleteLeftmost(tNode.getLeftChild())); 156 return tNode; 157 } // end if 158 } // end deleteLeftmost 159 160 } // end MyBinarySearchTree