第四节：二叉搜索树

4.1 二叉搜索树

二叉搜索树（BST），也称二叉排序树和二叉查找树。一棵这个树，可以为空。如果不为空，满足以下性质：

（1）非空左子树的所有键值小于其根结点的键值。

（2）非空右子树的所有键值大于其根结点的键值。

（3）左、右子树都是二叉搜索树。

1.二叉搜索树操作的函数：

Position Find(ElementType X, BinTree BST)：从二叉搜索树BST中查找元素X，并返回其结点地址；

Position FindMin(ElementType X, BinTree BST)：从二叉搜索树BST中查找最小元素X，并返回其结点地址；

Position FindMax(ElementType X, BinTree BST)：从二叉搜索树BST中查找最大元素X，并返回其结点地址；

BinTree Insert(ElementType X, BinTree BST)

BinTree Delete(ElementType X, BinTree BST)

2.二叉搜索树的查找操作：Find

查找从根结点开始，如果树为空，返回NULL。

若树非空，则根结点关键字与X进行比较，并进行以下处理：

（1）若X小于根结点键值，则在左子树中继续搜索；

（2）若X大于根节点键值，则在右子树中搜索；

（3）若两者相等，搜索完成，返回指向此结点的指针。

代码如下：

C++
1
2
3
4
5
6
7
8
9
10
11
Position Find(ElementType X, BinTree BST)
{
       if(!BST)
              return NULL;
       if(X>BST->Data)
              return Find(X,BST->Right);
       else if(X<BST->Data)
              return Find(X, Bst->Left);
       else
              return BST;
}

由于非递归函数的执行效率高，可将尾递归函数修改为迭代函数：

C++
1
2
3
4
5
6
7
8
9
10
11
12
Position Find(ElementType X, BinTree BST)
{
       while(BST){
              if(X>BST->Data)
                     BST= BST->Right;
              else if(X<BST->Data)
                     BST= BST->Left;
       else
              return BST;
       }
       return NULL;
}

3.查找最大和最小元素

最大元素一定在树的最右分支的端结点上；最小元素在最左分支的端结点上。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*查找最小元素的递归函数*/
Position FindMin(BinTree BST)
{
       if(!BST) return NULL;
       else if(!BST->Left)
              return BST;
       else
              return FindMin(BST->Left);
}
/*查找最大元素的迭代函数*/
Position FindMax(BinTree BST)
{
       if(BST)
              while(BST->Right)
                     BST = BST->Right;
       return BST;
}

4.二叉搜索树的插入

分析：关键是要找到元素应该插入的位置，可以采用与Find类型的方法。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
BinTree Insert(ElementType X, BinTree BST)
{
       if(!BST){
              BST = malloc(sizeof(struct TreeNode));
              BST->Data =X;
              BST->Left = BST->Right =NULL;
       }
       else if(X<BST->Data)
              BST->Left = Insert(X, BST->Left);
       else if(X>BST->Data)
              BST->Right = Inser(X,BST->Right);
       return BST;
}

4.二叉搜索树的删除

我们需要考虑三种情况：

（1）要删除的是叶结点：直接删除，并再修改其父结点指针为NULL。

（2）要删除的结点只有一个孩子结点：要将其父结点的指针指向要删除结点的孩子结点。

（3）要删除的结点有左、右两棵子树：用另一结点代替被删除的结点：右子树的最小元素或者左子树的最大元素。如图2所示。

 1524539102126072.jpg

图1

代码如下所示：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
BinTree Delete( ElementType X, BinTree BST )
{   Position Tmp;
    if( !BST ) printf("要删除的元素未找到");
    else if( X < BST->Data )
            BST->Left = Delete( X, BST->Left); /* 左子树递归删除 */
    else if( X > BST->Data )
            BST->Right = Delete( X, BST->Right); /* 右子树递归删除 */
    else /*找到要删除的结点 */
         if( BST->Left && BST->Right ) { /*被删除结点有左右两个子结点 */
             Tmp = FindMin( BST->Right );
                           /*在右子树中找最小的元素填充删除结点*/
             BST->Data = Tmp->Data;
             BST->Right = Delete( BST->Data, BST->Right);
                                    /*在删除结点的右子树中删除最小元素*/
         } else { /*被删除结点有一个或无子结点*/
             Tmp = BST;
             if( !BST->Left ) /* 有右孩子或无子结点*/
                  BST = BST->Right;
             else if( !BST->Right ) /*有左孩子或无子结点*/
                  BST = BST->Left;
             free( Tmp );
         }
    return BST;
}

4.2 平衡二叉树

1.平衡二叉树基本介绍

查找二叉搜索树（BST）的时间复杂度（最坏情况下）用查找过程中的比较次数来衡量，它取决于树的深度。

对于二叉树中任一结点T，其“平衡因子（Balance Factor，简称BF）”定义为BF(T)=hL-hR。（其中hL和hR分别为T的左、右子树的高度。）

“平衡二叉树（Balanced Binary Tree）”又称为“AVL树” 。 AVL树或者是一棵空树，或者是具有下列性质的非空二叉搜索树：任一结点左、右子树高度差的绝对值不超过1。”即|BF(T) |≤ 1。

平衡二叉树的高度能达到logn吗？

设nh高度为h的平衡二叉树的最少结点树。结点数最少时：

nh=n(h-1)+n(h-2)+1

具体见图2.

1524539126857172.jpg 

图2

1.平衡二叉树的调整

（1）右单旋

如图3所示，当只将Mar加上May的时候，其平衡因子为-1，但是当增加了一个Nov的时候，其平衡引子变成了-2，不符合平衡二叉树的要求，因此很显然我们会想到将其调整到图3右侧的结构，这样其三个结点的平衡因子都是0了。

1524539140516138.jpg 

图3

首个不平衡的“发现者”是Mar（未必是根结点），它是调整起点位置。而“麻烦结点”Nov 在发现者右子树的右边，因而叫RR插入，需要RR旋转（右单旋）；一般情况（设A是首个发现者）的调整方式如下:

 1524539153680093.jpg

图4

（2）左单旋

 1524539165635453.jpg

图5

（3）左-右双旋

 1524539179564828.jpg

图6

（4）右-左双旋

1524539192123126.jpg 

图7