AVL

概念及实现

我们在研究二分搜索树时发现，如果我们将数据顺序添加进树中时，它有会退化成一棵链表，即所有的元素都添加到一个孩子上，这样树结构的优势就体现不出来，为了不使左右孩子的高度相差太大，我们需要对树进行调整，使树达到平衡，成为一棵平衡二叉树，AVL就是一种经典的平衡二叉树
AVL树 - 图1
在AVL中，我们定义的平衡二叉树为，对于任意一个节点，左子树和右子树的高度相差不能超过1。
AVL树 - 图2
我们为每一个节点标注好高度值，计算方法为取左右子树高度较高的高度，然后+1
AVL树 - 图3
然后我们还有记录节点左右子树的高度差，我们称之为平衡因子(规定用左子树的高度-右子树的高度)
AVL树 - 图4
由于我们只是在添加元素和删除元素时对树进行调整，其余的代码同二分搜索树是相同的，所以就不贴出所有的代码，只给出不同的代码，首先我们需要在Node类中添加一个height变量来记录高度

  1. private class Node {
  2.     public E e;
  3.     public Node left;
  4.     public Node right;
  5.     //高度
  6.     public int height;
  7.     public Node(E e) {
  8.         this.e = e;
  9.         left = null;
  10.         right = null;
  11.         //高度初始为1
  12.         height = 1;
  13.     }
  14.     @Override
  15.     public String toString() {
  16.         return e.toString();
  17.     }
  18. }

新增加一个获得某节点高度的函数和平衡因子的函数

  1. private int getHeight(Node node) {
  2.     if (node == null) {
  3.         return 0;
  4.     }
  5.     return node.height;
  6. }
  7. private int getBalanceFactor(Node node) {
  8.     if (node == null) {
  9.         return 0;
  10.     }
  12.     return getHeight(node.left) - getHeight(node.right);
  13. }

有了这些因素，我们一般需要在添加元素时进行维护，重新计算高度和平衡因子，从而进行调整

  1. private Node add(Node node, E e) {
  2.     if (node == null) {
  3.         size++;
  4.         return new Node(e);
  5.     }
  6.     if (e.compareTo(node.e) < 0) {
  7.         node.left = add(node.left, e);
  8.     } else if (e.compareTo(node.e) > 0) {
  9.         node.right = add(node.right,e);
  10.     }
  12.     //更新高度
  13.     node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
  14.     //计算平衡因子
  15.     int balanceFactor = getBalanceFactor(node);
  16.     if (Math.abs(balanceFactor) > 1) {
  17.         //进行调整
  18.     }
  19.     return node;
  20. }

我们后面的内容主要是如何调整，后面所以只给出如何调整的代码，在学如何调整之前，我们来写两个辅助函数来判断这棵树是不是二分搜索树和AVL树，因为如果我们的代码有问题的话，有可能破坏二分搜索树的性质，这样有利于我们检查，那怎么检查一棵树是不是二分搜索树，我们根据二分搜索树的性质，它的中序遍历的结果是从小到大的特性，我们重写中序遍历为

  1. public boolean isBST() {
  2.     ArrayList<E> arrayList = new ArrayList<>();
  3.     inOrder(root, arrayList);
  5.     for (int i = 1; i < arrayList.size(); i++) {
  6.         if (arrayList.get(i-1).compareTo(arrayList.get(i)) > 0) 
  7.             return false;
  8.         }
  9.     }
  10.     return true;
  11. }
  12. private void inOrder(Node node, ArrayList<E> arrayList) {
  13.     if (node == null) {
  14.         return;
  15.     }
  17.     inOrder(node.left, arrayList);
  18.     arrayList.add(node.e);
  19.     inOrder(node.right, arrayList);
  20. }

现在我们判断这棵树是不是平衡二叉树

  1. public boolean isBalanced() {
  2.     return isBalanced(root);
  3. }
  4. //判断某个节点是不是平衡
  5. private boolean isBalanced(Node node) {
  6.     if (node == null) {
  7.         return true;
  8.     }
  9.     int balanceFactor = getBalanceFactor(node);
  10.     if (Math.abs(balanceFactor) > 1) {
  11.         return false;
  12.     }
  13.     return isBalanced(node.left) && isBalanced(node.right);
  14. }

