数据结构与算法--平衡二叉树

Posted on Oct 31, 2019

数据结构与算法——平衡二叉树

1 引言

二叉树是数据结构中的重点与难点，也是应用较为广泛的一类数据结构。二叉树的基础知识在之前的数据结构与算法——二叉树基础中已经详细介绍。本篇文章将着重介绍两类二叉树，二叉搜索树和平衡二叉树。

2 二叉搜索树

2.1 定义

二叉搜索树又称二叉查找树，亦称为二叉排序树。设x为二叉查找树中的一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y] <= key[x]；如果y是x的右子树的一个节点，则key[y] >= key[x]。

2.2 性质

（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
（3）左、右子树也分别为二叉搜索树；

例如：图2.2.1所示的二叉树为一棵二叉搜索树。

图2.2.1

例如：图2.2.2所示不是一棵二叉搜索树，因为节点40的左孩子节点值为44，不满足二叉搜索树的定义。

图2.2.2

2.3 节点结构

二叉树的节点结构通常包含三部分，其中有：左孩子的指针，右孩子指针以及数据域。节点的图示如下：

代码定义：

/* 二叉树的二叉链表节点结构定义 */

/* 节点结构 */



struct BSTNode 

{

    int key;   //节点数据 

    struct BSTNode *lchild, *rchild;    /* 左右孩子指针 */

};

2.4 创建二叉搜索树

现有序列：A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。根据此序列构造二叉搜索树过程如下：

（1）i = 0，A[0] = 61，节点61作为根节点；
（2）i = 1，A[1] = 87，87 > 61，且节点61右孩子为空，故81为61节点的右孩子；
（3）i = 2，A[2] = 59，59 < 61，且节点61左孩子为空，故59为61节点的左孩子；
（4）i = 3，A[3] = 47，47 < 59，且节点59左孩子为空，故47为59节点的左孩子；
（5）i = 4，A[4] = 35，35 < 47，且节点47左孩子为空，故35为47节点的左孩子；
（6）i = 5，A[5] = 73，73 < 87，且节点87左孩子为空，故73为87节点的左孩子；
（7）i = 6，A[6] = 51，47 < 51，且节点47右孩子为空，故51为47节点的右孩子；
（8）i = 7，A[7] = 98，98 < 87，且节点87右孩子为空，故98为87节点的右孩子；
（9）i = 8，A[8] = 93，93 < 98，且节点98左孩子为空，故93为98节点的左孩子；创建完毕后如图2.4中的二叉搜索树：

图2.4

2.5 查找

查找流程：
（1）如果树是空的，则查找结束，无匹配。
（2）如果被查找的值和节点的值相等，查找成功。
（3）如果被查找的值小于节点的值，递归查找左子树，
（4）如果被查找的值大于节点的值，递归查找右子树，

查找代码：

/* 递归查找二叉排序树T中是否存在key, */

/* 指针f指向T的双亲，其初始调用值为NULL */

/* 若查找成功，则指针p指向该数据元素节点，并返回TRUE */

/* 否则指针p指向查找路径上访问的最后一个节点并返回FALSE */



bool searchBST(BSTNode* T, int key, BSTNode* f, BSTNode **p)

{  

    if (!T) /*  查找不成功 */

    { 

        *p = f;  

        return false; 

    }

    else if (key == T->key) /*  查找成功 */

    { 

        *p = T;  

        return true; 

    } 

    else if (key < T->key) 

        return searchBST(T->lchild, key, T, p);  /*  在左子树中继续查找 */

    else  

        return searchBST(T->rchild, key, T, p);  /*  在右子树中继续查找 */

}

使用二叉搜索树可以提高查找效率，其平均时间复杂度为O(log2n)。

2.6 插入

插入流程：
（1）先检测该元素是否在树中已经存在。如果已经存在，则不进行插入；
（2）若元素不存在，则进行查找过程，并将元素插入在查找结束的位置。

图解过程：

代码实现：

void insertBST(BSTNode **T,int key) //此处使用二重指针是因为要修改指针的指针

{

    BSTNode *s;

    if(*T==NULL) //到达查找结束位置，再次位置插入元素

    {

        s = (BSTNode*)malloc(sizeof(BSTNode));

        s->key = key;

        s->lchild = NULL;

        s->rchild = NULL;

        *T=s;

    }

    else if(key<(*T)->key)//要插入的值大于当前节点，往左子树搜

    {

        insertBST(&((*T)->lchild),key);

    }

    else if(key>(*T)->key)//大于当前节点，往右子树搜

    {

        insertBST(&((*T)->rchild),key);

    }

}

