|
| 1 | +// Java implementation for above approach |
| 2 | +class Splay |
| 3 | +{ |
| 4 | + |
| 5 | +// An AVL tree node |
| 6 | +static class node{ |
| 7 | + |
| 8 | + int key; |
| 9 | + node left, right; |
| 10 | +}; |
| 11 | + |
| 12 | +static node newNode(int key){ |
| 13 | + node Node = new node(); |
| 14 | + Node.key = key; |
| 15 | + Node.left = Node.right = null; |
| 16 | + return (Node); |
| 17 | +} |
| 18 | + |
| 19 | +// A utility function to right |
| 20 | +// rotate subtree rooted with y |
| 21 | +// See the diagram given above. |
| 22 | +static node rightRotate(node x) |
| 23 | +{ |
| 24 | + node y = x.left; |
| 25 | + x.left = y.right; |
| 26 | + y.right = x; |
| 27 | + return y; |
| 28 | +} |
| 29 | + |
| 30 | +// A utility function to left |
| 31 | +// rotate subtree rooted with x |
| 32 | +// See the diagram given above. |
| 33 | +static node leftRotate(node x) |
| 34 | +{ |
| 35 | + node y
10000
= x.right; |
| 36 | + x.right = y.left; |
| 37 | + y.left = x; |
| 38 | + return y; |
| 39 | +} |
| 40 | + |
| 41 | +// This function brings the key at |
| 42 | +// root if key is present in tree. |
| 43 | +// If key is not present, then it |
| 44 | +// brings the last accessed item at |
| 45 | +// root. This function modifies the |
| 46 | +// tree and returns the new root |
| 47 | +static node splay(node root, int key) |
| 48 | +{ |
| 49 | + // Base cases: root is null or |
| 50 | + // key is present at root |
| 51 | + if (root == null || root.key == key) |
| 52 | + return root; |
| 53 | + |
| 54 | + // Key lies in left subtree |
| 55 | + if (root.key > key) |
| 56 | + { |
| 57 | + // Key is not in tree, we are done |
| 58 | + if (root.left == null) return root; |
| 59 | + |
| 60 | + // Zig-Zig (Left Left) |
| 61 | + if (root.left.key > key) |
| 62 | + { |
| 63 | + // First recursively bring the |
| 64 | + // key as root of left-left |
| 65 | + root.left.left = splay(root.left.left, key); |
| 66 | + |
| 67 | + // Do first rotation for root, |
| 68 | + // second rotation is done after else |
| 69 | + root = rightRotate(root); |
| 70 | + } |
| 71 | + else if (root.left.key < key) // Zig-Zag (Left Right) |
| 72 | + { |
| 73 | + // First recursively bring |
| 74 | + // the key as root of left-right |
| 75 | + root.left.right = splay(root.left.right, key); |
| 76 | + |
| 77 | + // Do first rotation for root.left |
| 78 | + if (root.left.right != null) |
| 79 | + root.left = leftRotate(root.left); |
| 80 | + } |
| 81 | + |
| 82 | + // Do second rotation for root |
| 83 | + return (root.left == null) ? |
| 84 | + root : rightRotate(root); |
| 85 | + } |
| 86 | + else // Key lies in right subtree |
| 87 | + { |
| 88 | + // Key is not in tree, we are done |
| 89 | + if (root.right == null) return root; |
| 90 | + |
| 91 | + // Zag-Zig (Right Left) |
| 92 | + if (root.right.key > key) |
| 93 | + { |
| 94 | + // Bring the key as root of right-left |
| 95 | + root.right.left = splay(root.right.left, key); |
| 96 | + |
| 97 | + // Do first rotation for root.right |
| 98 | + if (root.right.left != null) |
| 99 | + root.right = rightRotate(root.right); |
| 100 | + } |
| 101 | + else if (root.right.key < key)// Zag-Zag (Right Right) |
| 102 | + { |
| 103 | + // Bring the key as root of |
| 104 | + // right-right and do first rotation |
| 105 | + root.right.right = splay(root.right.right, key); |
| 106 | + root = leftRotate(root); |
| 107 | + } |
| 108 | + |
| 109 | + // Do second rotation for root |
| 110 | + return (root.right == null) ? |
| 111 | + root : leftRotate(root); |
| 112 | + } |
| 113 | +} |
| 114 | + |
| 115 | +// The search function for Splay tree. |
| 116 | +// Note that this function returns the |
| 117 | +// new root of Splay Tree. If key is |
| 118 | +// present in tree then, it is moved to root. |
| 119 | +static node search(node root, int key) |
| 120 | +{ |
| 121 | + return splay(root, key); |
| 122 | +} |
| 123 | + |
| 124 | +// A utility function to print |
| 125 | +// preorder traversal of the tree. |
| 126 | +// The function also prints height of every node |
| 127 | +static void preOrder(node root) |
| 128 | +{ |
| 129 | + if (root != null) |
| 130 | + { |
| 131 | + System.out.print(root.key + " "); |
| 132 | + preOrder(root.left); |
| 133 | + preOrder(root.right); |
| 134 | + } |
| 135 | +} |
| 136 | + |
| 137 | +// Driver code |
| 138 | +public static void main(String[] args) |
| 139 | +{ |
| 140 | + node root = newNode(100); |
| 141 | + root.left = newNode(50); |
| 142 | + root.right = newNode(200); |
| 143 | + root.left.left = newNode(40); |
| 144 | + root.left.left.left = newNode(30); |
| 145 | + root.left.left.left.left = newNode(20); |
| 146 | + |
| 147 | + root = search(root, 20); |
| 148 | + System.out.print("Preorder traversal of the" + |
| 149 | + " modified Splay tree is \n"); |
| 150 | + preOrder(root); |
| 151 | +} |
| 152 | +} |
| 153 | + |
| 154 | +// This code is contributed by 29AjayKumar |
0 commit comments