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

完全二叉树

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

---

二叉平衡树( 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

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