2.7 删除

（1）删除节点为叶子节点
删除叶子节点的方式最为简单，只需查找到该节点，直接删除即可。例如删除图2.4中的叶子节点37、节点51、节点60、节点73和节点93的方式是相同的。

（2）删除的节点只有左子树
删除的节点若只有左子树，将节点的左子树替代该节点位置。例如：删除图2.4中的98节点：

（3）删除的节点只有右子树
删除的节点若只有右子树，将节点的右子树替代该节点位置。这种情况与删除左子树处理方式类似，不再赘述。

（4）删除的节点既有左子树又有右子树。
若删除的节点既有左子树又有右子树，这种节点删除过程相对复杂。其流程如下：
（1）遍历待删除节点的左子树，找到其左子树中的最大节点，即删除节点的前驱节点；
（2）将最大节点代替被删除节点；
（3）删除左子树中的最大节点；
（4）左子树中待删除最大节点一定为叶子节点或者仅有左子树。按照之前情形删除即可。

注：同样可以使用删除节点的右子树中最小节点，即后继节点代替删除节点，此流程与使用前驱节点类似。

删除代码：

//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素节点

//并返回TRUE；否则返回FALSE。

bool deleteBST(BSTNode* T,int key)

{ 

    if(!*T) /* 不存在关键字等于key的数据元素 */ 

        return false;

    else

    {

        if (key == (*T)->key) /* 找到关键字等于key的数据元素 */ 

            return deleteBSTNode(T);

        else if (key<(*T)->key)

            return deleteBST(&(*T)->lchild,key);

        else

            return deleteBST(&(*T)->rchild,key);



    }

}

/* 从二叉排序树中删除节点p，并重接它的左或右子树。 */

bool deleteBSTNode(BSTNode* p)

{

    BSTNode* q,s;

    if((*p)->rchild==NULL) //右子树空则只需重接它的左子树（待删节点是叶子也走此分支) 

    {

        q=*p;

        *p=(*p)->lchild; 

        free(q);

    }

    else if((*p)->lchild==NULL) //左子树为空，只需重接它的右子树

    {

        q=*p; 

        *p=(*p)->rchild; 

        free(q);

    }

    else //左右子树均不空

    {

        q=*p; 

        s=(*p)->lchild;

        while(s->rchild) // 转到左子树，然后向右到尽头（找待删节点的前驱） */

        {

            q=s;

            s=s->rchild;

        }

        (*p)->key=s->key; //s指向被删节点的直接前驱（将被删节点前驱的值取代被删节点的值）

        if(q!=*p)

            q->rchild=s->lchild; //重接q的右子树

        else

            q->lchild=s->lchild; //重接q的左子树

        free(s);

    }

    return TRUE;

}

3 平衡二叉树

3.1 定义

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序，例如序列A = {1，2，3，4，5，6}，构造二叉搜索树如图3.1。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为O(n)。

图3.1

在此二叉搜索树中查找元素6需要查找6次。二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列A，改为图3.2方式存储，查找元素6时只需比较3次，查找效率提升一倍。

可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。

非平衡二叉树

平衡二叉树

3.2 平衡因子

定义：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于1的节点。在一棵平衡二叉树中，节点的平衡因子只能取-1、1或者0。

3.3 节点结构

定义平衡二叉树的节点结构：

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode

{

    int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡

    Tree parent; //该结点的父节点，方便操作

    ElementType val; //结点值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) //默认构造函数

    {

        parent=NULL;

        depth=0;

        lchild=rchild=NULL;

        this->val=val;

    }

};

对于给定结点数为n的AVL树，最大高度为O(log2n).

3.4 左旋与右旋

（1）左旋
如图3.4.1所示的平衡二叉树

如在此平衡二叉树插入节点62，树结构变为：

可以得出40节点的左子树高度为1，右子树高度为3，此时平衡因子为-2，树失去平衡。为保证树的平衡，此时需要对节点40做出旋转，因为右子树高度高于左子树，对节点进行左旋操作，流程如下：
（1）节点的右孩子替代此节点位置
（2）右孩子的左子树变为该节点的右子树
（3）节点本身变为右孩子的左子树

图解过程：

