数据结构-平衡二叉树

数据结构-平衡二叉树

目录

​​平横二叉树的定义​​​​平横二叉树的生成​​​​为什么要命名为RR旋转？​​​​平衡二叉树的查找​​

平横二叉树的定义

平衡因子，节点的左右子树的高度差定义为该节点的平衡因子。

子树节点高度差的绝对值不大于1即为平衡二叉树。即节点的平衡因子不大于1.

直观点说就是：某个节点的左子树在0层而右子树已经到-2层就失衡了

平横二叉树的生成

平衡二叉树在插入数据的时候首先要保证当前数据进入平衡二叉树后是否平衡，一旦出现了不平衡的情况需要进行一个调整。这个调整的步骤就是生成平衡二叉树的关键所在,。

下面使用一组数据进行说明

数据{11,21,31,41,1,91,0}

依次序生成二叉树

此时元素11的平衡因子为2，已经出现了失衡。那么可以采用（RR平衡旋转）

为什么要命名为RR旋转？

失衡的节点是11 其右子树（R）的右节点（R） 导致失衡

接着继续进行元素的插入

此时元素31的平衡因子已经失衡，对失衡的二叉树采用RR旋转即可平衡

继续插入元素，可以看到不平衡的二叉树(LL平衡旋转)完成了二叉树的平衡

以上我们即可完成该组元素插入。

总结：节点左子树导致失衡采用LL旋转，右子树失衡采用RR旋转

但是还有一种情况：当某次平衡旋转不能够完成平衡二叉树怎么办呢？下面举例来看：

以上经过一次平衡旋转后无法达成平衡二叉树.那么需要按照下面的步骤进行：

以上先对3,7进行左旋转接进行右旋转，这种操作称为LR平衡旋转

接着进行RL平衡旋转的一个例子演示：

观察RL平衡旋转这个例子进行总结总结：失衡节点（平衡因子大于1）的左孩子的右子树上插入新节点导致失衡采用LR平衡，失衡节点的右孩子的左子树上插入新节点导致了失衡使用的是RL平衡

平衡二叉树的查找

平衡二叉树的最大深度为O(log2n),平均查找长度为O(log2n)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。