API tools faq
paste
Advertisement
kimo12

Untitled

kimo12
Mar 26th, 2017
78
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 11.72 KB | None | 0 0
raw download clone embed print report
  1. package eg.edu.alexu.csd.filestructure.avl;
  2.  
  3. public class AVLTree<T extends Comparable<T>> implements IAVLTree<T> {
  4.     private Node<T> root;
  5.  
  6.     public AVLTree() {
  7.         root = new Node<T>(null, null);
  8.     }
  9.  
  10.     @Override
  11.     public void insert(T key) {
  12.  
  13.         Node<T> cursor = null; // y
  14.         Node<T> current = root; // x
  15.         Node<T> newNode = new Node<T>(key, null); // z
  16.         while (current != null && current.getValue() != null) {
  17.             cursor = current;
  18.             try {
  19.                 if (newNode.getValue().compareTo(current.getValue()) < 0) {
  20.                     current = (Node<T>) current.getLeftChild();
  21.                 } else if (newNode.getValue().compareTo(current.getValue()) > 0) {
  22.                     current = (Node<T>) current.getRightChild();
  23.                 }
  24.             } catch (NullPointerException ex) {
  25.                 break;
  26.             }
  27.         }
  28.  
  29.         newNode.setParent(cursor);
  30.         if (cursor == null) {
  31.             root = newNode;
  32.         } else if (newNode.getValue().compareTo(cursor.getValue()) < 0) {
  33.             cursor.setLeftChild(newNode);
  34.             newNode.setParent(cursor);
  35.             reBalance((Node<T>) cursor.getLeftChild());
  36.         } else if (newNode.getValue().compareTo(cursor.getValue()) > 0) {
  37.             cursor.setRightChild(newNode);
  38.             newNode.setParent(cursor);
  39.             reBalance((Node<T>) cursor.getRightChild());
  40.         }
  41.  
  42.     }
  43.  
  44.     public void reBalance(Node<T> t) {
  45.         Node<T> parent = null; // up
  46.         Node<T> check = t;
  47.         Node<T> child = t;
  48.         while (check.hasParent()) {
  49.             // parent = (Node<T>) check.getParent();
  50.             child = check;
  51.             check = (Node<T>) check.getParent();
  52.             int balanceFactor = check.getBalanceFactor();
  53.             if (balanceFactor == 2) {
  54.                 if (check.getParent() != null)
  55.                     parent = (Node<T>) check.getParent();
  56.                 if (child.getBalanceFactor() == 1) {
  57.                     leftLeft(check, child, parent);
  58.                     break;
  59.                 } else if (child.getBalanceFactor() == -1) {
  60.                     leftRight(check, child, parent);
  61.                     break;
  62.                 }
  63.             } else if (balanceFactor == -2) {
  64.  
  65.                 if (check.getParent() != null)
  66.                     parent = (Node<T>) check.getParent();
  67.                 if (child.getBalanceFactor() == 1) {
  68.                     rightLeft(check, child, parent);
  69.                     break;
  70.                 } else if (child.getBalanceFactor() == -1) {
  71.                     rightRight(check, child, parent);
  72.                     break;
  73.  
  74.                 }
  75.             }
  76.         }
  77.     }
  78.  
  79.     private void rightRight(Node<T> check, Node<T> child, Node<T> parent) {
  80.         boolean right = false, noParent = false;
  81.         check.setRightChild(null);
  82.         child.setParent(null);
  83.         if (parent == null)
  84.             noParent = true;
  85.         else if (parent.getValue().compareTo(check.getValue()) < 0)
  86.             right = true;
  87.  
  88.         if (!noParent) {
  89.             if (right)
  90.                 parent.setRightChild(child);
  91.             else
  92.                 parent.setLeftChild(child);
  93.             child.setParent(parent);
  94.         }
  95.         if (child.hasLeftChild()) {
  96.             ((Node<T>) child.getLeftChild()).setParent(check);
  97.             check.setRightChild((Node<T>) child.getLeftChild());
  98.         }
  99.         child.setLeftChild(check);
  100.         check.setParent(child);
  101.         if (check == root)
  102.             root = child;
  103.     }
  104.  
  105.     private void rightLeft(Node<T> check, Node<T> child, Node<T> parent) {
  106.         Node<T> n = (Node<T>) child.getLeftChild();
  107.         boolean right = false, noParent = false;
  108.         check.setRightChild(null);
  109.         child.setLeftChild(null);
  110.         if (parent == null)
  111.             noParent = true;
  112.         else if (parent.getValue().compareTo(check.getValue()) < 0)
  113.             right = true;
  114.  
  115.         if (!noParent) {
  116.             if (right)
  117.                 parent.setRightChild(n);
  118.             else
  119.                 parent.setLeftChild(n);
  120.             n.setParent(parent);
  121.         }
  122.  
  123.         if (n.hasRightChild()) {
  124.             ((Node<T>) n.getRightChild()).setParent(child);
  125.             child.setLeftChild((Node<T>) n.getRightChild());
  126.         }
  127.         n.setRightChild(child);
  128.         child.setParent(n);
  129.         if (n.hasLeftChild()) {
  130.             ((Node<T>) n.getLeftChild()).setParent(check);
  131.             check.setRightChild((Node<T>) n.getLeftChild());
  132.         }
  133.         n.setLeftChild(check);
  134.         check.setParent(n);
  135.         if (check == root)
  136.             root = n;
  137.  
  138.     }
  139.  
  140.     private void leftRight(Node<T> check, Node<T> child, Node<T> parent) {
  141.         Node<T> n = (Node<T>) child.getRightChild();
  142.         boolean right = false, noParent = false;
  143.         check.setLeftChild(null);
  144.         child.setRightChild(null);
  145.         if (parent == null)
  146.             noParent = true;
  147.         else if (parent.getValue().compareTo(check.getValue()) < 0)
  148.             right = true;
  149.  
  150.         if (!noParent) {
  151.             if (right)
  152.                 parent.setRightChild(n);
  153.             else
  154.                 parent.setLeftChild(n);
  155.             n.setParent(parent);
  156.         }
  157.  
  158.         if (n.hasRightChild()) {
  159.             ((Node<T>) n.getRightChild()).setParent(check);
  160.             check.setLeftChild((Node<T>) n.getRightChild());
  161.         }
  162.         n.setRightChild(check);
  163.         check.setParent(n);
  164.         if (n.hasLeftChild()) {
  165.             ((Node<T>) n.getLeftChild()).setParent(child);
  166.             child.setRightChild((Node<T>) n.getLeftChild());
  167.         }
  168.         n.setLeftChild(child);
  169.         child.setParent(n);
  170.         if (check == root)
  171.             root = n;
  172.  
  173.     }
  174.  
  175.     private void leftLeft(Node<T> check, Node<T> child, Node<T> parent) {
  176.         boolean right = false, noParent = false;
  177.         check.setLeftChild(null);
  178.         child.setParent(null);
  179.         if (parent == null)
  180.             noParent = true;
  181.         else if (parent.getValue().compareTo(check.getValue()) < 0)
  182.             right = true;
  183.  
  184.         if (!noParent) {
  185.             if (right)
  186.                 parent.setRightChild(child);
  187.             else
  188.                 parent.setLeftChild(child);
  189.             child.setParent(parent);
  190.         }
  191.         if (child.hasRightChild()) {
  192.             ((Node<T>) child.getRightChild()).setParent(check);
  193.             check.setLeftChild((Node<T>) child.getRightChild());
  194.  
  195.         }
  196.         child.setRightChild(check);
  197.         check.setParent(child);
  198.         if (check == root)
  199.             root = child;
  200.     }
  201.  
  202.     public void inOrder(Node root) {
  203.  
  204.         if (root != null) {
  205.             inOrder((Node<T>) root.getLeftChild());
  206.             System.out.println(root.getValue());
  207.             inOrder((Node) root.getRightChild());
  208.         }
  209.     }
  210.  
  211.     private Node<T> minimum(Node<T> node) {
  212.         if (!node.hasLeftChild())
  213.             return node;
  214.         return minimum((Node<T>) node.getLeftChild());
  215.  
  216.     }
  217.  
  218.     private void deleteRebalance(Node<T> t) {
  219.         Node<T> parent = null; // up
  220.         Node<T> check = t;
  221.         Node<T> child = t;
  222.         if (check.getValue() != root.getValue()) {
  223.             while (check.hasParent()) {
  224.                 check = (Node<T>) check.getParent();
  225.                 int balanceFactor = check.getBalanceFactor();
  226.                 if (balanceFactor == 2) {
  227.                     if (check.getParent() != null)
  228.                         parent = (Node<T>) check.getParent();
  229.                     if (check.hasLeftChild()) {
  230.                         int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  231.                         if (leftChildBF == 1 || leftChildBF == 0) {
  232.                             child = (Node<T>) check.getLeftChild();
  233.                             leftLeft(check, child, parent);
  234.                         } else if (leftChildBF == -1) {
  235.                             child = (Node<T>) check.getLeftChild();
  236.                             leftRight(check, child, parent);
  237.                         }
  238.                     }
  239.                 } else if (balanceFactor == -2) {
  240.                     if (check.getParent() != null)
  241.                         parent = (Node<T>) check.getParent();
  242.                     if (check.hasRightChild()) {
  243.                         int rightChildBF = ((Node) check.getRightChild()).getBalanceFactor();
  244.                         if (rightChildBF == -1 || rightChildBF == 0) {
  245.                             child = (Node<T>) check.getRightChild();
  246.                             rightRight(check, child, parent);
  247.                         } else if (rightChildBF == 1) {
  248.                             child = (Node<T>) check.getRightChild();
  249.                             rightLeft(check, child, parent);
  250.                         }
  251.                     }
  252.                 }
  253.             }
  254.         } else {
  255.             int balanceFactor = check.getBalanceFactor();
  256.             if (balanceFactor == 2) {
  257.                 child = (Node<T>) check.getLeftChild();
  258.                 if (check.getParent() != null)
  259.                     parent = (Node<T>) check.getParent();
  260.                 if (check.hasLeftChild()) {
  261.                     int leftChildBF = child.getBalanceFactor();
  262.                     if (leftChildBF == 1 || leftChildBF == 0) {
  263.                         leftLeft(check, child, parent);
  264.                     } else if (leftChildBF == -1) {
  265.                         leftRight(check, child, parent);
  266.                     }
  267.                 }
  268.             } else if (balanceFactor == -2) {
  269.                 child = (Node<T>) check.getRightChild();
  270.                 if (check.getParent() != null)
  271.                     parent = (Node<T>) check.getParent();
  272.                 if (check.hasRightChild()) {
  273.                     int rightChildBF = child.getBalanceFactor();
  274.                     if (rightChildBF == -1 || rightChildBF == 0) {
  275.                         rightRight(check, child, parent);
  276.                     } else if (rightChildBF == 1) {
  277.                         rightLeft(check, child, parent);
  278.                     }
  279.                 }
  280.             }
  281.         }
  282.     }
  283.  
  284.     private void transplant(Node<T> toBeRemoved, Node<T> toBePlanted) {
  285.  
  286.         Node<T> toBeRemovedParent = (Node<T>) toBeRemoved.getParent();
  287.         if (!toBeRemoved.hasParent()) {
  288.             root = toBePlanted;
  289.         } else if (toBeRemoved.equals(toBeRemovedParent.getLeftChild())) {
  290.             toBeRemovedParent.setLeftChild(toBePlanted);
  291.         } else if (toBeRemoved.equals(toBeRemovedParent.getRightChild())) {
  292.             toBeRemovedParent.setRightChild(toBePlanted);
  293.         }
  294.         toBeRemoved.setParent(null);
  295.  
  296.         if (toBePlanted != null) {
  297.             Node<T> toBePlantedParent = (Node<T>) toBePlanted.getParent();
  298.             if (!toBeRemoved.equals(toBePlantedParent)) {
  299.                 if (toBePlantedParent.hasLeftChild() && toBePlantedParent.getLeftChild().equals(toBePlanted)) {
  300.                     toBePlantedParent.setLeftChild((Node) toBePlanted.getRightChild());
  301.                     if (toBePlanted.hasRightChild())
  302.                         ((Node) toBePlanted.getRightChild()).setParent(toBePlantedParent);
  303.                 } else if (toBePlantedParent.hasRightChild() && toBePlantedParent.getRightChild().equals(toBePlanted)) {
  304.                     toBePlantedParent.setRightChild(null);
  305.                 }
  306.  
  307.                 toBePlanted.setParent(toBeRemovedParent);
  308.  
  309.                 if (toBeRemoved.hasLeftChild()) {
  310.                     Node<T> leftOfToBeRemoved = ((Node<T>) toBeRemoved.getLeftChild());
  311.                     toBePlanted.setLeftChild(leftOfToBeRemoved);
  312.                     leftOfToBeRemoved.setParent(toBePlanted);
  313.                     toBeRemoved.setLeftChild(null);
  314.  
  315.                 }
  316.  
  317.                 if (toBeRemoved.hasRightChild()) {
  318.                     Node<T> rightOfToBeRemoved = ((Node<T>) toBeRemoved.getRightChild());
  319.                     toBePlanted.setRightChild(rightOfToBeRemoved);
  320.                     rightOfToBeRemoved.setParent(toBePlanted);
  321.                     toBeRemoved.setRightChild(null);
  322.  
  323.                 }
  324.             } else if (toBeRemoved.equals(toBePlantedParent)) {
  325.                 toBePlanted.setParent(toBeRemovedParent);
  326.                 if (toBeRemoved.hasRightChild() && toBeRemoved.getRightChild().equals(toBePlanted)) {
  327.                     toBePlanted.setLeftChild((Node) toBeRemoved.getLeftChild());
  328.                     if (toBeRemoved.hasLeftChild())
  329.                         ((Node) toBePlanted.getLeftChild()).setParent(toBePlanted);
  330.                 } else if (toBeRemoved.hasLeftChild() && toBeRemoved.getLeftChild().equals(toBePlanted)) {
  331.                     toBePlanted.setRightChild((Node) toBeRemoved.getRightChild());
  332.                     if (toBeRemoved.hasRightChild())
  333.                         ((Node) toBePlanted.getRightChild()).setParent(toBePlanted);
  334.                 }
  335.             }
  336.             }
  337.         if (toBeRemovedParent != null){
  338.             deleteRebalance(toBeRemovedParent);
  339.         }
  340.         else{
  341.             deleteRebalance(root);
  342.         }
  343.     }
  344.  
  345.     @Override
  346.     public boolean delete(T key) {
  347.         if (!search(key))
  348.             return false;
  349.  
  350.         Node<T> toBeDeleted = searchReturnsNode(key);
  351.         if (!toBeDeleted.hasLeftChild()) {
  352.             this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getRightChild());
  353.         } else if (!toBeDeleted.hasRightChild()) {
  354.             this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getLeftChild());
  355.         } else {
  356.             Node<T> node = minimum((Node<T>) toBeDeleted.getRightChild());
  357.             this.transplant(toBeDeleted, node);
  358.         }
  359.  
  360.         return true;
  361.     }
  362.  
  363.     private Node<T> searchReturnsNode(T key, Node<T> node) {
  364.         if (key.compareTo(node.getValue()) == 0)
  365.             return node;
  366.         if (key.compareTo(node.getValue()) < 0)
  367.             return searchReturnsNode(key, (Node<T>) node.getLeftChild());
  368.         else
  369.             return searchReturnsNode(key, (Node<T>) node.getRightChild());
  370.  
  371.     }
  372.  
  373.     public Node<T> searchReturnsNode(T key) {
  374.         return this.searchReturnsNode(key, root);
  375.     }
  376.  
  377.     private boolean search(T key, Node<T> node) {
  378.         if (node != null) {
  379.             if (key.compareTo(node.getValue()) == 0)
  380.                 return true;
  381.             if (key.compareTo(node.getValue()) < 0)
  382.                 return search(key, (Node<T>) node.getLeftChild());
  383.             else
  384.                 return search(key, (Node<T>) node.getRightChild());
  385.         }
  386.         return false;
  387.  
  388.     }
  389.  
  390.     @Override
  391.     public boolean search(T key) {
  392.         return this.search(key, root);
  393.     }
  394.  
  395.     @Override
  396.     public int height() {
  397.         if (root.getValue() == null) {
  398.             return -1;
  399.         } else {
  400.             return Math.max(root.getLeftHeight(), root.getLeftHeight()) + 1;
  401.         }
  402.     }
  403.  
  404.     @Override
  405.     public INode<T> getTree() {
  406.         return root;
  407.     }
  408.  
  409. }
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!