（2）右旋
右旋操作与左旋类似，操作流程为：
（1）节点的左孩子代表此节点
（2）节点的左孩子的右子树变为节点的左子树
（3）将此节点作为左孩子节点的右子树。

图解过程：

3.5 插入

假设一颗 AVL 树的某个节点为A，有四种操作会使 A 的左右子树高度差大于 1，从而破坏了原有 AVL 树的平衡性。平衡二叉树插入节点的情况分为以下四种：

（1） A的左孩子的左子树插入节点(LL)

例如：图3.5.1所示的平衡二叉树：

图3.5.1

节点A的左孩子为B，B的左子树为D，无论在节点D的左子树或者右子树中插入F均会导致节点A失衡。因此需要对节点A进行旋转操作。A的平衡因子为2，值为正，因此对A进行右旋操作。

图解过程：

代码实现：

//LL型调整函数

//返回:新父节点

Tree LL_rotate(Tree node)

{

    //node为离操作结点最近的失衡的结点

    Tree parent=NULL,son;

    //获取失衡结点的父节点

    parent=node->parent;

    //获取失衡结点的左孩子

    son=node->lchild;



    //设置son结点右孩子的父指针

    if (son->rchild!=NULL)

        son->rchild->parent=node;



    //失衡结点的左孩子变更为son的右孩子

    node->lchild=son->rchild;



    //更新失衡结点的高度信息

    update_depth(node);



    //失衡结点变成son的右孩子

    son->rchild=node;



    //设置son的父结点为原失衡结点的父结点

    son->parent=parent;





    //如果失衡结点不是根结点，则开始更新父节点

    if (parent!=NULL)

    {

        //如果父节点的左孩子是失衡结点，指向现在更新后的新孩子son

        if (parent->lchild==node)

            parent->lchild=son;

        else //父节点的右孩子是失衡结点

            parent->rchild=son;

    }

    //设置失衡结点的父亲

    node->parent=son;

    //更新son结点的高度信息

    update_depth(son);

    return son;

}



//更新当前深度

void update_depth(Tree node)

{

    if (node==NULL)

        return;

    else

    {

        int depth_Lchild=get_balance(node->lchild); //左孩子深度

        int depth_Rchild=get_balance(node->rchild); //右孩子深度

        node->depth=max(depth_Lchild,depth_Rchild)+1;

    }

}





//获取当前结点的深度

int get_balance(Tree node)

{

    if (node==NULL)

        return 0;

    return node->depth;

}



//返回当前平衡因子

int is_balance(Tree node)

{

    if (node==NULL)

        return 0;

    else

        return get_balance(node->lchild)-get_balance(node->rchild);

}

（2） A的右孩子的右子树插入节点(RR)

如图3.5.2所示：插入节点F后，节点A的平衡因子为-2，对节点A进行左旋操作。

图3.5.2

图解过程：

代码实现：

//RR型调整函数

//返回新父节点

Tree RR_rotate(Tree node)

{

    //node为离操作结点最近的失衡的结点



    Tree parent=NULL,son;

    //获取失衡结点的父节点

    parent=node->parent;

    //获取失衡结点的右孩子

    son=node->rchild;



    //设置son结点左孩子的父指针

    if (son->lchild!=NULL)

        son->lchild->parent=node;



    //失衡结点的右孩子变更为son的左孩子

    node->rchild=son->lchild;



    //更新失衡结点的高度信息

    update_depth(node);



    //失衡结点变成son的左孩子

    son->lchild=node;



    //设置son的父结点为原失衡结点的父结点

    son->parent=parent;





    //如果失衡结点不是根结点，则开始更新父节点

    if (parent!=NULL)

    {

        //如果父节点的左孩子是失衡结点，指向现在更新后的新孩子son

        if (parent->lchild==node)

            parent->lchild=son;

        else //父节点的右孩子是失衡结点

            parent->rchild=son;

    }

    //设置失衡结点的父亲

    node->parent=son;

    //更新son结点的高度信息

    update_depth(son);

    return son;

}

（3） A的左孩子的右子树插入节点(LR)
若A的左孩子节点B的右子树E插入节点F，导致节点A失衡。

A的平衡因子为2，若仍按照右旋调整，调整过程如下：

经过右旋调整发现，调整后树仍然失衡，说明这种情况单纯的进行右旋操作不能使树重新平衡。那么这种插入方式需要执行两步操作：
（1）对失衡节点A的左孩子B进行左旋操作，即RR情形操作。
（2）对失衡节点A做右旋操作，即LL情形操作。

