SHARE
TWEET

Untitled

a guest Jan 12th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Splay Tree Search Implementation
  2. public class SplayBST {
  3.     Node root;
  4.     int count;
  5.     int level = 0;
  6.     boolean found = false;
  7.     public SplayBST() {
  8.         root = null;
  9.         count = 0;
  10.     }
  11.  
  12. public String searchIt(String x) {
  13.     //after finishing search method I need to check if splaySearch exists then don't insert just splay it
  14.     splaySearch(root, x);
  15.     if (this.found == true) {
  16.         this.found = false;
  17.         return x;
  18.     }
  19.     else {
  20.         return null;
  21.     }
  22. }
  23.  
  24.  
  25.     Node splaySearch(Node h, String x) {
  26.         if (h == null) {
  27.             return null;
  28.         }
  29.         if (x.compareTo(h.value) < 0) {
  30.             try {
  31.             if (x.compareTo(h.left.value) < 0) {
  32.                 h.left.left = splaySearch(h.left.left, x);
  33.                 h = rotateRight(h);
  34.             } else if (x.compareTo(h.left.value) > 0) {
  35.                 h.left.right = splaySearch(h.left.right, x);
  36.                 h.left = rotateLeft(h.left);
  37.             }
  38.             else {
  39.                 this.found = true;
  40.                 return h.left;
  41.             }
  42.             return rotateRight(h);
  43.             }
  44.         catch (NullPointerException ex) {
  45.             return null;
  46.             }
  47.         }
  48.  
  49.         else { //basically x.compareTo(h.value)>0
  50.             try {
  51.             if (x.compareTo(h.right.value) > 0) {
  52.                 h.right.right = splaySearch(h.right.right, x);                
  53.                 h = rotateLeft(h);
  54.             } else if (x.compareTo(h.right.value) < 0) {
  55.                 h.right.left = splaySearch(h.right.left, x);
  56.                 h.right = rotateRight(h.right);
  57.             }
  58.             else {
  59.                 this.found = true;
  60.                 return h.right;
  61.             }
  62.             return rotateLeft(h);
  63.             }
  64.             catch (NullPointerException ex) {
  65.                 return null;
  66.             }
  67.         }
  68.     }
  69.  
  70.  
  71.     Node rotateLeft(Node h) {
  72.         Node x = h.right;
  73.         h.right = x.left;
  74.         x.left = h;
  75.         return x;
  76.     }
  77.     Node rotateRight(Node h) {
  78.         Node x = h.left;
  79.         h.left = x.right;
  80.         x.right = h;
  81.         return x;
  82.     }
  83.  
  84.  
  85.     class Node {
  86.         Node left;
  87.         Node right;
  88.         String value;
  89.         int pos;
  90.         public Node(String x) {
  91.             left = null;
  92.             right = null;
  93.             value = x;
  94.         }
  95.     }
  96. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top