数据结构-二叉平衡树-二.平衡二叉树的调整

在右子树的右子树上的插入做RR插入

把被破坏节点的右子树变成跟节点并把这个右子树的左子树挂载到原来被破坏的结点的右子树,被破坏的节点作为右儿子

插入节点在被破坏者右边的右边是RR

不一定插在某个节点的右边

在左子树的左子树上的插入做LL插入

把被破坏节点的左子树变成跟节点并把这个左子树的右子树挂载到原来被破坏的结点的左子树,被破坏的节点作为左儿子

插入节点在被破坏者左边的左边是LL

两个节点的平衡性被破坏了,只要考虑最下面的节点这个节点平衡了上面节点自然就平衡了

被破坏结点左边的右边插入,叫做LR插入

所以需要关注May,Aug,Mar三个结点将这三个结点的中间值结点变为跟结点,这里的中间结点是Mar所以需要先将提上来,左旋转,然后再进行右旋转

第一次旋转(左旋转)

第二次旋转(右旋转)

RL旋转与LR旋转相似

上一篇:C++设计模式:建造者模式(Builder) 房屋建造案例-优点:


下一篇:【青牛科技】汽车收音机调频中频放大器——D1145