Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Splay Tree Search Implementation
- public class SplayBST {
- Node root;
- int count;
- int level = 0;
- boolean found = false;
- public SplayBST() {
- root = null;
- count = 0;
- }
- public String searchIt(String x) {
- //after finishing search method I need to check if splaySearch exists then don't insert just splay it
- splaySearch(root, x);
- if (this.found == true) {
- this.found = false;
- return x;
- }
- else {
- return null;
- }
- }
- Node splaySearch(Node h, String x) {
- if (h == null) {
- return null;
- }
- if (x.compareTo(h.value) < 0) {
- try {
- if (x.compareTo(h.left.value) < 0) {
- h.left.left = splaySearch(h.left.left, x);
- h = rotateRight(h);
- } else if (x.compareTo(h.left.value) > 0) {
- h.left.right = splaySearch(h.left.right, x);
- h.left = rotateLeft(h.left);
- }
- else {
- this.found = true;
- return h.left;
- }
- return rotateRight(h);
- }
- catch (NullPointerException ex) {
- return null;
- }
- }
- else { //basically x.compareTo(h.value)>0
- try {
- if (x.compareTo(h.right.value) > 0) {
- h.right.right = splaySearch(h.right.right, x);
- h = rotateLeft(h);
- } else if (x.compareTo(h.right.value) < 0) {
- h.right.left = splaySearch(h.right.left, x);
- h.right = rotateRight(h.right);
- }
- else {
- this.found = true;
- return h.right;
- }
- return rotateLeft(h);
- }
- catch (NullPointerException ex) {
- return null;
- }
- }
- }
- Node rotateLeft(Node h) {
- Node x = h.right;
- h.right = x.left;
- x.left = h;
- return x;
- }
- Node rotateRight(Node h) {
- Node x = h.left;
- h.left = x.right;
- x.right = h;
- return x;
- }
- class Node {
- Node left;
- Node right;
- String value;
- int pos;
- public Node(String x) {
- left = null;
- right = null;
- value = x;
- }
- }
- }
Add Comment
Please, Sign In to add comment