API tools faq
paste
Advertisement
ELEPHANTOR3301

BinaryTree AVL with Iterator

ELEPHANTOR3301
Dec 2nd, 2018
207
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 9.74 KB | None | 0 0
raw download clone embed print report
  1. public class Link<E> {
  2.     private E content;
  3.     private int balancing;
  4.     private Link left;
  5.     private Link right;
  6.     private Link father;
  7.     public Link(E content) {
  8.         this.content = content;
  9.         this.balancing = 0;
  10.         this.left = null;
  11.         this.right = null;
  12.     }
  13.     public E getContent() {
  14.         return content;
  15.     }
  16.     public void setContent(E content) {
  17.         this.content = content;
  18.     }
  19.     public int getBalancing() {
  20.         return balancing;
  21.     }
  22.     public void setBalancing(int balancing) {
  23.         this.balancing = balancing;
  24.     }
  25.     public Link getLeft() {
  26.         return left;
  27.     }
  28.     public void setLeft(Link left) {
  29.         this.left = left;
  30.     }
  31.     public Link getRight() {
  32.         return right;
  33.     }
  34.     public void setRight(Link right) {
  35.         this.right = right;
  36.     }
  37.     public Link getFather() {
  38.         return father;
  39.     }
  40.     public void setFather(Link father) {
  41.         this.father = father;
  42.     }
  43. }
  44.  
  45. public class TreeIterator implements Iterator{
  46.     private Stack<Link> stack = new Stack<>();
  47.  
  48.     public TreeIterator(Link root) {
  49.         push(root);
  50.     }
  51.     @Override
  52.     public boolean hasNext() {
  53.         return !stack.isEmpty();
  54.     }
  55.     @Override
  56.     public Link next() {
  57.         Link node = stack.pop();
  58.         push(node.getRight());
  59.         return node;
  60.     }
  61.     private void push(Link node) {
  62.         while (node != null) {
  63.             stack.push(node);
  64.             node = node.getLeft();
  65.         }
  66.     }
  67. }
  68.  
  69. public class TreeLink<Generic> {
  70.     private Link<Generic> root;
  71.     private int size;
  72.     private Comparator comparator;
  73.    
  74.     public TreeLink(Comparator comparator) {
  75.         this.comparator = comparator;
  76.     }
  77.     public void addInTree(Generic content) {
  78.         if(isEmpty()) addInRoot(content);
  79.         else {
  80.             Link<Generic> newLink = new Link<>(content);
  81.             addInBranch(root, newLink);
  82.         }
  83.         size++;
  84.     }
  85.     public Generic removeByContent(Generic content) {
  86.         Link<Generic> find = search(content);
  87.         removeFoundLink(find);
  88.         size--;
  89.         return find.getContent();
  90.     }
  91.     public Generic removeByPosition(int index) {
  92.         if(index > size || index < 0) return null;
  93.         else {
  94.             return removeByContent(getByPosition(index));
  95.         }
  96.     }
  97.     public Link search(Generic content) {
  98.         Link aux = root;
  99.         if(aux != null) {
  100.             while(aux != null) {
  101.                 if(comparator.compare(content, aux.getContent()) == 0) {
  102.                     return aux;
  103.                 }
  104.                 else if(comparator.compare(content, aux.getContent()) > 0) aux = aux.getRight();
  105.                 else aux = aux.getLeft();
  106.             }
  107.         }
  108.         return null;
  109.     }
  110.     public void removeAll() {
  111.         for(int i = 0; i < size; i++)
  112.             removeByContent(getByPosition(i));
  113.     }
  114.     public Generic getByPosition(int index) {
  115.         if(index > size || index < 0) return null;
  116.         else {
  117.             Iterator it = iterator();
  118.             for(int i = 0; i < index; i++)
  119.                 it.next();
  120.             return (Generic) ((Link)it.next()).getContent();
  121.         }
  122.     }
  123.     public boolean isEmpty() {
  124.         return size == 0;
  125.     }
  126.     public int size() {
  127.         return size;
  128.     }
  129.     public Link getRoot() {
  130.         return root;
  131.     }
  132.     public void display() {
  133.         inOrder(root);
  134.     }
  135.     public void setComparator(Comparator comparator) {
  136.         this.comparator = comparator;
  137.         TreeLink newTree = new TreeLink(comparator);
  138.         for(int i = 0; i < size; i++)
  139.             newTree.addInTree(removeByPosition(i));
  140.         root = newTree.getRoot();
  141.     }
  142.     private void addInRoot(Generic content) {
  143.         root = new Link<>(content);
  144.     }
  145.     private void addInBranch(Link current, Link newLink) {
  146.         if(comparator.compare(newLink.getContent(), current.getContent()) < 0) {
  147.             if(current.getLeft() == null) {
  148.                 current.setLeft(newLink);
  149.                 newLink.setFather(current);
  150.                 checkBalance(current);
  151.             }
  152.             else {
  153.                 addInBranch(current.getLeft(), newLink);
  154.             }
  155.     }
  156.         else if(comparator.compare(newLink.getContent(), current.getContent()) > 0) {
  157.             if(current.getRight() == null) {
  158.                 current.setRight(newLink);
  159.                 newLink.setFather(current);
  160.                 checkBalance(current);
  161.             }
  162.             else {
  163.                 addInBranch(current.getRight(), newLink);
  164.             }
  165.         }
  166.     }
  167.     private void checkBalance(Link anyLink) {
  168.         setBalancing(anyLink);
  169.         int balancing = anyLink.getBalancing();
  170.         if(balancing == -2) {
  171.             if(height(anyLink.getLeft().getLeft()) >= height(anyLink.getLeft().getRight())) {
  172.                 anyLink = singleRotationRight(anyLink);
  173.             }
  174.             else {
  175.                 anyLink = doubleRotationRight(anyLink);
  176.             }
  177.         }
  178.         else if(balancing == 2) {
  179.             if(height(anyLink.getRight().getRight()) >= height(anyLink.getRight().getLeft())) {
  180.                 anyLink = singleRotationLeft(anyLink);
  181.             }
  182.             else {
  183.                 anyLink = doubleRotationLeft(anyLink);
  184.             }
  185.         }
  186.         if(anyLink.getFather() != null) {
  187.             checkBalance(anyLink.getFather());
  188.         }
  189.         else {
  190.             this.root = anyLink;
  191.         }
  192.     }
  193.     private void removeFoundLink(Link find) {
  194.         Link aux1;
  195.         if(find.getLeft() == null || find.getRight() == null) {
  196.             if(find.getFather() == null) {
  197.                 root = null;
  198.                 find = null;
  199.                 return;
  200.             }
  201.             aux1 = find;
  202.         }
  203.         else {
  204.             aux1 = nextLink(find);
  205.             find.setContent(aux1.getContent());
  206.         }
  207.         Link aux2;
  208.         if(aux1.getLeft() != null) {
  209.             aux2 = aux1.getLeft();
  210.         }
  211.         else {
  212.             aux2 = aux1.getRight();
  213.         }
  214.         if(aux2 != null) {
  215.             aux2.setFather(aux1.getFather());
  216.         }
  217.         if(aux1.getFather() == null) {
  218.             root = aux2;
  219.         }
  220.         else {
  221.             if(aux1 == aux1.getFather().getLeft()) {
  222.                 aux1.getFather().setLeft(aux2);
  223.             }
  224.             else {
  225.                 aux1.getFather().setRight(aux2);
  226.             }
  227.             checkBalance(aux1.getFather());
  228.         }
  229.         aux1 = null;
  230.     }
  231.     private Link singleRotationLeft(Link anyLink) {
  232.         Link linkRight = anyLink.getRight();
  233.         linkRight.setFather(anyLink.getFather());
  234.         anyLink.setRight(linkRight.getLeft());
  235.         if(anyLink.getRight() != null) {
  236.             anyLink.getRight().setFather(anyLink);
  237.         }
  238.         linkRight.setLeft(anyLink);
  239.         anyLink.setFather(linkRight);
  240.         if(linkRight.getFather() != null) {
  241.             if(linkRight.getFather().getRight() == anyLink) {
  242.                 linkRight.getFather().setRight(linkRight);
  243.             }
  244.             else if(linkRight.getFather().getLeft() == anyLink) {
  245.                 linkRight.getFather().setLeft(linkRight);
  246.             }
  247.         }
  248.         setBalancing(anyLink);
  249.         setBalancing(linkRight);
  250.         return linkRight;
  251.     }
  252.     private Link singleRotationRight(Link anyLink) {
  253.         Link linkLeft = anyLink.getLeft();
  254.         linkLeft.setFather(anyLink.getFather());
  255.         anyLink.setLeft(linkLeft.getRight());
  256.         if(anyLink.getLeft() != null) {
  257.             anyLink.getLeft().setFather(anyLink);
  258.         }
  259.         linkLeft.setRight(anyLink);
  260.         anyLink.setFather(linkLeft);
  261.         if(linkLeft.getFather() != null) {
  262.             if(linkLeft.getFather().getRight() == anyLink) {
  263.                 linkLeft.getFather().setRight(linkLeft);
  264.             }
  265.             else if(linkLeft.getFather().getLeft() == anyLink) {
  266.                 linkLeft.getFather().setLeft(linkLeft);
  267.             }
  268.         }
  269.         setBalancing(anyLink);
  270.         setBalancing(linkLeft);
  271.         return linkLeft;
  272.     }
  273.     private Link doubleRotationRight(Link anyLink) {
  274.         anyLink.setLeft(singleRotationLeft(anyLink.getLeft()));
  275.         return singleRotationRight(anyLink);
  276.     }
  277.     private Link doubleRotationLeft(Link anyLink) {
  278.         anyLink.setRight(singleRotationRight(anyLink.getRight()));
  279.         return singleRotationLeft(anyLink);
  280.     }
  281.     private Link nextLink(Link anyLink) {
  282.         if (anyLink.getRight() != null) {
  283.             Link aux = anyLink.getRight();
  284.             while (aux.getLeft() != null)
  285.                 aux = aux.getLeft();
  286.             return aux;
  287.         }
  288.         else {
  289.             Link aux = anyLink.getFather();
  290.             while (aux != null && anyLink == aux.getRight()) {
  291.                 anyLink = aux;
  292.                 aux = anyLink.getFather();
  293.             }
  294.             return aux;
  295.         }
  296.     }
  297.     private int height(Link anyLink) {
  298.         if (anyLink == null) {
  299.             return -1;
  300.         }
  301.         if (anyLink.getLeft() == null && anyLink.getRight() == null) {
  302.             return 0;  
  303.         }
  304.         else if (anyLink.getLeft() == null) {
  305.             return 1 + height(anyLink.getRight());
  306.         }
  307.         else if (anyLink.getRight() == null) {
  308.             return 1 + height(anyLink.getLeft());
  309.         }
  310.         else {
  311.             return 1 + Math.max(height(anyLink.getLeft()), height(anyLink.getRight()));
  312.         }
  313.     }
  314.     private void setBalancing(Link anyLink) {
  315.         anyLink.setBalancing(height(anyLink.getRight()) - height(anyLink.getLeft()));
  316.     }
  317.     private void inOrder(Link anyLink) {
  318.         if (anyLink == null) {
  319.             return;
  320.         }
  321.         inOrder(anyLink.getLeft());
  322.         System.out.println(anyLink.getContent());
  323.         inOrder(anyLink.getRight());
  324.     }
  325.     private Iterator iterator() {
  326.         return new TreeIterator(root);
  327.     }
  328. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!