AVL树的实现

た入场券 2022-06-02 03:00 137阅读 0赞

前面笔者介绍了[二叉搜索树的一般实现][Link 1]和[平衡二叉树的实现原理][Link 2]。  
本篇文章将继续前文的平衡搜索树来介绍一种具体的平衡搜索树—AVL树。

### AVL树的特性 ###

AVL树中，对于任一节点V，其左右子树的高度差不能超过1。这个高度差定义为平衡因子。

为了判断AVL树的平衡性，在沿用前文的平衡二叉树的模版代码中，需要添加如下方法：

public Boolean isAvlBalanced(TreeNode node) {
            //获取平衡因子
            int balance = node.right.height - node.left.height;
    
            return balance > 2 && balance < -2; 
        }

### 失衡和重平衡 ###

AVL树与常规的二叉搜索树一样，也应支持插入、删除等动态修改操作。但经过这类操作之后，节点的高度可能发生变化，以致于不再满足AVL树的条件。

观察下图的插入操作，在对图(b)一个AVL树插入’M’，于是，节点’N’、’R’和’G’ 都将失衡。类似地，删除’Y’之后， 也会如图(a)所示导致节点’R’的失衡。

![这里写图片描述][SouthEast]

如此因节点x的插入或删除而暂时失衡的节点，构成失衡节点集，记作失衡节点集UT(x)。请注意，若x为被摘除的节点，则UT(x)仅含单个节点; 但若x为被引入的节点，则UT(x)可能包含多个节点。  
从对UT(x)的分析入手，分别介绍使失衡搜索树重新恢复平衡的调整算法。

#### 节点插入失衡的恢复算法 ####

不难看出，新引入节点x后，UT(x)中的节点都是x的祖先，且高度不低于x的祖父。以下，将其中的最深者记作g(x)—最深者即为高度最小的节点。在x与g(x)之间的通路上，设p为g(x)的孩子，v为p的孩子。注意， 既然g(x)不低于x的祖父，则p必是x的真祖先。

首先，需要找到如上定义的g(x)。为此，可从x出发沿parent指针逐层上行并核对平衡因子， 首次遇到的失衡祖先即为g(x)。既然原树是平衡的，故这一过程只需O(logn)时间。

既然g(x)是因x的引入而失衡，则p和v的高度均不会低于其各自的兄弟。因此，可在g(x)的左右孩子中寻找高度最高的节点p,用同样的方法在节点p的左右孩子中寻找节点最高的孩子v。

确定g(x),p,v三个节点后，将根据三个节点的联接方向，采用不同的局部调整方案，分述如下：

**单旋**

![这里写图片描述][SouthEast 1]

如上图(a)所示，设v是p的右孩子，p是g的右孩子。**这种情况必是在v的子树中插入的新的节点x，使得g失衡，图(a)的阴影部分为插入x的节点，其兄弟为空。**采用前文[平衡二叉树的实现原理][Link 2]中的逆时针zag已g为轴旋转之后，使得g重新平衡。旋转后的结果图(b)所示。根据搜索树的等价原理来看。a,b两树的等价的。

同理，如果v是p的左孩子，p是g的左孩子。则可通过顺时针zig来重平衡。

**双旋**

![这里写图片描述][SouthEast 2]

如上图(a)所示，设节点v是p的左孩子，而p是g的右孩子。

这种情况，也必是由于在子树v中插入了新节点x，而致使g不再平衡。同样地，在图中以虚线联接的每一对灰色方块中，其一对应于新节点x，另一为空。

此时，可先做p为轴的顺时针旋转，得到如图(b)所示的一棵等价二叉搜索树。

再做g为轴的逆时针旋转zag，得到如图(c)所示的另一棵等价二叉搜索树。  
此类分别以父子节点为轴、方向互逆的连续两次旋转，合称“双旋”。可见，经如此调整之后，g亦必将重新平衡。不难验证，通过zag(p)和zig(g)可以处理对称的情况。

**无论单旋或双旋，经局部调整之后，不仅g(x)能够重获平衡， 而且局部子树的高度也必将复原。这就意味着，g(x)以上所有祖先的平衡因子亦将统一地复原，也意味着在AVL树中插入新节点后，仅需不超过两次旋转，即可使整树恢复平衡。**

AVL树中节点的插入：

**这段代码中的3+4算法即在本文后面**

