二叉排序树与平衡二叉排序树

二叉排序树与平衡二叉排序树

  • 作者:Geticsen
  • 时间:2019-10-15
  • 70人已阅读
简介 二叉排序树

二叉排序树又称二叉查找树,它或是一棵空的二叉树,或是具有下列性质的二叉树:

  • 1.若它的左子树不空,则左子树上所有节点的值均小于根节点的值

  • 2.若它的右子树不空,则右子树上所有节点的值均大于根节点的值

  • 3.它的左右子树也都是二叉排序树

由上述定义可知,中虚遍历二叉排序树可以得到一个按关键码有序的序列。

给定值的比较次数等于给定值节点在二叉排序树中的层数。如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为Log2n+1,其查找效率为O(Log2n),近似于折半查找。如果二叉排序树完全不平衡,则其深度可达到n,查找效率为O(n),退化为顺序查找。一般的,二叉排序树的查找性能在O(Log2n)到O(n)之间。因此,为了获得较好的查找性能,就要构造一棵平衡的二叉排序树。

对于给定的数组,如果按照之前的方式进行排序的话,有的时候会得到如下的结果 

image.png

在其中查找数字 8 ,很幸运只需要两步比较就可以得到最后的结果。但是也有可能变为如下的这种情况 

image.png

如果这个时候我们是要查找 9 的话就需要一直找到最后,所以这种情况是不好的。为了避免这种效率极端低下的查找过程,可以使用平衡二叉树排序树这种数据结构


1. 相关定义

  平衡二叉排序树要求每个节点的左右子树有着相同高度,或者要求任何节点的左右节点的左右子树高度差不超过1。

  根据定义我们可以判断以下的几棵树是否属于平衡二叉排序树


image.png

上面这个满足定义的要求,是一棵平衡二叉排序树。 

image.png

这棵树看起来像是平衡二叉排序树,因为他的深度满足要求;但实际上它并不是,因为首先不是一棵二叉排序树。 

image.png

这个也不是平衡二叉排序树,因为它虽然满足了二叉排序树的要求,但是并没有达到平衡的要求。比如说结点 9 的左子树的深度要比右子树的深度大 2,这就超过 1 了。 

image.png

这是平衡二叉排序树。

2. 实现原理

  对于一个给定的数组 [3, 2, 1, 4, 5, 6, 7, 10, 9, 8],如果不适用平衡二叉排序树的生成方法,很有可能得到如下的结果 

image.png

这个结果明显是查找效率极低的,所以使用如下的平衡二叉排序树的方法。前三个数字组成的数组如下图所示 

image.png

明显这已经是一个不平衡的二叉排序树,我们可以看到左子树的深度减去右子树的深度都是大于零的,所以树向右旋转得到如下图所示的结果 

image.png

之后再加上 4 5 两个元素可以得到如下的图像 

image.png

我们可以看到这个二叉排序树中,对于 2 3 两个结点都是不平衡的,且两者的不平衡因子都是 2 ,在这里是 3 的不平衡导致了 2 不平衡,所以调整 3 4 5 这棵不平衡术就可以了,因为在这两个不平衡点中不平衡因子(BF)都是负数,所以应该将这棵最小不平衡树进行左旋转,如下图所示 

image.png

再向其中加入 6 这个结点,如下图所示 

image.png

在这棵树中可以看到只有根节点 2 是不平衡的,且 BF = -2 < 0,所以需要将根节点 2 向左旋转,得到如下的结果 


image.png

在这棵树中可以看到只有根节点 2 是不平衡的,且 BF = -2 < 0,所以需要将根节点 2 向左旋转,得到如下的结果 

image.png

这个时候可以看到树已经不是一个二叉树,所以需要对 3 进行处理,由于 3 小于 4 ,所以将 3 连接在 4 的左子树的最右端,得到如下图所示的结果 

image.png

然后向其中加入数据节点 7 ,得到如下的结果 

image.png

其中的 5 6 7 构成了最小不平衡树,将它进行左旋转,得到如下结果 

image.png

再向其中加入 10 9 两个点,可以发现对于4 6 7 三个结点,它们的 bf = 2 ,所以需要调整二叉排序树,如下图所示 

image.png

但是这个结点不可以像之前一样通过旋转 7 10 9 这棵子树,因为这个时候, 10 结点的 BF 符号与之前的符号均不相同,所以要首先将 9 10 旋转,之后再将不平衡子树进行旋转,如下图所示 

image.png

其中左侧是将 9 10 旋转之后得到的结果,而右侧是再经过一层旋转得到二叉平衡树。

  最后向树中添加结点 8,得到的结果如下图所示 

image.png

明显结点 4 的 BF 为正,结点 6 的 BF 为正,但是结点 9 的 BF 为负,这个时候应该先将 8 7 9 10 进行旋转,使得 BF 值相等,然后再调整二叉排序树,如下图所示

image.png

经过第一次旋转之后得到的结果如上图中左图所示,明显 4 6 结点不平衡,所以对 6 结点进行左旋转,得到上图中中间的图,这个时候的树不是二叉树,所以需要对 8 进行处理,因为 8 的值比对应的根节点 7 大,所以将它放在根节点 7 右子树的最左侧,得到上图中右图所示的情况,至此完成了平衡二叉树的生成。

实现代码如下:

#define LH 1
#define EH 0
#define RH -1

typedef struct BiTNode
{
    int data;
    int bf;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void R_Rotate(BiTree *p)
{
    BiTree L;
    L = (*p)->lchild;
    (*p)->lchild = L->rchild;
    L->rchild = (*p);
    *p = L;

}

void LeftBalance(BiTree *T)
{
    BiTree L, Lr;
    L = (*T)->lchild;

    switch(L->bf)
    {
        case LH:
            (*T)->bf = L->bf = EH;
            R_Rotate(T);
            break;
        case RH:
            Lr = L->rchild;
            switch(Lr->bf)
            {
                case LH:
                    (*T)->bf = RH;
                    L->bf = EH;
                    break
                case EH:
                    (*T)->bf = L->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    L->bf = LH;
                    break;
            }
            Lr->bf = EH;
            L_Rotate(&(*T)->lchild);
            R_Rotate(T);
    }
}

int InsertAVL(BiTree *T, int e, int *taller)
{
    if( !*T )
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = TRUE;
    }
    else
    {
        if(e == (*T)->data)
        {
            *taller = FALSE;
            return FALSE;
        }
        if(e < (*T)->data)
        {
            if(!InsertAVL(&(*T)->lchild, e, taller))
            {
                return FALSE;
            }
            if(*taller)
            {
                switch((*T)->bf)
                {
                    case LH:
                        LeftBalance(T);
                        *taller = FALSE;
                        break;
                    case EH:
                        (*T)->bf = LH;
                        *taller = TRUE;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        *taller = FALSE;
                        break;
                }
            }
        }
        else
        {
            if(!InsertAVL(&(*T)->rchild, e, taller))
            {
                return FALSE;
            }
            if(*taller)
            {
                switch((*T)->bf)
                {
                    case LH:
                        (*T)->bf = EH;
                        *taller = FALSE;
                        break;
                    case EH:
                        (*T)->bf = RH;
                        *taller = TRUE;
                        break;
                    case RH:
                        RightBalance(T);
                        *taller = FALSE;
                        break;
                }
            }
        }
    }
}


上一篇:集合类继承树

下一篇:精神贫瘠

文章评论

Top