下面对不平衡的四种情形进行讨论，并给出调整方法
AVL树 - 图5

  1. // 对节点y进行向右旋转操作，返回旋转后新的根节点x
  2. //        y                              x
  3. //       / \                           /   \
  4. //      x   T4     向右旋转 (y)        z     y
  5. //     / \       - - - - - - - ->    / \   / \
  6. //    z   T3                       T1  T2 T3 T4
  7. //   / \
  8. // T1   T2
  9. private Node rightRotate(Node y) {
  10.     Node x = y.left;
  11.     Node T3 = x.right;
  12.     x.right = y;
  13.     y.left = T3;
  15.     //更新x和y的高度值 先更新y的，因为y是x的右孩子，x的更新取决于y
  16.     y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
  17.     x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
  19.     return x;
  20. }
  21. // 对节点y进行向左旋转操作，返回旋转后新的根节点x
  22. //    y                             x
  23. //  /  \                          /   \
  24. // T4   x      向左旋转 (y)       y     z
  25. //     / \   - - - - - - - ->   / \   / \
  26. //   T3  z                     T4 T3 T1 T2
  27. //      / \
  28. //     T1 T2
  29. private Node leftRotate(Node y) {
  30.     Node x = y.right;
  31.     Node T3 = x.left;
  32.     x.left = y;
  33.     y.right = T3;
  35.     y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
  36.     x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
  38.     return x;
  39. }
  41. public void add(E e) {
  42.     root = add(root, e);
  43. }
  44. private Node add(Node node, E e) {
  45.     if (node == null) {
  46.         size++;
  47.         return new Node(e);
  48.     }
  49.     if (e.compareTo(node.e) < 0) {
  50.         node.left = add(node.left, e);
  51.     } else if (e.compareTo(node.e) > 0) {
  52.         node.right = add(node.right,e);
  53.     }
  54.     //更新高度
  55.     node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
  56.     //计算平衡因子
  57.     int balanceFactor = getBalanceFactor(node);
  58.     //调整
  59.     if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
  60.         return rightRotate(node);
  61.     }
  62.     if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
  63.         return leftRotate(node);
  64.     }
  65.     if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
  66.         node.left = leftRotate(node.left);
  67.         return rightRotate(node);
  68.     }
  69.     if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
  70.         node.right = rightRotate(node.right);
  71.         return leftRotate(node);
  72.     }
  73.     return node;
  74. }
  75. public void remove(E e) {
  76.     root = remove(root, e);
  77. }
  78. private Node remove(Node node, E e) {
  79.     if (node == null) {
  80.         return null;
  81.     }
  82.     Node retNode;
  83.     if (e.equals(node.e)) {
  84.         if (node.right == null) {
  85.             Node leftNode = node.left;
  86.             node.left = null;
  87.             size--;
  88.             retNode = leftNode;
  89.         } else if (node.left == null) {
  90.             Node rightNode = node.right;
  91.             node.right = null;
  92.             size--;
  93.             retNode = rightNode;
  94.         } else {
  95.             Node successor = minimum(node.right);
  96.             ////由于removeMin没有维持balance，所以我们复用remove
  97.             successor.right = remove(node.right,successor.e);
  98.             successor.left = node.left;
  99.             node.left = node.right = null;
  101.             retNode = successor;
  102.         }
  103.     } else if (e.compareTo(node.e) < 0) {
  104.         node.left = remove(node.left, e);
  105.         retNode = node;
  106.     } else {
  107.         node.right = remove(node.right, e);
  108.         retNode = node;
  109.     }
  111.     //否则retNode.height会有空指针异常
  112.     if (retNode == null) {
  113.         return null;
  114.     }
  116.     //更新高度
  117.     retNode.height = Math.max(getHeight(retNode.left),getHeight(retNode.right)) + 1;
  118.     //计算平衡因子
  119.     int balanceFactor = getBalanceFactor(retNode);
  120.     if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
  121.         return rightRotate(retNode);
  122.     }
  123.     if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
  124.         return leftRotate(retNode);
  125.     }
  126.     if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
  127.         retNode.left = leftRotate(retNode.left);
  128.         return rightRotate(retNode);
  129.     }
  130.     if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
  131.         retNode.right = rightRotate(retNode.right);
  132.         return leftRotate(retNode);
  133.     }
  134.     return retNode;
  135. }