图解过程：

代码实现：

//LR型，先左旋转，再右旋转

//返回：新父节点

Tree LR_rotate(Tree node)

{

    RR_rotate(node->lchild);

    return LL_rotate(node);

}

（4） A的右孩子的左子树插入节点(RL)
右孩子插入左节点的过程与左孩子插入右节点过程类似，只需对右孩子进行LL操作，然后在对节点进行RR操作。

图解过程：

代码实现：

//RL型，先右旋转，再左旋转

//返回:新父节点

Tree RL_rotate(Tree node)

{

    LL_rotate(node->rchild);

    return RR_rotate(node);

}

3.6 删除

平衡二叉树的删除情况与二叉搜索树删除情况相同，同样分为以下四种情况：
（1）删除叶子节点
（2）删除节点只有左子树
（3）删除节点只有右子树
（4）删除节点既有左子树又有右子树
平衡二叉树的节点删除与二叉搜索树删除方法一致，但是需要在节点删除后判断树是否仍然保持平衡，若出现失衡情况，需要进行调整。

代码实现：

//删除操作

//参数：根，需要删除的结点

//返回值: 返回删除结点的父节点

Tree remove_val(Tree &root,Tree &node)

{

    Tree parent=node->parent;

    Tree temp=NULL;

    //只有左孩子

    if (node->rchild==NULL && node->lchild!=NULL)

    {

        temp=node;

        node=node->lchild; //指向左孩子

        node->parent=temp->parent;

        delete temp;       //释放结点

        update_depth(node); //更新当前结点信息

    }

    else if(node->lchild==NULL && node->rchild!=NULL) //只有右孩子

    {

        temp=node;

        node=node->rchild; //指向右结点

        node->parent=temp->parent;

        delete temp;       //释放结点

        update_depth(node); //更新当前结点信息

    }

    else if(node->rchild==NULL && node->lchild==NULL) //叶子结点

    {

        parent=node->parent; //找到其父节点

        if (parent) //如果父节点存在

        {

            /*

            if (parent->lchild==node)//当前结点是父节点的左孩子

            {

                parent->lchild=0;    //删掉左孩子

                delete node;         //释放空间

            }

            else    //当前结点是父节点的右孩子

            {

                parent->rchild=0;

                delete node;

            }

             */

            delete node;

            node=NULL;

            update_depth(parent); //更新父节点高度信息

        }

        else //删除的是根

        {

            delete root;

            root=NULL;

        }

    }

    else //既有左孩子也有右孩子，化繁为简

    {

        Tree *tmp=Find_Min(node->rchild); //找到替代元素，temp为叶子结点

        node->val=(*tmp)->val;         //更新值

        //判断当前叶子结点是左孩子还是右孩子。

        parent=(*tmp)->parent;

        /*

        if (parent->lchild==temp)

        {

            parent->lchild=0;

            delete temp;

        }

        else

        {

            parent->rchild=0;

            delete temp;

        }

         */

        delete *tmp;

        *tmp=NULL;

        update_depth(parent);

    }

    return parent;

}



//AVL树调整函数

//参数：根结点，插入结点

//返回：调整后的根结点

Tree AVLTree(Tree &root,Tree node)

{

    int balance=0; //平衡因子

    while (node!=NULL) //检查其祖先是否需要调整，更新

    {

        update_depth(node); //更新当前结点的高度信息

        balance=is_balance(node); //获取当前结点的平衡因子情况

        if (balance>1 || balance<-1) //平衡因子超标

        {

            if (balance>1) //左子树高

            {

                if (is_balance(node->lchild)>0) //LL型

                    node=LL_rotate(node);

                else  //LR型

                    node=LR_rotate(node);

            }

            else //右子树高

            {

                if (is_balance(node->rchild)<0) //RR型

                    node=RR_rotate(node);

                else //RL型

                    node=RL_rotate(node);

            }

            if (node->parent==NULL) //到达根结点

            {

                root=node; //设置新的根结点

                break; //退出

            }

        }

        node=node->parent; //依次找到其父节点



    }

    return root; //返回新根

}





//查找最小结点

Tree *Find_Min(Tree &root)

{

    if (root->lchild)

    {

       return Find_Min(root->lchild);

    }

    return &root;

}

数论和图论