/**
         * 添加子节点
         * @throws Exception 
         */
        public TreeNode addNode(Double data) {
            TreeNode inTree = this.search(data);
    
            if(inTree.data != null) {
                return inTree;
            }
    
            inTree.data = data;
            if(inTree.data < inTree.parent.data) {
                inTree.parent.left = inTree;
            }else if(inTree.data > inTree.parent.data) {
                inTree.parent.right = inTree;
            }
    
            //从新节点的parent出发，依次向上出发，寻找失衡的最深节点g
            for(TreeNode g = inTree.parent;g!=null;g = g.parent){
    
                  if(!isAvlBalanced(g)) {
    
                      TreeNode v = this.tallerChild(tallerChild(g));
                      //当节点g失衡，使用3+4算法使之恢复平衡
                      TreeNode balancedTree = rotateAt(v);
                      //g.parent与以g为轴旋转后的子树链接
                      //g.parent已经在旋转中得到更新
                      if(g != root && g.parent.left == g) {
                          g.parent.setLeft(balancedTree);
                      }else if(g != root && g.parent.right == g) {
                          g.parent.setRight(balancedTree);
                      }else {
                          root = balancedTree;
                      }
                      //旋转过程中已经更新高度
                      break;
                  }else {
                      //g未失衡。但需要更新g的高度
                      this.updateHeight(g);
                  }
            }
    
            return inTree;
        }

**效率**

插入算法首先按照二叉搜索树的常规算法，在O(logn)时间内插入新节点x。  
既然原树是平衡的，故至多检查O(logn)个节点即可确定g(x);  
如有必要，至多旋转两次，即可使局部乃至全树恢复平衡。由此可见，AVL树的节点插入操作可以在O(logn)时间内完成

#### 节点删除失衡的恢复算法 ####

与插入操作十分不同，在摘除节点x后，以及随后的调整过程中，失衡节点集UT(x)始终至多只含一个节点。**而且若该节点g(x)存在，其高度必与失衡前相同。 另外还有一点重要的差异是，g(x)有可能就是x的父亲。**

与插入操作同理，从被删除的节点沿parent指针上行，经过O(logn)时间即  
可确定g(x)位置。**作为失衡节点的g(x)，在不包含x的一侧，必有一个非空孩子p，且p的高度至少为1（因为在删除前，原树的守恒的）。**

于是，可按以下规则从p的两个孩子(其一可能为空)中选出节点v:  
若两个孩子不等高， 则v取作其中的更高者;  
否则，优先取v与p同向者(亦即，v与p同为左孩子，或者同为右孩子)。

以下不妨假定失衡后g(x)的平衡因子为+2(为-2的情况完全对称)。根据祖孙三代节点 g(x)、p和v的位置关系，通过以g(x)和p为轴的适当旋转，同样可以使得这一局部恢复平衡。

**单旋**

![这里写图片描述][SouthEast 3]

如上图(a)所示，由于在T3中删除了节点而致使g不再平衡，但**p与g的关系与v与p的关系一致(均为左孩子)， 通过以g(x)为轴zig顺时针旋转一次即可恢复局部的平衡。**平衡后的局部子树如图(b)所示。

**p与g的关系与v与p的关系一致(均为右孩子)，通过以g(x)为轴zag逆时针旋转一次即可恢复局部的平衡**

要保证原树是平衡的，或p子树的平衡的。上图(a)中以虚线联接的灰色方块所对应的节点，不能同时为空; T2底部的灰色方块所对应的节点，可能为空，也可能非空。

**双旋**

![这里写图片描述][SouthEast 4]

如图上(a)所示，g(x)失衡时**若g与p的关系与p与v的关系不一致，一个为左子树，一个为右子树。则先按p为轴，进行一次旋转(v是p的右孩子，进行zag逆时针。v是p的左孩子，进行zig顺时针)**。

与图(a)为例子，则经过以p为轴的一次逆时针旋转之 后(图(b))，即可转化为图(a)的情况，**g与v的关系与p与v的关系一致**。再已g为轴进行一次旋转，则可恢复全树平衡。

**失衡传播**

与插入操作不同，在删除节点之后，尽管也可通过单旋或双旋调整使局部子树恢复平衡，但复平衡之后，局部子树的高就全局而言，依然可能再次失衡。若能仔细观察单旋的图(b)和双旋图(c)，则不难发现:

g(x)高度却可能降低。这与引入节点之后的重平衡后完全不同，在插入节点时，后者不仅能恢复子树的平衡性，也同时能恢复子树的高度。

