API tools faq
paste
Advertisement
kimo12

Untitled

kimo12
Mar 23rd, 2017
93
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
  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.         if (n.hasLeftChild()) {
  129.             ((Node<T>) n.getLeftChild()).setParent(check);
  130.             check.setRightChild((Node<T>) n.getLeftChild());
  131.         }
  132.         n.setLeftChild(check);
  133.         if (check == root)
  134.             root = n;
  135.  
  136.     }
  137.  
  138.     private void leftRight(Node<T> check, Node<T> child, Node<T> parent) {
  139.         Node<T> n = (Node<T>) child.getRightChild();
  140.         boolean right = false, noParent = false;
  141.         check.setLeftChild(null);
  142.         child.setRightChild(null);
  143.         if (parent == null)
  144.             noParent = true;
  145.         else if (parent.getValue().compareTo(check.getValue()) < 0)
  146.             right = true;
  147.  
  148.         if (!noParent) {
  149.             if (right)
  150.                 parent.setRightChild(n);
  151.             else
  152.                 parent.setLeftChild(n);
  153.             n.setParent(parent);
  154.         }
  155.  
  156.         if (n.hasRightChild()) {
  157.             ((Node<T>) n.getRightChild()).setParent(check);
  158.             check.setLeftChild((Node<T>) n.getRightChild());
  159.         }
  160.         n.setRightChild(check);
  161.         check.setParent(n);
  162.         if (n.hasLeftChild()) {
  163.             ((Node<T>) n.getLeftChild()).setParent(child);
  164.             child.setRightChild((Node<T>) n.getLeftChild());
  165.         }
  166.         n.setLeftChild(child);
  167.         child.setParent(n);
  168.         if (check == root)
  169.             root = n;
  170.  
  171.     }
  172.  
  173.     private void leftLeft(Node<T> check, Node<T> child, Node<T> parent) {
  174.         boolean right = false, noParent = false;
  175.         check.setLeftChild(null);
  176.         child.setParent(null);
  177.         if (parent == null)
  178.             noParent = true;
  179.         else if (parent.getValue().compareTo(check.getValue()) < 0)
  180.             right = true;
  181.  
  182.         if (!noParent) {
  183.             if (right)
  184.                 parent.setRightChild(child);
  185.             else
  186.                 parent.setLeftChild(child);
  187.             child.setParent(parent);
  188.         }
  189.         if (child.hasRightChild())
  190.             check.setLeftChild((Node<T>) child.getRightChild());
  191.         child.setRightChild(check);
  192.         check.setParent(child);
  193.         if (check == root)
  194.             root = child;
  195.     }
  196.  
  197.     public Node<T> getNodes() {
  198.         return this.root;
  199.     }
  200.  
  201.     public void inOrder(Node root) {
  202.  
  203.         if (root != null) {
  204.             inOrder((Node<T>) root.getLeftChild());
  205.             System.out.println(root.getValue());
  206.             inOrder((Node) root.getRightChild());
  207.         }
  208.     }
  209.  
  210.     private Node<T> minimum(Node<T> node) {
  211.         if (!node.hasLeftChild())
  212.             return node;
  213.         return minimum((Node<T>) node.getLeftChild());
  214.  
  215.     }
  216.  
  217.     // private Node<T> getMySuccessor(Node<T> node) {
  218.     // if (node.hasRightChild()) {
  219.     // return this.minimum((Node<T>) node.getRightChild());
  220.     // } else {
  221.     // Node<T> carry = (Node<T>) node.getParent();
  222.     // while (carry != null && ((Node<T>) node).equals((Node<T>)
  223.     // carry.getRightChild())) {
  224.     // node = carry;
  225.     // carry = (Node<T>) node.getParent();
  226.     // }
  227.     // return carry;
  228.     // }
  229.     //
  230.     // }
  231.  
  232.     private void transplant(Node<T> toBeRemoved, Node<T> toBePlanted) {
  233.         Node<T> toBeRemovedParent = (Node<T>) toBeRemoved.getParent();
  234.         if (!toBeRemoved.hasParent()) {
  235.             root = toBePlanted;
  236.             // reBalance(toBePlantedParent);
  237.         } else if (toBeRemoved.equals(toBeRemovedParent.getLeftChild())) {
  238.             toBeRemovedParent.setLeftChild(toBePlanted);
  239.             // toBeRemoved.setLeftChild(null);
  240.  
  241.         } else {
  242.             toBeRemovedParent.setRightChild(toBePlanted);
  243.             // toBeRemoved.setRightChild(null);
  244.  
  245.         }
  246.         toBeRemoved.setParent(null);
  247.         if (toBePlanted != null) {
  248.             Node<T> toBePlantedParent = (Node<T>) toBePlanted.getParent();
  249.  
  250.             if (toBePlantedParent.hasLeftChild() && toBePlantedParent.getLeftChild().equals(toBePlanted))
  251.                 toBePlantedParent.setLeftChild(null);
  252.             else if (toBePlantedParent.hasRightChild())
  253.                 toBePlantedParent.setRightChild(null);
  254.             toBePlanted.setParent(toBeRemovedParent);
  255.             if (toBeRemoved.hasLeftChild()) {
  256.                 Node<T> leftOfToBeRemoved = ((Node<T>) toBeRemoved.getLeftChild());
  257.                 toBePlanted.setLeftChild(leftOfToBeRemoved);
  258.                 leftOfToBeRemoved.setParent(toBePlanted);
  259.             }
  260.             if (toBeRemoved.hasRightChild()) {
  261.                 Node<T> rightOfToBeRemoved = ((Node<T>) toBeRemoved.getRightChild());
  262.                 toBePlanted.setRightChild(rightOfToBeRemoved);
  263.                 rightOfToBeRemoved.setParent(toBePlanted);
  264.             }
  265.         }
  266.  
  267.     }
  268.  
  269.     @Override
  270.     public boolean delete(T key) {
  271.         if (!search(key))
  272.             return false;
  273.  
  274.         Node<T> toBeDeleted = searchReturnsNode(key);
  275.         if (!toBeDeleted.hasLeftChild()) {
  276.             this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getRightChild());
  277.         } else if (!toBeDeleted.hasRightChild()) {
  278.             this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getLeftChild());
  279.         } else {
  280.             Node<T> node = minimum((Node<T>) toBeDeleted.getRightChild());
  281.             this.transplant(toBeDeleted, node);
  282.         }
  283.         return true;
  284.     }
  285.  
  286.     private Node<T> searchReturnsNode(T key, Node<T> node) {
  287.         if (key.compareTo(node.getValue()) == 0)
  288.             return node;
  289.         if (key.compareTo(node.getValue()) < 0)
  290.             return searchReturnsNode(key, (Node<T>) node.getLeftChild());
  291.         else
  292.             return searchReturnsNode(key, (Node<T>) node.getRightChild());
  293.  
  294.     }
  295.  
  296.     private void deleteRebalance(Node<T> t) {
  297.         Node<T> parent = null; // up
  298.         Node<T> check = t;
  299.         Node<T> child = t;
  300.         while (check.hasParent()) {
  301.             check = (Node<T>) check.getParent();
  302.             int balanceFactor = check.getBalanceFactor();
  303.             if (balanceFactor == 2) {
  304.                 if (check.getParent() != null)
  305.                     parent = (Node<T>) check.getParent();
  306.                 if (check.hasLeftChild()) {
  307.                     int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  308.                     if (leftChildBF == 1) {
  309.                         child =(Node<T>) check.getLeftChild();
  310.                         leftLeft(check, child, parent);
  311.                     }
  312.                 } else if (check.hasRightChild()) {
  313.                     int rightChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  314.                     if (rightChildBF == -1) {
  315.                         child =(Node<T>) check.getRightChild();
  316.                         leftRight(check, child, parent);
  317.                     }
  318.                 }
  319.             } else if (balanceFactor == -2) {
  320.                 if (check.getParent() != null)
  321.                     parent = (Node<T>) check.getParent();
  322.                 if (check.hasLeftChild()) {
  323.                     int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  324.                     if (leftChildBF == -1) {
  325.                         child =(Node<T>) check.getRightChild();
  326.                         rightRight(check, child, parent);
  327.                     }
  328.                 } else if (check.hasRightChild()) {
  329.                     int rightChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  330.                     if (rightChildBF == 1) {
  331.                         child =(Node<T>) check.getLeftChild();
  332.                         rightLeft(check, child, parent);
  333.                     }
  334.                 }
  335.             }
  336.         }
  337.     }
  338.  
  339.     public Node<T> searchReturnsNode(T key) {
  340.         return this.searchReturnsNode(key, root);
  341.     }
  342.  
  343.     private boolean search(T key, Node<T> node) {
  344.         if (node != null) {
  345.             if (key.compareTo(node.getValue()) == 0)
  346.                 return true;
  347.             if (key.compareTo(node.getValue()) < 0)
  348.                 return search(key, (Node<T>) node.getLeftChild());
  349.             else
  350.                 return search(key, (Node<T>) node.getRightChild());
  351.         }
  352.         return false;
  353.  
  354.     }
  355.  
  356.     @Override
  357.     public boolean search(T key) {
  358.         return this.search(key, root);
  359.     }
  360.  
  361.     @Override
  362.     public int height() {
  363.         if (root.getValue() == null) {
  364.             return -1;
  365.         } else {
  366.             return Math.max(root.getLeftHeight(), root.getLeftHeight());
  367.         }
  368.     }
  369.  
  370.     @Override
  371.     public INode<T> getTree() {
  372.         return this.root;
  373.     }
  374.  
  375. }
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!