001package algs33; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac SplayBST.java 005 * Execution: java SplayBST 006 * 007 * Splay tree. Supports splay-insert, -search, and -delete. 008 * Splays on every operation, regardless of the presence of the associated 009 * key prior to that operation. 010 * 011 * Written by Josh Israel. 012 * 013 *************************************************************************/ 014 015 016public class XSplayBST<K extends Comparable<? super K>, V> { 017 018 private Node<K,V> root; // root of the BST 019 020 // BST helper node data type 021 private static class Node<K,V> { 022 public final K key; // key 023 public V value; // associated data 024 public Node<K,V> left, right; // left and right subtrees 025 026 public Node(K key, V value) { 027 this.key = key; 028 this.value = value; 029 } 030 } 031 032 public boolean contains(K key) { 033 return (get(key) != null); 034 } 035 036 // return value associated with the given key 037 // if no such value, return null 038 public V get(K key) { 039 root = splay(root, key); 040 int cmp = key.compareTo(root.key); 041 if (cmp == 0) return root.value; 042 else return null; 043 } 044 045 /* *********************************************************************** 046 * splay insertion 047 *************************************************************************/ 048 public void put(K key, V value) { 049 // splay key to root 050 if (root == null) { 051 root = new Node<>(key, value); 052 return; 053 } 054 055 root = splay(root, key); 056 057 int cmp = key.compareTo(root.key); 058 059 // Insert new node at root 060 if (cmp < 0) { 061 Node<K,V> n = new Node<>(key, value); 062 n.left = root.left; 063 n.right = root; 064 root.left = null; 065 root = n; 066 } 067 068 // Insert new node at root 069 else if (cmp > 0) { 070 Node<K,V> n = new Node<>(key, value); 071 n.right = root.right; 072 n.left = root; 073 root.right = null; 074 root = n; 075 } 076 077 // It was a duplicate key. Simply replace the value 078 else if (cmp == 0) { 079 root.value = value; 080 } 081 082 } 083 084 /* *********************************************************************** 085 * splay deletion 086 *************************************************************************/ 087 /* This splays the key, then does a slightly modified Hibbard deletion on 088 * the root (if it is the node to be deleted; if it is not, the key was 089 * not in the tree). The modification is that rather than swapping the 090 * root (call it node A) with its successor, it's successor (call it Node<K,V> B) 091 * is moved to the root position by splaying for the deletion key in A's 092 * right subtree. Finally, A's right child is made the new root's right 093 * child. 094 */ 095 public void remove(K key) { 096 if (root == null) return; // empty tree 097 098 root = splay(root, key); 099 100 int cmp = key.compareTo(root.key); 101 102 if (cmp == 0) { 103 if (root.left == null) { 104 root = root.right; 105 } 106 else { 107 Node<K,V> x = root.right; 108 root = root.left; 109 splay(root, key); 110 root.right = x; 111 } 112 } 113 114 // else: it wasn't in the tree to remove 115 } 116 117 118 /* ********************************************************************** 119 * splay function 120 * **********************************************************************/ 121 // splay key in the tree rooted at Node<K,V> h. If a node with that key exists, 122 // it is splayed to the root of the tree. If it does not, the last node 123 // along the search path for the key is splayed to the root. 124 private Node<K,V> splay(Node<K,V> h, K key) { 125 if (h == null) return null; 126 127 int cmp1 = key.compareTo(h.key); 128 129 if (cmp1 < 0) { 130 // key not in tree, so we're done 131 if (h.left == null) { 132 return h; 133 } 134 int cmp2 = key.compareTo(h.left.key); 135 if (cmp2 < 0) { 136 h.left.left = splay(h.left.left, key); 137 h = rotateRight(h); 138 } 139 else if (cmp2 > 0) { 140 h.left.right = splay(h.left.right, key); 141 if (h.left.right != null) 142 h.left = rotateLeft(h.left); 143 } 144 145 if (h.left == null) return h; 146 else return rotateRight(h); 147 } 148 149 else if (cmp1 > 0) { 150 // key not in tree, so we're done 151 if (h.right == null) { 152 return h; 153 } 154 155 int cmp2 = key.compareTo(h.right.key); 156 if (cmp2 < 0) { 157 h.right.left = splay(h.right.left, key); 158 if (h.right.left != null) 159 h.right = rotateRight(h.right); 160 } 161 else if (cmp2 > 0) { 162 h.right.right = splay(h.right.right, key); 163 h = rotateLeft(h); 164 } 165 166 if (h.right == null) return h; 167 else return rotateLeft(h); 168 } 169 170 else return h; 171 } 172 173 174 /* *********************************************************************** 175 * helper functions 176 *************************************************************************/ 177 178 // height of tree (empty tree height = 0) 179 public int height() { return height(root); } 180 private int height(Node<K,V> x) { 181 if (x == null) return 0; 182 return 1 + Math.max(height(x.left), height(x.right)); 183 } 184 185 186 public int size() { 187 return size(root); 188 } 189 190 private int size(Node<K,V> x) { 191 if (x == null) return 0; 192 else return (1 + size(x.left) + size(x.right)); 193 } 194 195 // right rotate 196 private Node<K,V> rotateRight(Node<K,V> h) { 197 Node<K,V> x = h.left; 198 h.left = x.right; 199 x.right = h; 200 return x; 201 } 202 203 // left rotate 204 private Node<K,V> rotateLeft(Node<K,V> h) { 205 Node<K,V> x = h.right; 206 h.right = x.left; 207 x.left = h; 208 return x; 209 } 210 211 // test client 212 public static void main(String[] args) { 213 XSplayBST<Integer, Integer> st1 = new XSplayBST<>(); 214 st1.put(5, 5); 215 st1.put(9, 9); 216 st1.put(13, 13); 217 st1.put(11, 11); 218 st1.put(1, 1); 219 220 221 XSplayBST<String, String> st = new XSplayBST<>(); 222 st.put("www.cs.princeton.edu", "128.112.136.11"); 223 st.put("www.cs.princeton.edu", "128.112.136.12"); 224 st.put("www.cs.princeton.edu", "128.112.136.13"); 225 st.put("www.princeton.edu", "128.112.128.15"); 226 st.put("www.yale.edu", "130.132.143.21"); 227 st.put("www.simpsons.com", "209.052.165.60"); 228 StdOut.println("The size 0 is: " + st.size()); 229 st.remove("www.yale.edu"); 230 StdOut.println("The size 1 is: " + st.size()); 231 st.remove("www.princeton.edu"); 232 StdOut.println("The size 2 is: " + st.size()); 233 st.remove("non-member"); 234 StdOut.println("The size 3 is: " + st.size()); 235 StdOut.println(st.get("www.cs.princeton.edu")); 236 StdOut.println("The size 4 is: " + st.size()); 237 StdOut.println(st.get("www.yale.com")); 238 StdOut.println("The size 5 is: " + st.size()); 239 StdOut.println(st.get("www.simpsons.com")); 240 StdOut.println("The size 6 is: " + st.size()); 241 StdOut.println(); 242 } 243 244}