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

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.1

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

图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.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

图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

图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;

top Created with Sketch.