平衡二叉树旋转

时间:2021-05-29 17:31:21

  首先附上本文节选地址:http://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html

 

  二叉查找树不是严格的O(logN),导致了在真实场景中没有用武之地,谁也不愿意有O(N)的情况发生,作为一名码农,肯定会希望能把“范围查找”做到地球人都不能优化的地步。 当有很多数据灌到我的树中时,我肯定会希望最好是以“完全二叉树”的形式展现,这样我才能做到“查找”是严格的O(logN),比如把这种”树“调正到如下结构。

     平衡二叉树旋转

这里就涉及到了“树节点”的旋转,也是我们今天要聊到的内容。

 

一:平衡二叉树(AVL)

1:定义

       1、父节点的左子树和右子树的高度之差不能大于1,也就是说不能高过1层,否则该树就失衡了,此时就要旋转节点,在

编码时,我们可以记录当前节点的高度,比如空节点是-1,叶子节点是0,非叶子节点的height往根节点递增,比如在下图

中我们认为树的高度为h=2。

  2、它的左子树和右子树都是平衡二叉树。

平衡二叉树旋转

2:旋转

    节点再怎么失衡都逃不过4种情况,下面我们一一来看一下。

① 左左情况(左子树的左边节点)

平衡二叉树旋转

我们看到,在向树中追加“节点1”的时候,根据定义我们知道这样会导致了“节点3"失衡,满足“左左情况“,可以这样想,把这

棵树比作齿轮,我们在“节点5”处把齿轮往下拉一个位置,也就变成了后面这样“平衡”的形式,如果用动画解释就最好理解了。

 

② 右右情况(右子树的右边节点)

平衡二叉树旋转

同样,”节点5“满足”右右情况“,其实我们也看到,这两种情况是一种镜像,当然操作方式也大同小异,我们在”节点1“的地方

将树往下拉一位,最后也就形成了我们希望的平衡效果。

 

③左右情况(左子树的右边节点)

平衡二叉树旋转

从图中我们可以看到,当我们插入”节点3“时,“节点5”处失衡,注意,找到”失衡点“是非常重要的,当面对”左右情况“时,我们将

失衡点的左子树进行"右右情况旋转",然后进行”左左情况旋转“,经过这样两次的旋转就OK了,很有意思,对吧。

 

④右左情况(右子树的左边节点)

平衡二叉树旋转

这种情况和“情景3”也是一种镜像关系,很简单,我们找到了”节点15“是失衡点,然后我们将”节点15“的右子树进行”左左情况旋转“,

然后进行”右右情况旋转“,最终得到了我们满意的平衡。