如何将有序树转化为平衡二叉树

如何将有序树转化为平衡二叉树

平衡二叉树：在有序二叉树基础上左右子树高度高度差不超过1.

目的：构建有序二叉树的目的是降低时间复杂度，有序二叉树查找元素的时间复杂度在O（logn）-O(n)之间，如果插入的序列为1,2,3,4,5,6,7，那么它们构建的有序二叉树就是一个链表，所以这样的有序二叉树时间复杂度是O（n），所以让有序二叉树变为一个平衡二叉树让它的时间复杂度降为O（logn）级别的

转为平衡二叉树的类型基本上有以下四种类型：LL型、RR型、LR型、RL型，我们通过旋转的方式将它们转为平衡二叉树

有序二叉树不平衡时我们首先要经历以下三种步骤：

1）找到不平衡节点

2）找到谁的插入造成了不平衡

3）让不平衡的节点向造成不平衡的节点走两步

LL型：

示例：

 

步骤：

1.将不平衡节点的左子节点提升为新根节点

2.将原来不平衡节点降为新根节点的右子节点

3.将各子树按大小关系排列

按以上步骤将LL型示例转换为平衡二叉树如下图所示：

 

RR型：

示例：

 

步骤：

1.将不平衡节点的右子节点提升为新根节点

2.将原来不平衡节点降为新根节点的左子节点

3.将各子树按大小关系排列

按以上步骤将LL型示例转换为平衡二叉树如下图所示：

 

LR型：

示例：

 

步骤：

1.将不平衡节点的左子节点的右子节点提升为新根节点

2.将原来根节点降为新根节点的右子节点

3.将各子树按大小关系排列

按以上步骤将LL型示例转换为平衡二叉树如下图所示：

 

RL型：

示例：​​​​​​​

 

步骤：

1.将不平衡节点的右子节点的左子节点提升为新根节点

2.将原来根节点降为新根节点的左子节点

3.将各子树按大小关系排列

按以上步骤将LL型示例转换为平衡二叉树如下图所示：