AVL Tree

港控/mmm° 2022-04-04 12:17 99阅读 0赞

# 前言 #

希望读者

了解二叉搜索树

了解左旋右旋基本操作

[https://blog.csdn.net/hebtu666/article/details/84992363][https_blog.csdn.net_hebtu666_article_details_84992363]

直观感受直接到文章底部，有正确的调整策略动画，自行操作。

# 二叉搜索树    #

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。  
具体介绍和实现：https://blog.csdn.net/hebtu666/article/details/81741034

我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，

此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。

# AVL Tree #

在[计算机科学][Link 1]中，**AVL树**是最先发明的自平衡二叉查找树。**在AVL树中任何节点的两个子树的高度最大差别为1**，所以它也被称为**高度平衡树**。增加和删除可能需要通过一次或多次[树旋转][Link 2]来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

这种结构是对平衡性要求最严苛的self-Balancing Binary Search Tree。

旋转操作继承自self-Balancing Binary Search Tree

public class AVLTree extends AbstractSelfBalancingBinarySearchTree

# 旋转 #

上面网址中已经介绍了二叉搜索树的调整和自平衡二叉搜索树的基本操作（左旋右旋），上篇文章我是这样定义左旋的：

达到了 **看似** 更平衡的效果。

我们回忆一下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

看起来好像不是很平，对吗？我们转一下：

![20181217124804853.png][]

看起来平了很多。

**但！是！**

只是看起来而已。

我们知道。ABCD其实都是子树，他们也有自己的深度，如果是这种情况：

我们简化一下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

转之后(A上来，3作为A的右孩子，A的右子树作为新的3的左孩子）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]

没错，旋转确实让树变平衡了，这是因为，不平衡是由A的左子树造成的，A的左子树深度更深。

我们这样旋转实际上是让

A的左子树相对于B提上去了两层，深度相对于B，-2，

A的右子树相对于B提上去了一层，深度相对于B，-1.

而如果是这样的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3][]

旋转以后：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 4][]

依旧是不平的。

那我们怎么解决这个问题呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 5][]

先3的左子树旋转：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 6][]细节问题：不再讲解![20181217143832348.png][]

这样，我们的最深处又成了左子树的左子树。然后再按原来旋转就好了。

# 旋转总结 #

那我们来总结一下旋转策略：

## 单向右旋平衡处理LL： ##

由于在\*a的**左子树根结点的左子树上插入结点**，\*a的平衡因子由1增至2，致使以\*a为根的子树失去平衡，则需进行一次右旋转操作；

## 单向左旋平衡处理RR： ##

由于在\*a的**右子树根结点的右子树上插入结点**，\*a的平衡因子由-1变为-2，致使以\*a为根的子树失去平衡，则需进行一次左旋转操作；

## 双向旋转（先左后右）平衡处理LR： ##

由于在\*a的**左子树根结点的右子树上插入结点**，\*a的平衡因子由1增至2，致使以\*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。

## 双向旋转（先右后左）平衡处理RL： ##

由于在\*a的**右子树根结点的左子树上插入结点**，\*a的平衡因子由-1变为-2，致使以\*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

# 深度的记录 #

我们解决了调整问题，但是我们怎么发现树不平衡呢？总不能没插入删除一次都遍历一下求深度吧。

当然要记录一下了。

我们需要知道左子树深度和右子树深度。这样，我们可以添加两个变量，记录左右子树的深度。

但其实不需要，只要记录自己的深度即可。然后左右子树深度就去左右孩子去寻找即可。

这样就引出了一个问题：深度的修改、更新策略是什么呢？

# 单个节点的深度更新 #

本棵树的深度=（左子树深度，右子树深度）+1

所以写出节点node的深度更新方法：

private static final void updateHeight(AVLNode node) {
    //不存在孩子，为-1，最后+1，深度为0
            int leftHeight = (node.left == null) ? -1 : ((AVLNode) node.left).height;
            int rightHeight = (node.right == null) ? -1 : ((AVLNode) node.right).height;
            node.height = 1 + Math.max(leftHeight, rightHeight);
        }

# 写出旋转代码 #

配合上面的方法和文章头部给出文章Abstract Self-Balancing Binary Search Tree的旋转，我们可以AVL树的四种旋转：

private Node avlRotateLeft(Node node) {
            Node temp = super.rotateLeft(node);
            updateHeight((AVLNode)temp.left);
            updateHeight((AVLNode)temp);
            return temp;
        }
    
        private Node avlRotateRight(Node node) {
            Node temp = super.rotateRight(node);
            updateHeight((AVLNode)temp.right);
            updateHeight((AVLNode)temp);
            return temp;
        }
    
        protected Node doubleRotateRightLeft(Node node) {
            node.right = avlRotateRight(node.right);
            return avlRotateLeft(node);
        }
    
        protected Node doubleRotateLeftRight(Node node) {
            node.left = avlRotateLeft(node.left);
            return avlRotateRight(node);
        }