设g(x)复衡之后，局部子树的高度的确降低。此时，若g(x)原本属于某一更高祖先的更短 分支，则因为该分支现在又进一步缩短，从而会致使该祖先失衡。在摘除节点之后的调整过程中， 这种由于低层失衡节点的重平衡而致使其更高层祖先失衡的现象，称作“失衡传播”。

失衡传播的方向必然自底而上，而不致于影响到后代节点。在此过程中的任一时刻，至多只有一个失衡的节点;高层的某一节点由平衡转为失衡，只可能发生在下层失衡节点恢复平衡之后。因此，可沿parent指针逐层遍历所有祖先，每找到一个失衡的祖先节点，即可套用以 上方法使之恢复平衡。

AVL树中节点的删除：

public TreeNode delNode(Double data) {
            TreeNode inTree = this.search(data);
            TreeNode next = null; //被删除节点的位置
    
            if(inTree.data == null) {
                return null;
            }
    
            TreeNode hot = inTree.parent;
    
            if(inTree.left == null) {
    
                //接替被删除的节点的子树
                if(hot.left == inTree) {
                    hot.left.setLeft(inTree.right);
                }else {
                    hot.right.setRight(inTree.right);
                }
    
                //开始孤立inTree
                inTree.right.parent = hot;
                inTree.parent = null;
                inTree.right = null;
    
                //从hot 向上出发，逐层检查
                for(TreeNode g = hot; g!=null; g = g.parent) {
                    if(!isAvlBalanced(g)) {
                        this.updateHeight(rebalance(g));
                        //删除节点存在失衡传播，不进行break
                    }
                    //即g未失衡，删除节点后的旋转中也会降低高度
                    this.updateHeight(g);
                }
                return inTree;
            }else if(inTree.right == null) {
    
                if(hot.left == inTree) {
                    hot.left.setLeft(inTree.left);
                }else { 
                    hot.right.setRight(inTree.left);
                }
    
                //开始孤立inTree
                inTree.left.parent = hot;
                inTree.parent = null;
                inTree.left = null;
    
                //从hot 向上出发，逐层检查
                for(TreeNode g = hot; g!=null; g = g.parent) {
                    if(!isAvlBalanced(g)) {
                        this.updateHeight(rebalance(g));
                        //删除节点存在失衡传播，不进行break
                    }
                    //即g未失衡，删除节点后的旋转中也会降低高度
                    this.updateHeight(g);
                }
    
                return inTree;
            }else {
    
                //当左右节点都存在时，先获取其在中序遍历中的直接后继，直接后继next一定没有左孩子
                next= this.nextForIn(inTree);
                swap(inTree, next);
                //如果其直接后继为其孩子(右孩子)，则被删除的节点之后的节点属于next的右孩子
                if(inTree == next.parent) {
                    next.parent.right = next.right;
                }else {
                //如果其直接后继不是其孩子，则是其右孩子的左子树的某个节点，则被删除的节点之后的节点属于next的左孩子
                    next.parent.left = next.right;
                }
    
                //开始孤立next (next无左孩子，也一定是next.parent.left)
                next.parent.left = next.right;
                if(next.right!=null) {
                  next.right.parent = next.parent;
                }
                next.parent = null;
                next.right = null;
    
                //从hot 向上出发，逐层检查
                for(TreeNode g = next.right; g!=null; g = g.parent) {
                    if(!isAvlBalanced(g)) {
                        this.updateHeight(rebalance(g));
                        //删除节点存在失衡传播，不进行break
                    }
                    //即g未失衡，删除节点后的旋转中也会降低高度
                    this.updateHeight(g);
                }
    
                return next;
            }
        }
    
        public TreeNode rebalance(TreeNode g) {
    
            TreeNode v = this.tallerChild(tallerChild(g));
              //当节点g失衡，使用3+4算法使之恢复平衡
              TreeNode balancedTree = rotateAt(v);
              //g.parent与以g为轴旋转后的子树链接
              //g.parent已经在旋转中得到更新
              if(g != root && g.parent.left == g) {
                  g.parent.setLeft(balancedTree);
                  return g;
              }else if(g != root && g.parent.right == g) {
                  g.parent.setRight(balancedTree);
                  return g;
              }else {
                  root = balancedTree;
                  return root;
              }
              //旋转过程中已经更新高度
        }

**效率**  
由上可见，较之插入操作，删除操作可能需在重平衡方面多花费一些时间。不过，既然需做重平衡的节点都是x的祖先，故重平衡过程累计只需不过O(logn)时间。综合各方面的消耗，AVL树的节点删除操作总体的时间复杂度依然是O(logn)。

#### 统一重平衡算法 ####

