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}