API tools faq
paste
Guest User

Untitled

a guest
Feb 20th, 2018
57
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.82 KB | None | 0 0
raw download clone embed print report
  1. package adt.splaytree;
  2.  
  3. import java.util.Arrays;
  4.  
  5. import adt.avltree.AVLTreeImpl;
  6. import adt.bst.BSTNode;
  7.  
  8. public class SplayTreeImpl<K extends Comparable<? super K>, V> extends AVLTreeImpl<K, V> implements
  9.         SplayTree<K, V> {
  10.    
  11.    
  12.  
  13.      private void splay(BSTNode<K,V> node){
  14.          if (node != null && node.getParent() != null) {
  15.                  if (node.getParent().getKey() == root.getKey()) {
  16.                          if (node.getParent().getLeft().getKey() == node.getKey())
  17.                                  rightRotation(node.getParent());
  18.                          else if (node.getParent().getRight().getKey() == node.getKey())
  19.                                  leftRotation(node.getParent());
  20.                  } else if (node.getKey() == node.getParent().getLeft().getKey()) {
  21.                          if (node.getParent().getKey() == node.getParent().getParent().getLeft().getKey()) {
  22.                                  rightRotation(node.getParent().getParent());
  23.                                  rightRotation(node.getParent());
  24.                          } else {
  25.                                  rightRotation(node.getParent());
  26.                                  leftRotation(node.getParent());
  27.                          }
  28.                  } else if (node.getKey() == node.getParent().getRight().getKey()) {
  29.                          if (node.getParent().getKey() == node.getParent().getParent().getRight().getKey()) {
  30.                                  leftRotation(node.getParent().getParent());
  31.                                  leftRotation(node.getParent());
  32.                          } else {
  33.                                  leftRotation(node.getParent());
  34.                                  rightRotation(node.getParent());
  35.                          }
  36.                  }
  37.          }
  38.  }
  39.    
  40.     public BSTNode<K, V> splaySearch(K key){
  41.  
  42.         BSTNode<K, V> node = search(key);
  43.         if(!node.isEmpty()){
  44.             splay(node);
  45.         }else{
  46.             splay(node.getParent());
  47.         }
  48.         return node;
  49.     }
  50.    
  51.      @Override
  52.      public void insert(K key, V value) {
  53.              recursiveInsertion(root, key, value);
  54.      }
  55.  
  56.      private void recursiveInsertion(BSTNode<K, V> node, K key, V value) {
  57.              if (node.isEmpty()) {
  58.                      node.setKey(key);
  59.                      node.setValue(value);
  60.                      node.setLeft(new BSTNode<K, V>());
  61.                      node.getLeft().setParent(node);
  62.                      node.setRight(new BSTNode<K, V>());
  63.                      node.getRight().setParent(node);
  64.                      splay(node);
  65.  
  66.              } else {
  67.                      if (key.compareTo(node.getKey()) < 0) {
  68.                              recursiveInsertion(node.getLeft(), key, value);
  69.                      } else if (key.compareTo(node.getKey()) > 0) {
  70.                              recursiveInsertion(node.getRight(), key, value);
  71.                      }
  72.              }
  73.  
  74.      }
  75.    
  76.    
  77.    
  78.  
  79.     @Override
  80.     public void remove(K key) {
  81.         BSTNode<K, V> node = search(key);
  82.         removeAux(node);
  83.     }
  84.    
  85.     private void removeAux(BSTNode<K,V> node){
  86.         if (!node.isEmpty()){
  87.             if (node.getLeft().isEmpty() && node.getRight().isEmpty()){
  88.                 node.setKey(null);
  89.                 node.setValue(null);               
  90.             } else{            
  91.                 if (!node.getLeft().isEmpty() || !node.getRight().isEmpty()){
  92.                     if (!node.equals(root)){
  93.                         if (node.getParent().getLeft().equals(node)){
  94.                             if (!node.getLeft().isEmpty()){
  95.                                 node.getParent().setLeft(node.getLeft());
  96.  
  97.                             } else{
  98.                                 node.getParent().setLeft(node.getRight());
  99.  
  100.                             }
  101.                         } else {
  102.                             if (!node.getLeft().isEmpty()){
  103.                                 node.getParent().setRight(node.getLeft());
  104.  
  105.                             } else{
  106.                                 node.getParent().setRight(node.getRight());
  107.  
  108.                             }                      
  109.                         }
  110.                     } else{
  111.                         if (!root.getLeft().isEmpty() && root.getRight().isEmpty()){
  112.                             root = root.getLeft();
  113.                             root.setParent(null);
  114.                         } else{
  115.                             if (root.getLeft().isEmpty() && !root.getRight().isEmpty()) {
  116.                                 root = root.getRight();
  117.                                 root.setParent(null);
  118.                             } else{
  119.                                 BSTNode<K, V> sucessor = sucessor(node);
  120.                                 node.setKey(sucessor.getKey());
  121.                                 node.setValue(sucessor.getValue());
  122.                                 removeAux(sucessor);                                                   
  123.                             }
  124.                         }
  125.                     }  
  126.                 } else{
  127.                     if (node.getParent() == null){
  128.                         node.setKey(null);
  129.                         node.setValue(null);
  130.                     }
  131.                     BSTNode<K, V> sucessor = sucessor(node);
  132.                     node.setKey(sucessor.getKey());
  133.                     node.setValue(sucessor.getValue());
  134.                     removeAux(sucessor);                   
  135.                 }
  136.             }
  137.         }
  138.     }
  139.  
  140.     public void splayRemove(K key){
  141.         BSTNode<K, V> node = search(key);
  142.         if(!node.isEmpty()){
  143.             splay(node.getParent());
  144.         }else{
  145.             this.remove(node.getKey());
  146.             splay(node.getParent());
  147.         }
  148.     }
  149.    
  150.    
  151.  
  152.     public Comparable findMin() {
  153.         BSTNode aux = root;
  154.         if(root == null) return null;
  155.         while(aux.left != null) aux = aux.left;
  156.         splay(aux);
  157.         return aux.key;
  158.     }
  159.  
  160.     /**
  161.      * Find the largest item in the tree.
  162.      */
  163.     public Comparable findMax() {
  164.         BSTNode aux = root;
  165.         if(root == null) return null;
  166.         while(aux.right != null) aux = aux.right;
  167.         splay(aux);
  168.         return aux.key;
  169.     }
  170.     public static void main(String[] args) {
  171. //      SplayTreeImpl<Integer, Integer> arvore = new SplayTreeImpl<Integer, Integer>();
  172. //      arvore.insert(0, 0);
  173. //      arvore.insert(1, 1);
  174. //      System.out.println(Arrays.toString(arvore.preOrder()));
  175. //      System.out.println(arvore.search(0));
  176. //      System.out.println(Arrays.toString(arvore.preOrder()));
  177. //      arvore.insert(4, 4);
  178. //      System.out.println(Arrays.toString(arvore.preOrder()));
  179. //      arvore.insert(2, 2);
  180. //      System.out.println(Arrays.toString(arvore.preOrder()));
  181. //      arvore.insert(3, 3);
  182. //      System.out.println(Arrays.toString(arvore.preOrder()));
  183. //      System.out.println(arvore.search(1));
  184. //      System.out.println(Arrays.toString(arvore.preOrder()));
  185. //      System.out.println(arvore.search(0));
  186. //      System.out.println(Arrays.toString(arvore.preOrder()));
  187. //      arvore.insert(10, 10);
  188. //      arvore.insert(5, 5);
  189. //      arvore.insert(6, 6);
  190. //      arvore.insert(9, 9);
  191. //      System.out.println(Arrays.toString(arvore.preOrder()));
  192.        
  193.         SplayTreeImpl<Integer,Integer> node= new SplayTreeImpl<Integer,Integer>();
  194. //        for(int i = 0;i<11;i++){
  195. //                node.insert(i, i);
  196. //        }
  197. //        System.out.println(Arrays.toString(node.preOrder()));
  198.        
  199. //      SplayTreeImpl<Integer, Integer> arvore = new SplayTreeImpl<Integer, Integer>();
  200. //        arvore.insert(0, 0);
  201. //        arvore.insert(1, 1);
  202. //        System.out.println(Arrays.toString(arvore.preOrder()));
  203. //        System.out.println(arvore.search(0));
  204. //        System.out.println(Arrays.toString(arvore.preOrder()));
  205. //        arvore.insert(4, 4);
  206. //        System.out.println(Arrays.toString(arvore.preOrder()));
  207. //        arvore.insert(2, 2);
  208. //        System.out.println(Arrays.toString(arvore.preOrder()));
  209. //        arvore.insert(3, 3);
  210. //        System.out.println(Arrays.toString(arvore.preOrder()));
  211. //        System.out.println(arvore.search(1));
  212. //        System.out.println(Arrays.toString(arvore.preOrder()));
  213. //        System.out.println(arvore.search(0));
  214. //        System.out.println(Arrays.toString(arvore.preOrder()));
  215. //        arvore.insert(10, 10);
  216. //        arvore.insert(5, 5);
  217. //        arvore.insert(6, 6);
  218. //        arvore.insert(9, 9);
  219. //        System.out.println(Arrays.toString(arvore.preOrder()));
  220.        
  221.          node.insert(10, 10);
  222.          node.insert(0, 0);
  223.          node.insert(1, 1);
  224.          node.insert(2, 2);
  225.          node.insert(3, 3);
  226.          node.insert(4, 4);
  227.          node.insert(5, 5);
  228.          node.insert(6,6);
  229.          node.insert(7, 7);
  230.          node.insert(8,8);
  231.          node.insert(9, 9);
  232.  
  233.  
  234. }
  235.  
  236.         }
Add Comment
Please, Sign In to add comment
Public Pastes
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!