请自行模拟哪些节点的深度记录需要修改。

# 总写调整方法 #

我们写出了旋转的操作和相应的深度更新。

现在我们把这些方法分情况总写。

private void rebalance(AVLNode node) {
            while (node != null) {
                Node parent = node.parent;
                
                int leftHeight = (node.left == null) ? -1 : ((AVLNode) node.left).height;
                int rightHeight = (node.right == null) ? -1 : ((AVLNode) node.right).height;
                int nodeBalance = rightHeight - leftHeight;
    
                if (nodeBalance == 2) {
                    if (((AVLNode)node.right.right).height+1 == rightHeight) {
                        node = (AVLNode)avlRotateLeft(node);
                        break;
                    } else {
                        node = (AVLNode)doubleRotateRightLeft(node);
                        break;
                    }
                } else if (nodeBalance == -2) {
                    if (((AVLNode)node.left.left).height+1 == leftHeight) {
                        node = (AVLNode)avlRotateRight(node);
                        break;
                    } else {
                        node = (AVLNode)doubleRotateLeftRight(node);
                        break;
                    }
                } else {
                    updateHeight(node);//平衡就一直往上更新高度
                }
                
                node = (AVLNode)parent;
            }
        }

# 插入完工 #

我们的插入就完工了。

public Node insert(int element) {
            Node newNode = super.insert(element);//插入
            rebalance((AVLNode)newNode);//调整
            return newNode;
        }

# 删除 #

也是一样的思路，自底向上，先一路修改高度后，进行rebalance调整。

public Node delete(int element) {
            Node deleteNode = super.search(element);
            if (deleteNode != null) {
                Node successorNode = super.delete(deleteNode);
                //结合上面网址二叉搜索树实现的情况介绍
                if (successorNode != null) {
                    // if replaced from getMinimum(deleteNode.right) 
                    // then come back there and update heights
                    AVLNode minimum = successorNode.right != null ? (AVLNode)getMinimum(successorNode.right) : (AVLNode)successorNode;
                    recomputeHeight(minimum);
                    rebalance((AVLNode)minimum);
                } else {
                    recomputeHeight((AVLNode)deleteNode.parent);//先修改
                    rebalance((AVLNode)deleteNode.parent);//再调整
                }
                return successorNode;
            }
            return null;
        }
        /**
         * Recomputes height information from the node and up for all of parents. It needs to be done after delete.
         */
        private void recomputeHeight(AVLNode node) {
           while (node != null) {
              node.height = maxHeight((AVLNode)node.left, (AVLNode)node.right) + 1;
              node = (AVLNode)node.parent;
           }
        }
        
        /**
         * Returns higher height of 2 nodes. 
         */
        private int maxHeight(AVLNode node1, AVLNode node2) {
            if (node1 != null && node2 != null) {
                return node1.height > node2.height ? node1.height : node2.height;
            } else if (node1 == null) {
                return node2 != null ? node2.height : -1;
            } else if (node2 == null) {
                return node1 != null ? node1.height : -1;
            }
            return -1;
        }

请手动模拟哪里的高度需要改，哪里不需要改。

# 直观表现程序 #

如果看的比较晕，或者直接从头跳下来的同学，这个程序是正确的模拟了，维护AVL树的策略和一些我没写的基本操作。大家可以自己操作，直观感受一下。

[https://www.cs.usfca.edu/~galles/visualization/AVLtree.html?utm\_source=qq&utm\_medium=social&utm\_oi=826801573962338304][https_www.cs.usfca.edu_galles_visualization_AVLtree.html_utm_source_qq_utm_medium_social_utm_oi_826801573962338304]

[https_blog.csdn.net_hebtu666_article_details_84992363]: https://blog.csdn.net/hebtu666/article/details/84992363
[Link 1]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/9132
[Link 2]: https://baike.baidu.com/item/%E6%A0%91%E6%97%8B%E8%BD%AC
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20220404/c26cb2f5fe60470a9347805ba821958b.png
[20181217124804853.png]: /images/20220404/4ac2ab18212642b7a72360d7409b8569.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20220404/9c8d63a5c9f04fc09892d60dc9bc0aec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2]: /images/20220404/7efe9bc4078f4bbe9703c624a77579d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3]: /images/20220404/f9914a921b4d47c4ad465cb6517199ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 4]: /images/20220404/927a69f563c648b5847c00004b42f9fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 5]: /images/20220404/9bcfaab0ec934165b32b9f2abfeea2d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20181217144129237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[20181217143832348.png]: /images/20220404/818f39de55c64c18a68fd4a93df66743.png
[https_www.cs.usfca.edu_galles_visualization_AVLtree.html_utm_source_qq_utm_medium_social_utm_oi_826801573962338304]: https://www.cs.usfca.edu/~galles/visualization/AVLtree.html?utm_source=qq&utm_medium=social&utm_oi=826801573962338304