美文网首页算法
数据结构之完全二叉树&二叉平衡树

数据结构之完全二叉树&二叉平衡树

作者: 李2牛 | 来源:发表于2018-05-10 19:11 被阅读0次

完全二叉树

叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。堆是一种完全二叉树。


二叉平衡树( AVL 树)

特征:任何一节点的左右子树的高度差不超过 1

意义:解决了二叉树退化成链表的问题,将插入、查找、删除的时间复杂度维持在 log(N).

二叉树
二叉平衡树

二叉平衡树节点的定义

class Node{
    int value;
    int bf;
    Node left;
    Node right;
    Node(){}
    Node(int value){
        this.value = value;
    }
}

二叉平衡树的不平衡调整

插入删除节点会导致不平衡的出现,四种不平衡情况如下


四种不平衡的情况
  1. 左左:6的左子树高度比6的右子树大2,3的左子树高度比3的右子树大
  2. 左右:6的左子树高度比6的右子树大2,2的右子树高度比2的左子树大
  3. 右左:2的右子树高度比2的左子树大2,5的左子树高度比5的右子树大
  4. 右右:2的右子树高度比2的左子树大2,4的右子树高度比4的左子树大

左左和右右相似,一次旋转即可。左左需要一次右旋转,而右右需要一次左旋转。

左左情况需要右旋转

实现代码:

//右旋转---针对左左
rightRotate(Node kidTreeRoot){
        Node newNode = kidTreeRoot.left;
        kidTreeRoot.left = newNode.right;
        newNode.right = kidTreeRoot;
        kidTreeRoot = newNode; 
    }
//左旋转---针对右右
leftRotate(Node kidTreeRoot){
        Node newNode = kidTreeRoot.left;//保存根节点的左节点
        kidTreeRoot.right = newNode.left;
        newNode.left = kidTreeRoot;
        kidTreeRoot = newNode;
    }

左右和右左需要两次旋转。

下图是左右的情况,右左类似。


左右情况需要两次旋转

最后针对根节点的左子树高度大于根节点右子树的情况的调整方法如下:

void leftBalance(Node kidTreeRoot){
        Node L = kidTreeRoot.left;
        Node Lr ;
        switch(L.bf){
            case 1://左高,左左情况
                kidTreeRoot.bf = L.bf = 0;//调整为平衡
                rightRotate(kidTreeRoot);
                break;
            case -1://右高,左右情况
                Lr= L.right;
                switch(Lr.bf){
                    case 1://左边高对应 图1
                        L.bf = 0;
                        kidTreeRoot.bf = 0;
                        break;
                    case 0:
                        kidTreeRoot.bf = 0;//图2
                        L.bf = 0;
                        break;
                    case -1://图3
                        L.bf = 1;
                        kidTreeRoot.bf = 0;
                        break;
                }
                leftRotate(L);
                Lr.bf = 0;
                rightRotate(kidTreeRoot);

        }
    }
1. L.bf= -1 Lr.bf = 1
2. L.bf= -1 Lr.bf = 0
3. L.bf= -1 Lr.bf = -1

另一个方向的原理十分相似

相关文章

  • 不可多得的后端架构师技术图谱!内附参考资料!

    数据结构 二叉树 完全二叉树 平衡二叉树 二叉查找树(BST) 红黑树 B-,B+,B*树 LSM 树 队列 集合...

  • 后端架构师技术图谱

    数据结构队列集合链表、数组字典、关联数组栈树二叉树完全二叉树平衡二叉树二叉查找树(BST)红黑树B-,B+,B*树...

  • 后端架构师技术图谱(一)

    数据结构队列集合链表、数组字典、关联数组栈树二叉树完全二叉树平衡二叉树二叉查找树(BST)红黑树B-,B+,B*树...

  • 数据结构 - 概要

    数组 链表 堆/栈/队列 树 数据结构 - 二叉树数据结构 - 二叉查找树数据结构 - 平衡二叉树数据结构 - A...

  • 数据结构---堆

    导语 堆的逻辑数据结构实际上是一个可以使用数组实现的完全二叉树(堆也一定是平衡二叉树),所以学习堆,完全二叉树不是...

  • 二叉树 :有左右之分,次序不能颠倒 完全二叉树是一种效率很高的数据结构,二叉排序树要借助平衡性来实现,而平衡性基于...

  • 后端架构师技术图谱

    后端架构师技术图谱 最后更新于20180502 数据结构队列集合链表、数组字典、关联数组栈树二叉树完全二叉树平衡二...

  • Java数据结构之树

    数据结构之 树 二叉树每个节点最多有两个子树的树结构,在二叉树的概念下又衍生出满二叉树和完全二叉树。满二叉树除最后...

  • 树与二叉树

    **树 ** 二叉树 满二叉树 完全二叉树 三种遍历方法 树与二叉树的区别 二叉查找树 平衡二叉树 红黑二叉树

  • 认识二叉堆

    什么是二叉堆? 二叉堆本质上是一种完全二叉树( 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引...

网友评论

    本文标题:数据结构之完全二叉树&二叉平衡树

    本文链接:https://www.haomeiwen.com/subject/kdqzrftx.html