API tools faq
paste
Advertisement
kimo12

Untitled

kimo12
Mar 23rd, 2017
80
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 11.86 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.     private boolean haveRoot;
  6.  
  7.     public AVLTree() {
  8.         haveRoot = false;
  9.         root = new Node<T>(null, null);
  10.     }
  11.  
  12.     @Override
  13.     public void insert(T key) {
  14.  
  15.         Node<T> cursor = null; // y
  16.         Node<T> current = root; // x
  17.         Node<T> newNode = new Node<T>(key, null); // z
  18.         while (current != null && current.getValue() != null) {
  19.             cursor = current;
  20.             try {
  21.                 if (newNode.getValue().compareTo(current.getValue()) < 0) {
  22.                     current = (Node<T>) current.getLeftChild();
  23.                 } else if (newNode.getValue().compareTo(current.getValue()) > 0) {
  24.                     current = (Node<T>) current.getRightChild();
  25.                 }
  26.             } catch (NullPointerException ex) {
  27.                 break;
  28.             }
  29.         }
  30.  
  31.         newNode.setParent(cursor);
  32.         if (cursor == null) {
  33.             root = newNode;
  34.         } else if (newNode.getValue().compareTo(cursor.getValue()) < 0) {
  35.             cursor.setLeftChild(newNode);
  36.             newNode.setParent(cursor);
  37.             reBalance((Node<T>) cursor.getLeftChild());
  38.         } else if (newNode.getValue().compareTo(cursor.getValue()) > 0) {
  39.             cursor.setRightChild(newNode);
  40.             newNode.setParent(cursor);
  41.             reBalance((Node<T>) cursor.getRightChild());
  42.         }
  43.  
  44.     }
  45.  
  46.     public void reBalance(Node<T> t) {
  47.         Node<T> parent = null; // up
  48.         Node<T> check = t;
  49.         Node<T> child = t;
  50.         while (check.hasParent()) {
  51.             // parent = (Node<T>) check.getParent();
  52.             child = check;
  53.             check = (Node<T>) check.getParent();
  54.             int balanceFactor = check.getBalanceFactor();
  55.             if (balanceFactor == 2) {
  56.                 if (check.getParent() != null)
  57.                     parent = (Node<T>) check.getParent();
  58.                 if (child.getBalanceFactor() == 1) {
  59.                     leftLeft(check, child, parent);
  60.                     break;
  61.                 } else if (child.getBalanceFactor() == -1) {
  62.                     leftRight(check, child, parent);
  63.                     break;
  64.                 }
  65.             } else if (balanceFactor == -2) {
  66.  
  67.                 if (check.getParent() != null)
  68.                     parent = (Node<T>) check.getParent();
  69.                 if (child.getBalanceFactor() == 1) {
  70.                     rightLeft(check, child, parent);
  71.                     break;
  72.                 } else if (child.getBalanceFactor() == -1) {
  73.                     rightRight(check, child, parent);
  74.                     break;
  75.  
  76.                 }
  77.             }
  78.         }
  79.     }
  80.  
  81.     private void rightRight(Node<T> check, Node<T> child, Node<T> parent) {
  82.         boolean right = false, noParent = false;
  83.         check.setRightChild(null);
  84.         child.setParent(null);
  85.         if (parent == null)
  86.             noParent = true;
  87.         else if (parent.getValue().compareTo(check.getValue()) < 0)
  88.             right = true;
  89.  
  90.         if (!noParent) {
  91.             if (right)
  92.                 parent.setRightChild(child);
  93.             else
  94.                 parent.setLeftChild(child);
  95.             child.setParent(parent);
  96.         }
  97.         if (child.hasLeftChild())
  98.             check.setRightChild((Node<T>) child.getLeftChild());
  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 Node<T> getNodes() {
  203.         return this.root;
  204.     }
  205.  
  206.     public void inOrder(Node root) {
  207.  
  208.         if (root != null) {
  209.             inOrder((Node<T>) root.getLeftChild());
  210.             System.out.println(root.getValue());
  211.             inOrder((Node) root.getRightChild());
  212.         }
  213.     }
  214.  
  215.     private Node<T> minimum(Node<T> node) {
  216.         if (!node.hasLeftChild())
  217.             return node;
  218.         return minimum((Node<T>) node.getLeftChild());
  219.  
  220.     }
  221.  
  222.     // private Node<T> getMySuccessor(Node<T> node) {
  223.     // if (node.hasRightChild()) {
  224.     // return this.minimum((Node<T>) node.getRightChild());
  225.     // } else {
  226.     // Node<T> carry = (Node<T>) node.getParent();
  227.     // while (carry != null && ((Node<T>) node).equals((Node<T>)
  228.     // carry.getRightChild())) {
  229.     // node = carry;
  230.     // carry = (Node<T>) node.getParent();
  231.     // }
  232.     // return carry;
  233.     // }
  234.     //
  235.     // }
  236.  
  237.     private void deleteRebalance(Node<T> t) {
  238.         Node<T> parent = null; // up
  239.         Node<T> check = t;
  240.         Node<T> child = t;
  241.         while (check.hasParent()) {
  242.             check = (Node<T>) check.getParent();
  243.             int balanceFactor = check.getBalanceFactor();
  244.             if (balanceFactor == 2) {
  245.                 if (check.getParent() != null)
  246.                     parent = (Node<T>) check.getParent();
  247.                 if (check.hasLeftChild()) {
  248.                     int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  249.                     if (leftChildBF == 1) {
  250.                         child = (Node<T>) check.getLeftChild();
  251.                         leftLeft(check, child, parent);
  252.                     }
  253.                 } else if (check.hasRightChild()) {
  254.                     int rightChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  255.                     if (rightChildBF == -1) {
  256.                         child = (Node<T>) check.getRightChild();
  257.                         leftRight(check, child, parent);
  258.                     }
  259.                 }
  260.             } else if (balanceFactor == -2) {
  261.                 if (check.getParent() != null)
  262.                     parent = (Node<T>) check.getParent();
  263.                 if (check.hasLeftChild()) {
  264.                     int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  265.                     if (leftChildBF == -1) {
  266.                         child = (Node<T>) check.getRightChild();
  267.                         rightRight(check, child, parent);
  268.                     }
  269.                 } else if (check.hasRightChild()) {
  270.                     int rightChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  271.                     if (rightChildBF == 1) {
  272.                         child = (Node<T>) check.getLeftChild();
  273.                         rightLeft(check, child, parent);
  274.                     }
  275.                 }
  276.             }
  277.         }
  278.     }
  279.  
  280.      private void transplant(Node<T> toBeRemoved, Node<T> toBePlanted) {
  281.          
  282.             Node<T> toBeRemovedParent = (Node<T>) toBeRemoved.getParent();
  283.             if (!toBeRemoved.hasParent()) {
  284.                 root = toBePlanted;
  285.             } else if (toBeRemoved.equals(toBeRemovedParent.getLeftChild())) {
  286.                 toBeRemovedParent.setLeftChild(toBePlanted);
  287.             } else {
  288.                 toBeRemovedParent.setRightChild(toBePlanted);
  289.             }
  290.             toBeRemoved.setParent(null);
  291.             if (toBePlanted != null) {
  292.                 Node<T> toBePlantedParent = (Node<T>) toBePlanted.getParent();
  293.      
  294.                 // change
  295.                 if (!toBeRemoved.equals(toBePlantedParent)) {
  296.                     if (toBePlantedParent.hasLeftChild() && toBePlantedParent.getLeftChild().equals(toBePlanted)) {
  297.                         toBePlantedParent.setLeftChild((Node) toBePlanted.getRightChild());
  298.                         if (toBePlanted.hasRightChild())
  299.                             ((Node) toBePlanted.getRightChild()).setParent(toBePlantedParent);
  300.                     } else if (toBePlantedParent.hasRightChild() && toBePlantedParent.getRightChild().equals(toBePlanted)) {
  301.                         toBePlantedParent.setRightChild(null);
  302.                     }
  303.      
  304.                     toBePlanted.setParent(toBeRemovedParent);
  305.      
  306.                     if (toBeRemoved.hasLeftChild()) {
  307.                         Node<T> leftOfToBeRemoved = ((Node<T>) toBeRemoved.getLeftChild());
  308.                         toBePlanted.setLeftChild(leftOfToBeRemoved);
  309.                         leftOfToBeRemoved.setParent(toBePlanted);
  310.                         toBeRemoved.setLeftChild(null);
  311.      
  312.                     }
  313.      
  314.                     if (toBeRemoved.hasRightChild()) {
  315.                         Node<T> rightOfToBeRemoved = ((Node<T>) toBeRemoved.getRightChild());
  316.                         toBePlanted.setRightChild(rightOfToBeRemoved);
  317.                         rightOfToBeRemoved.setParent(toBePlanted);
  318.                         toBeRemoved.setRightChild(null);
  319.      
  320.                     }
  321.                 } else if (toBeRemoved.equals(toBePlantedParent)) {
  322.      
  323.                     toBePlanted.setParent(toBeRemovedParent);
  324.                     //
  325.                     if (toBeRemoved.hasRightChild() && toBeRemoved.getRightChild().equals(toBePlanted)) {
  326.                         toBePlanted.setLeftChild((Node) toBeRemoved.getLeftChild());
  327.                         if (toBeRemoved.hasLeftChild())
  328.                             ((Node) toBePlanted.getLeftChild()).setParent(toBePlanted);
  329.                     } else if (toBeRemoved.hasLeftChild() && toBeRemoved.getLeftChild().equals(toBePlanted)) {
  330.                         toBePlanted.setRightChild((Node) toBeRemoved.getRightChild());
  331.                         if (toBeRemoved.hasRightChild())
  332.                             ((Node) toBePlanted.getRightChild()).setParent(toBePlanted);
  333.                     }
  334.                 }
  335.                 deleteRebalance(toBePlanted);
  336.             }
  337.         }
  338.  
  339.     @Override
  340.     public boolean delete(T key) {
  341.         if (!search(key))
  342.             return false;
  343.  
  344.         Node<T> toBeDeleted = searchReturnsNode(key);
  345.         if (!toBeDeleted.hasLeftChild()) {
  346.             this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getRightChild());
  347.         } else if (!toBeDeleted.hasRightChild()) {
  348.             this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getLeftChild());
  349.         } else {
  350.             Node<T> node = minimum((Node<T>) toBeDeleted.getRightChild());
  351.             this.transplant(toBeDeleted, node);
  352.         }
  353.  
  354.         return true;
  355.     }
  356.  
  357.     private Node<T> searchReturnsNode(T key, Node<T> node) {
  358.         if (key.compareTo(node.getValue()) == 0)
  359.             return node;
  360.         if (key.compareTo(node.getValue()) < 0)
  361.             return searchReturnsNode(key, (Node<T>) node.getLeftChild());
  362.         else
  363.             return searchReturnsNode(key, (Node<T>) node.getRightChild());
  364.  
  365.     }
  366.  
  367.     public Node<T> searchReturnsNode(T key) {
  368.         return this.searchReturnsNode(key, root);
  369.     }
  370.  
  371.     private boolean search(T key, Node<T> node) {
  372.         if (node != null) {
  373.             if (key.compareTo(node.getValue()) == 0)
  374.                 return true;
  375.             if (key.compareTo(node.getValue()) < 0)
  376.                 return search(key, (Node<T>) node.getLeftChild());
  377.             else
  378.                 return search(key, (Node<T>) node.getRightChild());
  379.         }
  380.         return false;
  381.  
  382.     }
  383.  
  384.     @Override
  385.     public boolean search(T key) {
  386.         return this.search(key, root);
  387.     }
  388.  
  389.     @Override
  390.     public int height() {
  391.         if (root.getValue() == null) {
  392.             return -1;
  393.         } else {
  394.             return Math.max(root.getLeftHeight(), root.getLeftHeight());
  395.         }
  396.     }
  397.  
  398.     @Override
  399.     public INode<T> getTree() {
  400.         return root;
  401.     }
  402.  
  403. }
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!