数据结构-树（二）：平衡树AVL树

╰半橙微兮° 2022-04-23 15:20 267阅读 0赞

#### 设计初衷 ####

*  树主要是链表数据结构的变形，目的是实现各种操作的O(logN)时间复杂度，从而优化链表的O(N)时间复杂度。
 *  对于二叉查找树来说，对于每个节点，左子树的值均小于该节点的值，右节点的值均大于该节点值。故当数据分布不均匀时，可能会导致所有节点都在根节点的左子树或者右子树，从而退化回了链表，造成性能问题。
 *  所以为了解决这个问题，AVL树通过对树节点的旋转操作，保证每个节点的左右子树高度差最大为1来避免退化为链表，实现相对平衡，各种操作平均复杂度为O(logN)。

#### AVL树的特性 ####

*  AVL树：每个节点的左右子树的高度差最大为1的二叉查找树。当因为插入操作导致某个节点不符合AVL树的特性时，需要对受到影响的节点（即左右子树的高度差大于1的节点）进行旋转操作来使之重新符合AVL树的每个节点的左右子树的高度差最大为1的特性。
 *  节点的高度：从该节点到其子节点的最长路径。树的高度为根节点到叶子节点中最长的路径的长度。
 *  节点的深度：从根节点到该节点的路径长度，同一深度的节点的高度不一定相等。
    
        /** * 任意树节点的高度 * @param treeNode，输入可以是任意节点，如果是根节点则是树的高度 * @param <T> * @return */
        public <T> int treeNodeHeight(BinaryTree<T> treeNode) { 
            if (treeNode == null) { 
                return -1;
            }
        
            return 1 + Math.max(treeNodeHeight(treeNode.left), treeNodeHeight(treeNode.right));
        }
        
        /** * 树的深度 * @param root，输入只能是树的根节点，计算树的深度，如果是其他节点，则是到跟节点的距离，不是这样计算。 * @param <T> * @return */
        public <T> int treeDeep(BinaryTree<T> root) { 
            if (root == null) { 
                return -1;
            }
            
            return 1 + Math.max(treeDeep(root.left), treeDeep(root.right));
        }
 *  破坏平衡的两种情况：外边插入（左子树的左子节点，右子树的右子节点），内边插入（左子树的右子节点，右子树的左子节点）。
 *  外边插入：单旋转
 *  内边插入：双旋转

### 节点插入与平衡调整 ###

*  由于AVL树是一棵二叉查找树，节点定义如下：除了左右节点定义外，每个节点还包含高度height。（代码引自《数据结构与算法分析 Java语言描述》第三版）
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]
 *  插入过程为：首先是按照二叉查找树（左子树的值小于根节点的值，右子树的值大于根节点的值）插入这个节点，实现如下：平衡旋转操作在balance方法定义。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 1]
 *  如果插入之后，没有节点的高度失衡，则插入操作结束。否则需要根据是外边插入还是内边插入来决定是单旋转和双旋转，实现如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 2]
 *  32行代码表示在左子树的左节点失衡（39行为在右子树的右节点失衡，情况类似），故是“外边插入”，执行单旋转，rotateWithLeftChild，旋转过程的实现和示意图如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 3]
 *  35行表示为左子树的右节点失衡（41行为右子树的左节点失衡，情况类似），故是“内边插入”，执行双旋转：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 4]

#### 删除节点操作与旋转平衡 ####

*  删除操作跟插入操作类似，也需要在删除之后调用balance方法对失衡节点进行调整，不过balance方法不能完全重用以上的balance方法，因为删除操作情况更加复杂。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]: /images/20220226/c79d84e0c6e4422abb90a7472075670f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 1]: /images/20220226/fbe00697309844488e6e83cf4600bfa3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 2]: /images/20220226/6585d24437ba45e4a0bd880a9fb8f33d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 3]: /images/20220226/65a0cc6f9acb447aa86fc8d5537d842a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 4]: /images/20220226/8ed2adbac3cd4fe388b6e182b6111eb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 5]: /images/20220226/c582fc8762744d7ab707af1641a746cf.png