API tools faq
paste
Kabbalah

BinaryTree AVL with Iterator

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