完整代码

  1. import java.util.ArrayList;
  3. public class AVLTree<E extends Comparable<E>> {
  4.     private class Node {
  5.         public E e;
  6.         public Node left;
  7.         public Node right;
  8.         public int height;
  10.         public Node(E e) {
  11.             this.e = e;
  12.             left = null;
  13.             right = null;
  14.             height = 1;
  15.         }
  17.         @Override
  18.         public String toString() {
  19.             return e.toString();
  20.         }
  21.     }
  23.     //根节点
  24.     private Node root;
  25.     //树中元素的个数
  26.     private int size;
  28.     public AVLTree() {
  29.         root = null;
  30.         size = 0;
  31.     }
  33.     public int size() {
  34.         return size;
  35.     }
  36.     public boolean isEmpty() {
  37.         return size == 0;
  38.     }
  39.     private int getHeight(Node node) {
  40.         if (node == null) {
  41.             return 0;
  42.         }
  44.         return node.height;
  45.     }
  47.     private int getBalanceFactor(Node node) {
  48.         if (node == null) {
  49.             return 0;
  50.         }
  52.         return getHeight(node.left) - getHeight(node.right);
  53.     }
  55.     public boolean isBST() {
  56.         ArrayList<E> arrayList = new ArrayList<>();
  57.         inOrder(root, arrayList);
  59.         for (int i = 1; i < arrayList.size(); i++) {
  60.             if (arrayList.get(i-1).compareTo(arrayList.get(i)) > 0) {
  61.                 return false;
  62.             }
  63.         }
  64.         return true;
  65.     }
  66.     private void inOrder(Node node, ArrayList<E> arrayList) {
  67.         if (node == null) {
  68.             return;
  69.         }
  71.         inOrder(node.left, arrayList);
  72.         arrayList.add(node.e);
  73.         inOrder(node.right, arrayList);
  74.     }
  76.     public boolean isBalanced() {
  77.         return isBalanced(root);
  78.     }
  79.     //判断某个节点是不是平衡
  80.     private boolean isBalanced(Node node) {
  81.         if (node == null) {
  82.             return true;
  83.         }
  84.         int balanceFactor = getBalanceFactor(node);
  85.         if (Math.abs(balanceFactor) > 1) {
  86.             return false;
  87.         }
  88.         return isBalanced(node.left) && isBalanced(node.right);
  89.     }
  91.     private Node rightRotate(Node y) {
  92.         Node x = y.left;
  93.         Node T3 = x.right;
  94.         x.right = y;
  95.         y.left = T3;
  97.         //更新x和y的高度值 先更新y的，因为y是x的右孩子，x的更新取决于y
  98.         y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
  99.         x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
  101.         return x;
  102.     }
  104.     private Node leftRotate(Node y) {
  105.         Node x = y.right;
  106.         Node T3 = x.left;
  107.         x.left = y;
  108.         y.right = T3;
  110.         y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
  111.         x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
  113.         return x;
  114.     }
  116.     public void add(E e) {
  117.         root = add(root, e);
  118.     }
  121.     private Node add(Node node, E e) {
  122.         if (node == null) {
  123.             size++;
  124.             return new Node(e);
  125.         }
  127.         if (e.compareTo(node.e) < 0) {
  128.             node.left = add(node.left, e);
  129.         } else if (e.compareTo(node.e) > 0) {
  130.             node.right = add(node.right,e);
  131.         }
  133.         //更新高度
  134.         node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
  135.         //计算平衡因子
  136.         int balanceFactor = getBalanceFactor(node);
  138.         if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
  139.             return rightRotate(node);
  140.         }
  141.         if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
  142.             return leftRotate(node);
  143.         }
  144.         if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
  145.             node.left = leftRotate(node.left);
  146.             return rightRotate(node);
  147.         }
  148.         if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
  149.             node.right = rightRotate(node.right);
  150.             return leftRotate(node);
  151.         }
  153.         return node;
  154.     }
  156.     public boolean contains(E e) {
  157.         return contains(root, e);
  158.     }
  160.     private boolean contains(Node node, E e) {
  161.         if (node == null) {
  162.             return false;
  163.         }
  165.         if (e.equals(node.e)) {
  166.             return true;
  167.         } else if (e.compareTo(node.e) < 0) {
  168.             return contains(node.left, e);
  169.         } else {
  170.             return contains(node.right,e);
  171.         }
  172.     }
  174.     public E minimum() {
  175.         if (size == 0) {
  176.             throw new IllegalArgumentException("树为空");
  177.         }
  178.         return minimum(root).e;
  179.     }
  181.     private Node minimum(Node node) {
  182.         if (node.left == null) {
  183.             return node;
  184.         }
  185.         return minimum(node.left);
  186.     }
  188.     public void remove(E e) {
  189.         root = remove(root, e);
  190.     }
  191.     private Node remove(Node node, E e) {
  192.         if (node == null) {
  193.             return null;
  194.         }
  195.         Node retNode;
  196.         if (e.equals(node.e)) {
  197.             if (node.right == null) {
  198.                 Node leftNode = node.left;
  199.                 node.left = null;
  200.                 size--;
  201.                 retNode = leftNode;
  202.             } else if (node.left == null) {
  203.                 Node rightNode = node.right;
  204.                 node.right = null;
  205.                 size--;
  206.                 retNode = rightNode;
  207.             } else {
  208.                 Node successor = minimum(node.right);
  209.                 successor.right = remove(node.right,successor.e);//由于removeMin没有维持balance，所以我们用remove
  210.                 successor.left = node.left;
  211.                 node.left = node.right = null;
  212.                 //size--; 在removeMin中已经维护size了
  213.                 retNode = successor;
  214.             }
  215.         } else if (e.compareTo(node.e) < 0) {
  216.             node.left = remove(node.left, e);
  217.             retNode = node;
  218.         } else {
  219.             node.right = remove(node.right, e);
  220.             retNode = node;
  221.         }
  223.         //否则retNode.height会有空指针异常
  224.         if (retNode == null) {
  225.             return null;
  226.         }
  228.         //更新高度
  229.         retNode.height = Math.max(getHeight(retNode.left),getHeight(retNode.right)) + 1;
  230.         //计算平衡因子
  231.         int balanceFactor = getBalanceFactor(retNode);
  232.         if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
  233.             return rightRotate(retNode);
  234.         }
  235.         if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
  236.             return leftRotate(retNode);
  237.         }
  238.         if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
  239.             retNode.left = leftRotate(retNode.left);
  240.             return rightRotate(retNode);
  241.         }
  242.         if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
  243.             retNode.right = rightRotate(retNode.right);
  244.             return leftRotate(retNode);
  245.         }
  246.         return retNode;
  247.     }
  248. }