数据结构之平衡有序二叉树

数据结构之平衡有序二叉树

我们知道引入树是为了提高数据存储，读取的效率。可是有的二叉树并不能提高效率，例如下面的这个树。

这是一种极端的情况，实际上它已经和链表一样了，现在对它进行查询，时间复杂度已经成为了O（n）。而我们为了避免这种情况的出现，就引入了平衡二叉树。

平衡二叉树是在有序二叉树的基础上保证左右子树的高度差不超过1。

那我们如何把一个不平衡的有序二叉树变成平衡的有序二叉树呢？答案当然就是：旋转。

而旋转又分为4种：LL,LR,RL,RR。

那如何判断是哪种旋转类型呢？

1. 找到不平衡的节点；
2. 找到因为它的插入而造成树不平衡的节点；
3. 让不平衡的节点向造成不平衡的节点走两步，怎么走的就是什么类型。

下面咱们就来分别讨论这四种旋转方式。

LL型旋转

1. 将不平衡节点（A）的左子节点（B）提升为新的根节点；
2. 将原来的不平衡节点（A）降为B的右子节点；
3. 将剩下的各子树按照大小关系连接。

例子

 RR型旋转

RR型旋转和LL型旋转类似。

 

1. 将不平衡节点（A）的右子节点（B）提升为新的根节点；
2. 将原来的不平衡节点（A）降为B的左子节点；
3. 将剩下的各子树按照大小关系连接。

 例子

 LR型旋转

1.  将B的右子节点提升为新的根节点；
2. 将原来的根节点降为现在根节点（C）的右子节点；
3. 将各子树按照大小关系连接。

例子 

 RL型旋转

RL型旋转和LR型旋转类似。

1. 将B的左子节点提升为新的根节点；
2. 将原来的根节点降为现在根节点（C）的左子节点；
3. 将各子树按照大小关系连接。

例子 

 最后来一个综合的练习吧。

将列｛25，27，30，12，11，18，14，20，15｝构建成一个平衡有序二叉树。