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