daily pastebin goal
26%
SHARE
TWEET

Untitled

a guest Dec 16th, 2018 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ru.mail.polis.collections.set.sorted.todo;
  2.  
  3. import ru.mail.polis.collections.set.sorted.ISelfBalancingSortedTreeSet;
  4. import ru.mail.polis.collections.set.sorted.UnbalancedTreeException;
  5.  
  6. import java.util.Comparator;
  7. import java.util.NoSuchElementException;
  8. import java.util.Objects;
  9.  
  10. /**
  11.  * A AVL tree based {@link ISelfBalancingSortedTreeSet} implementation.
  12.  *
  13.  * <a href="https://en.wikipedia.org/wiki/AVL_tree>AVL_tree</a>
  14.  *
  15.  * @param <E> the type of elements maintained by this set
  16.  */
  17. @SuppressWarnings("unchecked")
  18.  
  19. public class AVLTree<E extends Comparable<E>> implements ISelfBalancingSortedTreeSet<E> {
  20.  
  21.  
  22.     protected static class AVLNode<E extends  Comparable<E>> {
  23.         E value;
  24.         AVLNode<E> left;
  25.         AVLNode<E> right;
  26.         int height = 1;
  27.  
  28.         AVLNode(E value){
  29.             this.value = value;
  30.         }
  31.     }
  32.  
  33.  
  34.     public AVLTree() {
  35.         this(Comparator.naturalOrder());
  36.     }
  37.  
  38.     public AVLTree(Comparator<E> comparator) {
  39.         if (comparator == null) {
  40.             throw new NullPointerException();
  41.         }
  42.         this.comparator = Objects.requireNonNull(comparator, "comparator");
  43.         length = 0;
  44.     }
  45.  
  46.  
  47.  
  48.     protected final Comparator<E> comparator;
  49.     protected AVLNode<E> root;
  50.     protected int length;
  51.  
  52.     protected int getHeight(AVLNode current){
  53.         if(current == null){
  54.             return 0;
  55.         }
  56.         return current.height;
  57.     }
  58.  
  59.  
  60.     protected   AVLNode rightRotate(AVLNode current){
  61.         AVLNode b = current.left;
  62.         current.left = b.right;
  63.  
  64.         //rotate
  65.         b.right = current;
  66.  
  67.         //upd
  68.         current.height = Math.max(getHeight(current.left), getHeight(current.right)) + 1;
  69.         b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1;
  70.  
  71.         return b;
  72.  
  73.     }
  74.  
  75.     protected AVLNode leftRotate(AVLNode current){
  76.         AVLNode b = current.right;
  77.         current.right = b.left;
  78.  
  79.         //rotate
  80.         b.left = current;
  81.  
  82.  
  83.         //upd
  84.         current.height = Math.max(getHeight(current.left), getHeight(current.right)) + 1;
  85.         b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1;
  86.  
  87.         return b;
  88.     }
  89.  
  90.  
  91.     protected void insert(E value){
  92.         this.root = insert(this.root, value);
  93.     }
  94.  
  95.  
  96.     protected AVLNode insert(AVLNode current, E value){
  97.         if(current == null){
  98.            return new AVLNode(value);
  99.         }
  100.         if(comparator.compare((E) current.value, value) > 0){
  101.             current.left = insert(current.left,value);
  102.         }
  103.         else if(comparator.compare((E) current.value, value) < 0){
  104.             current.right = insert(current.right, value);
  105.         }
  106.  
  107.         current.height = Math.max(getHeight(current.left), getHeight(current.right)) + 1;
  108.  
  109.         int getBalance = getBalance(current);
  110.  
  111.  
  112.         /*if balanceFactor not 0 or 1, we have to do balance our Tree*/
  113.  
  114.         //LL Case
  115.         if(getBalance > 1 && comparator.compare(value, (E) current.left.value) < 0){
  116.             return rightRotate(current);
  117.         }
  118.         //RR Case
  119.         if(getBalance < -1 && comparator.compare(value, (E) current.right.value) > 0){
  120.             return leftRotate(current);
  121.         }
  122.         // LR Case
  123.         if (getBalance > 1 && comparator.compare(value, (E) current.left.value) > 0) {
  124.             current.left = leftRotate(current.left);
  125.             return rightRotate(current);
  126.         }
  127.  
  128.         // RL Case
  129.         if (getBalance < -1 && comparator.compare(value, (E) current.right.value) < 0) {
  130.             current.right = rightRotate(current.right);
  131.             return leftRotate(current);
  132.         }
  133.  
  134.  
  135.         return current;
  136.     }
  137.  
  138.     /*This is a different between left height and right height of AVL Node */
  139.     protected int getBalance(AVLNode current){ // aka balanceFactor
  140.         if(current == null){
  141.             return  0;
  142.         }
  143.         return getHeight(current.left) - getHeight(current.right);
  144.     }
  145.  
  146.     protected AVLNode find(AVLNode current, E value){
  147.         if(current == null || current.value == null || comparator.compare((E) current.value,value) == 0) {
  148.             return current;
  149.         }
  150.         if(comparator.compare((E) current.value, value) > 0){
  151.             return find(current.left, value);
  152.         }
  153.         else{
  154.             return find(current.right,value);
  155.         }
  156.     }
  157.  
  158.  
  159.     protected AVLNode treeMin(AVLNode current){
  160.         while(current.left != null){
  161.             current = current.left;
  162.         }
  163.         return current;
  164.     }
  165.     protected AVLNode treeMax(AVLNode current){
  166.         while(current.right != null){
  167.             current = current.right;
  168.         }
  169.         return current;
  170.     }
  171.  
  172.  
  173.  
  174.     protected void delete(E value){
  175.         this.root = delete(root, value);
  176.     }
  177.  
  178.  
  179.     protected AVLNode delete(AVLNode current, E value) throws NoSuchElementException{
  180.         if(current == null){
  181.             throw new NoSuchElementException();
  182.         }
  183.         if(comparator.compare(value, (E) current.value) < 0){
  184.             current.left = delete(current.left, value);
  185.         }
  186.         else if(comparator.compare(value, (E) current.value) > 0){
  187.             current.right = delete(current.right, value);
  188.         }
  189.         else
  190.         {
  191.             AVLNode<E> currentLeft = current.left;
  192.             AVLNode<E> currentRight = current.right;
  193.  
  194.             if (currentRight == null) return currentLeft;
  195.             AVLNode<E> min = treeMin(currentRight);
  196.             min.right = removeMin(currentRight);
  197.             min.left = currentLeft;
  198.             return fixRemoveBalance(min);
  199.         }
  200.         return fixRemoveBalance(current);
  201.     }
  202.  
  203.     protected AVLNode<E> removeMin(AVLNode<E>  current) {
  204.         if(current.left == null){
  205.             return current.right;
  206.         }
  207.         current.left = removeMin(current.left);
  208.         return fixRemoveBalance(current);
  209.     }
  210.  
  211.    
  212.     protected AVLNode<E> fixRemoveBalance(AVLNode<E> current){
  213.  
  214.         current.height = Math.max(getHeight(current.left), getHeight(current.right)) + 1;
  215.  
  216.         if(getHeight(current.right) - getHeight(current.left) == 2){
  217.             if(getHeight(current.right.left) > getHeight(current.right.right)){
  218.                 current.right = rightRotate(current.right);
  219.             }
  220.             return leftRotate(current);
  221.         }
  222.         if(getHeight(current.left) - getHeight(current.right) == 2){
  223.             if(getHeight(current.left.right) > getHeight(current.left.left)){
  224.                 current.left = leftRotate(current.left);
  225.             }
  226.             return rightRotate(current);
  227.         }
  228.         return current;
  229.     }
  230.  
  231.  
  232.     @Override
  233.     public boolean add(E value) throws NullPointerException {
  234.         if(value == null){
  235.             throw  new NullPointerException();
  236.         }
  237.         AVLNode current = find(root, value);
  238.         if(current == null){
  239.             insert(value);
  240.             length ++;
  241.             return true;
  242.         }
  243.  
  244.         return false;
  245.  
  246.     }
  247.  
  248.  
  249.     @Override
  250.     public boolean remove(E value) throws NullPointerException {
  251.         if(value == null ){
  252.             throw new NullPointerException();
  253.         }
  254.         AVLNode current = find(root, value);
  255.         if(current == null || current.value == null){
  256.             return false;
  257.         }
  258.         delete(value);
  259.         length --;
  260.         return true;
  261.     }
  262.  
  263.  
  264.     @SuppressWarnings("RedundantIfStatement")
  265.     @Override
  266.     public boolean contains(Object value) throws NullPointerException {
  267.         if(value == null){
  268.             throw new NullPointerException();
  269.         }
  270.         AVLNode current = find(root,(E) value);
  271.         if(current == null || current.value == null) {
  272.             return false;
  273.         }
  274.         return true;
  275.     }
  276.  
  277.  
  278.     @Override
  279.     public E first() throws  NoSuchElementException{
  280.         if(root == null) {
  281.             throw new NoSuchElementException();
  282.         }
  283.         AVLNode current = root;
  284.         return (E) treeMin(current).value;
  285.     }
  286.  
  287.  
  288.     @Override
  289.     public E last() throws  NoSuchElementException{
  290.         if(root == null){
  291.             throw new NoSuchElementException();
  292.         }
  293.         AVLNode current = root;
  294.         return (E) treeMax(current).value;
  295.     }
  296.  
  297.  
  298.     @Override
  299.     public int size() {
  300.         return length;
  301.     }
  302.  
  303.  
  304.     @Override
  305.     public boolean isEmpty() {
  306.         return  root != null;
  307.     }
  308.  
  309.  
  310.     @Override
  311.     public void clear() {
  312.         root = null;
  313.         length = 0;
  314.     }
  315.  
  316.  
  317.     @Override
  318.     public void checkBalance() throws UnbalancedTreeException {
  319.         traverseTreeAndCheckBalanced(root);
  320.     }
  321.  
  322.     private int traverseTreeAndCheckBalanced(AVLNode<E> curr) throws UnbalancedTreeException {
  323.         if (curr == null) {
  324.             return 0;
  325.         }
  326.         int leftHeight = traverseTreeAndCheckBalanced(curr.left);
  327.         int rightHeight = traverseTreeAndCheckBalanced(curr.right);
  328.         if (Math.abs(leftHeight - rightHeight) > 1) {
  329.             throw UnbalancedTreeException.create("The heights of the two child subtrees of any node must be differ by at most one",
  330.                     leftHeight, rightHeight, curr.toString());
  331.         }
  332.         return Math.max(leftHeight, rightHeight) + 1;
  333.     }
  334. }
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