《数据结构和算法》——平衡二叉树

luciferzf

平衡二叉树：对比于二叉排序树对于时间复杂度的不可控制，平衡二叉树有个更加稳定的时间复杂度。我们构建了一个左右子树平衡的二叉树，使每个节点的左、右二叉树的深度差值不超过1，便于遍历。
构建过程：在构建时，除了需要按照排序二叉树的构建原则，使节点的左子树的数据小于节点的数据，节点右子树的数据大于节点的数据。同时，在添加数据时，我们需要对二叉树每个节点进行一个判定，若出现一个节点的平衡因子<=-2，则将该部分进行一次左旋转，若平衡因子大于2，则进行一次右旋转。需要注意的是，若出现几个节点的平衡因子正负号不同，则需要对平衡因子正负不同的几个节点的子树进行旋转，而不能只对几个节点统一只做一次大的旋转。
代码实现：我们利用递归的办法，先根据二叉排序树的规则将新的数据插入二叉树，然后判断一次“长高”部分的节点的平衡因子是否失衡，若失衡我们则需要对失衡部分进行旋转。先对节点进行平衡因子的调整和判断，若节点的左（右）子树的平衡因子不为0，我们只需要做一次旋转即可，否则需要进行两次旋转

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

class Bitnode
{
public:
        int data;
        int bf=0;
        Bitnode *lchild = NULL, *rchild = NULL;
};

void L_rotate(Bitnode *&P)
{
        Bitnode *L=P->lchild;
        P->rchild = L->lchild;
        L->rchild = P;
}
void R_rotate(Bitnode *&P)
{
        Bitnode *L = P->rchild;
        P->lchild = L->rchild;
        L->lchild = P;
}

void LeftB(Bitnode *&T)
{
        Bitnode *L = T->lchild, *Lr = NULL;
        switch (L->bf)
        {
        case 1:
                T->bf = L->bf = 0;
                R_rotate(T);
                break;
        case -1:
                Lr = L->rchild;
                switch (Lr->bf)
                {
                case 1:
                        T->bf = -1;
                        L->bf = 0;
                        break;
                case 0:
                        T->bf = L->bf = 0;
                        break;
                case -1:
                        T->bf = 0;
                        L->bf = 1;
                        break;
                }
                Lr->bf = 0;
                L_rotate(T->lchild);
                R_rotate(T);

        }
}

void RightB(Bitnode *&T)
{
        Bitnode *R = T->rchild, *Rl = NULL;
        switch (R->bf)
        {
        case 1:
                T->bf = R->bf = 0;
                L_rotate(T);
                break;
        case -1:
                Rl = R->lchild;
                switch (Rl->bf)
                {
                case 1:
                        T->bf = -1;
                        R->bf = 0;
                        break;
                case 0:
                        T->bf = R->bf = 0;
                        break;
                case -1:
                        T->bf = 0;
                        R->bf = 1;
                        break;
                }
                Rl->bf = 0;
                R_rotate(T->lchild);
                L_rotate(T);

        }
}

int InsertAVL(Bitnode *&T,int e,int *is)
{
        if (T == NULL)
        {
                T = new Bitnode;
                T->data = e;
                *is = true;
                return true;
        }
        else
        {
                if (e == T->data)
                {
                        *is = false;
                        return false;
                }
                if (e < T->data)
                {
                        if (!InsertAVL(T->lchild, e, is))
                        {
                                return false;
                        }
                        else
                        {
                                if (*is)
                                {
                                        switch (T->bf)
                                        {
                                        case 1:
                                                LeftB(T);//左旋节点
                                                *is = false;
                                                break;
                                        case 0:
                                                T->bf = 1;
                                                *is = true;
                                                break;
                                        case -1:
                                                T->bf = 0;
                                                *is = false;
                                                break;
                                        }
                                }
                        }
                        
                }
                else
                {
                        if (!InsertAVL(T->rchild, e, is))
                        {
                                return false;
                        }
                        if (*is)
                        {
                                switch (T->bf)
                                {
                                case -1:
                                        RightB(T);
                                        *is = false;
                                        break;
                                case 0:
                                        T->bf = -1;
                                        *is = true;
                                        break;
                                case 1:
                                        T->bf = 0;
                                        *is = false;
                                        break;
                                }
                        }
                }
        }
}