上述重平衡的方法，需要根据失衡节点及其孩子节点、孙子节点的相对位置关系，分别做单旋或双旋调整。按照这一思路直接实现调整算法，代码量大且流程繁杂，必然导致调试困难且容易出错。为此，介绍一种更为简明的统一处理方法。

无论对于插入或删除操作，新方法也同样需要从刚发生修改的位置x出发逆行而上，直至遇到最低的失衡节点g(x)。于是在g(x)更高一侧的子树内，其孩子节点p和孙子节点v必然存在， 而且这一局部必然可以g(x)、p和v为界，分解为四棵子树，按照上图中的惯例， 将它们按中序遍历次序重命名为T0至T3。

若同样按照中序遍历次序，重新排列g(x)、p和v，并将其命名为a、b和c，则这一局部的中序遍历序列应为:

\{ T0, a, T1, b, T2, c, T3 \}

这就意味着，这一局部应等价于如下图所示的子树。更重要的是，纵观上图可见，这四棵子树的高度相差不超过一层，故只需如下图所示将这三个节点与四棵子树重新 “组装”起来，恰好即是一棵AVL树!

![这里写图片描述][SouthEast 5]

实现代码如下所示：

/**
         * 按照“3 + 4”结构联接3个节点及其四棵子树，迒回重组后的局部子树根节点位置(即b)
         * @author wangxi
         * 
         */
        public TreeNode connect34(TreeNode a, TreeNode b, TreeNode c, TreeNode t0, TreeNode t1, TreeNode t2, TreeNode t3) {
            a.left = t0;
            a.right = t1;
    
            if(t0!=null) {
                t0.parent = a;
            }
    
            if(t1!=null) {
                t1.parent = b;
            }
    
            c.left = t2;
            c.right = t3;
    
            if(t2!=null) {
                t2.parent = c;
            }
    
            if(t3!=null) {
                t3.parent = c;
            }
    
            b.left = a;
            b.right = c;
    
            a.parent = b;
            c.parent = b;
    
            return b;
        }
    
       /**
         *  BST节点旋转变化统一算法(3节点 + 4子树)，返回调整之后局部子树根节点的位置
         *  参数只需传入节点v即可
         * @author wangxi
         *
         */
    
        public TreeNode rotateAt(TreeNode v) {
              TreeNode p = v.parent;
              TreeNode g = p.parent;
              //根据g p v三者的关系，分四种情况
    
              //单旋：
              //p ，v ,g三者关系一致，均为左子树。则按g为轴顺时针zig旋转
              if(p.left == v && g.left == p) {
                  p.parent = g.parent;
                  return this.connect34(v, p, g, v.left, v.right, p.right, g.right);
              }
    
              //p ，v ,g三者关系一致，均为右子树。则按g为轴逆时针zag旋转
          if(p.right == v && g.right == p) {
              p.parent = g.parent;
              return this.connect34(g, p, v, g.left, p.left, v.left, v.right);
              }
    
              //双旋：
              //p ，v ,g三者关系不一致，v是p的左子树，p是g的右子树。则先按p为轴顺时针zig旋转,再按g为轴逆时针zag旋转
          if(p.left == v && g.right == p) {
              v.parent = g.parent;
              return this.connect34(p, v, g, p.left, v.left, v.right, g.right);
    
          }
              //p ，v ,g三者关系不一致，v是p的右子树，p是g的左子树。则先按p为轴逆时针zag旋转,再按g为轴顺时针zig旋转
          if(p.right == v && g.left == p) {
              v.parent = g.parent;
              return this.connect34(g, v, p, g.left, v.left, v.right, p.right);
    
          }
              return null;
        }

比对即可看出，统一调整算法的效果，的确与此前的单旋、 双旋算法完全一致。该算法的复杂度也依然是O(1)。

[Link 1]: http://blog.csdn.net/canot/article/details/78942809
[Link 2]: http://blog.csdn.net/canot/article/details/78943516
[SouthEast]: /images/20220602/b34e8c60b9cb4f2f8a6224c7339da890.png
[SouthEast 1]: /images/20220602/4a9b1fd504324037bef5a7e60850b9dc.png
[SouthEast 2]: /images/20220602/5f242208bf3e4935a3880e4aabd218ca.png
[SouthEast 3]: /images/20220602/fddb3df6139946478b6206b6840f9f73.png
[SouthEast 4]: /images/20220602/09257bbdfedc48aca186b976a6ee0a7f.png
[SouthEast 5]: /images/20220602/4f862f862f984261a0c309ed53b8d833.png