主讲：计算机工程学院 李兰 邮箱：jsj2014cpp@163.com 答疑地点：主教学楼B区213 第9章 查 找 主讲：计算机工程学院 李兰 邮箱：jsj2014cpp@163.com 答疑地点：主教学楼B区213

9.2 动 态 查 找 树 表

学习目标： 主要内容 二叉排序树 平衡二叉树 重点 二叉排序树的定义、构造、插入、删除 平衡二叉树的定义、平衡旋转技术

9.2 树表的查找 静态查找表的缺点：当表的插入或删除操作频繁时,为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点（二分查找和分块查找只适用于静态查找表）。 以二叉树或树作为表的组织形式, 称为树表。

一、二叉排序树 （二叉查找树） 1．定义 2．查找算法 3．插入算法 4．删除算法 5．查找性能的分析

1 二叉排序树的定义 例如： 二叉排序树或者是一棵空树；或者 是具有如下特性的二叉树： （1）若它的左子树不空，则左子树上 1 二叉排序树的定义 122 250 300 110 200 99 105 230 216 二叉排序树或者是一棵空树；或者 是具有如下特性的二叉树： （1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值； （2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值； L N P E M C Y （3）它的左、右子树也都分别是二叉 排序树。 例如：

50 30 80 20 90 10 85 40 35 25 23 88 66 66 判定下面的是否二叉排序树 是二叉排序树 是二叉排序树 不是二叉排序树

结论：中序遍历二叉排序树得到一个关键字的递增有序序列 45 12 53 3 37 24 100 61 90 78 中序遍历二叉排序树后的结果有什么规律？ 3，12，24，37，45，53，61，78，90，100 递增 结论：中序遍历二叉排序树得到一个关键字的递增有序序列

2. 二叉排序树的查找过程 若二叉排序树为空，则查找不成功；否则， 1）若给定值等于根结点的关键字， 则查找成功 2. 二叉排序树的查找过程 若二叉排序树为空，则查找不成功；否则， 1）若给定值等于根结点的关键字， 则查找成功 2）若给定值小于根结点的关键字，则继续在 上进行查找 左子树 3）若给定值大于根结点的关键字，则继续在 上进行查找 右子树 查找关键字 == 50 , 35 , 90 , 50 95 , 50 50 50 50 50 30 80 30 80 查找失败 20 40 90 40 90 85 35 35 二叉排序树的查找举例 88 32

从上述查找过程可见， 在查找过程中，生成了一条查找路径： 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; ——查找成功 或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空为止。 ——查找不成功

typedef struct BiTNode { // 结点结构 TElemType data; 通常，取二叉链表作为二叉排序树的存储结构 typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;

二叉排序树算法 if (bt==NULL || bt->key==k) return bt; 指向二叉排序树根结点的指针 要查找的关键字 BSTNode * SearchBST(BiTree bt,KeyType k){ //递归终结条件 if (k<bt->key) //在左子树中递归查找 else //在右子树中递归查找 } if (bt==NULL || bt->key==k) return bt; return SearchBST(bt->lchild,k); return SearchBST(bt->rchild,k);

也可以采用如下非递归算法： BSTNode *SearchBST1(BSTNode *bt,KeyType k) { while (bt!=NULL) { if (k==bt->key) return bt; else if (k<bt->key) bt=bt->lchild; //在左子树中递归查找 else bt=bt->rchild; //在左子树中递归查找 } else //没有找到返回NULL return NULL;

例如，对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是 。 　　例如，对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是 。 　　A. 95,22,91,24,94,71 B. 92,20,91,34,88,35 　　C. 21,89,77,29,36,38 D. 12,25,71,68,33,34 说明：本题为2011年全国考研题。 　解：各选项对应的查找过程如下图所示，从中看到只有选项A对应的查找树不构成一棵二叉排序树，图中虚线圆框内部分表示违背二叉排序树的性质的子树。本题答案为A。

Status SearchBST(BiTree &T,KeyType key,BiTree f,BiTree &p) // 成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上 // 访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL if(!T) // 查找不成功 { p=f; return FALSE; } else if (key==T->data.key) // 查找成功 p=T; return TRUE; } else if (key<T->data.key) return SearchBST(T->lchild,key,T,p); // 在左子树中继续查找 else return SearchBST(T->rchild,key,T,p); // 在右子树中继续查找

3. 二叉排序树的插入过程 注意：新插入的结点总是叶子结点。 首先执行查找算法，找出被插结点的父亲结点。 3. 二叉排序树的插入过程 注意：新插入的结点总是叶子结点。 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 e.g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结点的关键字值，生成二叉排序树。 122 250 300 110 280 99 122 250 300 110 99 122 250 99 122 122 99 122 250 110 99 注意 输入顺序不同所建立的不同二叉排序树

Status InsertBST(BiTree &T, ElemType e) { // 当二叉排序树T中不存在关键字等于e.key的元素时，插入e并返回TRUE，否则返回FALSE。 BiTree p,s; if(!SearchBST(T,e.key,NULL,p)) // 查找不成功 { s=(BiTree)malloc(sizeof(BiTNode)); s->data=e; s->lchild=s->rchild=NULL; if(!p) T=s; // 被插结点*s为新的根结点 else if (e.key<p->data.key) p->lchild=s; // 被插结点*s为左孩子 else p->rchild=s; // 被插结点*s为右孩子 return TRUE; } return FALSE; // 树中已有关键字相同的结点，不再插入

4 二叉排序树的删除过程 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 可分三种情况讨论： （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。

（1）被删除的结点是叶子结点 例如: 被删关键字 = 20 88 50 30 80 20 40 90 35 85 32 88 结论： 20 40 90 35 85 直接删去该节点。 32 88 其双亲结点中相应指针域的值改为“空”

（2）被删除的结点只有左子树 或者只有右子树 被删关键字 = 40 80 50 30 80 20 40 90 35 85 32 88 结论： 30 80 20 40 90 用其左子树或者右子树代替它。 35 85 32 88 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。

（3）被删除的结点既有左子树，也有右子树 被删关键字 = 50 40 50 30 80 20 40 40 90 35 85 32 88 前驱结点 被删结点 以其前驱替代之，然后再删除该前驱结点。前驱是左子树中最大的节点。

（3）被删除的结点既有左子树，也有右子树 50 30 30 80 20 90 85 88 被删关键字 = 50 前驱结点 被删结点 以其前驱30替代之，然后再删除该前驱结点

Status DeleteBST(BiTree &T,KeyType key) 则删除该数据元素结点，并返回TRUE；否则返回FALSE。 if(!T) // 不存在关键字等于key的数据元素 return FALSE; else { if EQ(key,T->data.key) // 找到关键字等于key的数据元素 Delete(T); else if LT(key,T->data.key) DeleteBST(T->lchild,key); DeleteBST(T->rchild,key); return TRUE; }

void Delete(BiTree &p) BiTree q,s; if(!p->rchild) // p的右子树空则只需重接它的左子树 { q=p; p=p->lchild; free(q); } else if(!p->lchild) // p的左子树空，只需重接它的右子树 p=p->rchild;

else // p的左右子树均不空 { q=p; s=p->lchild; while(s->rchild) // 转左，然后向右到尽头(找待删结点的前驱) { q=s; s=s->rchild; } p->data=s->data; // s指向被删结点的＂前驱“ //(将被删结点前驱的值取代被删结点的值) if(q!=p) q->rchild=s->lchild; // 重接*q的右子树 else q->lchild=s->lchild; // 重接*q的左子树 free(s);

5. 二叉排序树的查找性能 å = C p 1 ASL 2 5 3 1 5 2 4 在等概率查找的情况下， n i 1 3 4 例如： 由关键字序列 1，2，3，4，5构造而得的二叉排序树， 3 ASL =（1+2+3+4+5）/ 5 = 3 1 5 由关键字序列 3，1，2，5，4构造而得的二叉排序树， 2 4 ASL =（1+2+3+2+3）/ 5 = 2.2

思考 平衡二叉树 通过上面的例子我们看到二叉排序树的不同形态平均查找长度也不同 问题：如何提高二叉排序树的查找效率？ 尽量让二叉树的形状均衡 我们后面讲解平衡二叉树

二、平衡二叉树 1.平衡二叉树的定义 2.平衡二叉树的特点 3.平衡旋转技术

1.平衡二叉树的定义 平衡因子： 结点的平衡因子是结点的左子树的高度减去右子树的高度。 平衡二叉树（AVL树 ） ： 每个结点的平衡因子都为 ＋1、－1、0 的二叉树或者说每个结点的左右子树的高度最多差一的二叉树。

判定下面的二叉树是否平衡二叉树 不是平衡二叉树 是平衡二叉树 14 12 5 3 9 28 63 53 60 50 17 18 7 30 不平衡的结点 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 -1 14 5 3 9 28 63 53 60 50 17 18 30 +1 +2 -1 不是平衡二叉树 是平衡二叉树

2. 平衡二叉树的特点 平衡二叉树是二叉排序树，左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均大于等于根结点的值。 平衡二叉树中所有结点的左子树和右子树高度最多相差1（平衡因子为0,1或-1） 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 -1

在左图所示的平衡树中插入数据域为 2 的结点。 插入之后仍应保持平衡二叉树的性质不变。 以插入为例： 在左图所示的平衡树中插入数据域为 2 的结点。 插入之后仍应保持平衡二叉树的性质不变。 危机结点 -1 14 -1 +1 -1 14 9 28 +2 +1 -1 9 28 +1 -1 5 12 18 50 原平衡度为 0 +1 +1 -1 5 12 18 50 30 60 3 7 17 +1 30 60 3 7 17 53 63 53 63 平衡树 2 如何用最简单、最有效的办法保持平衡二叉树的性质不变？

3 平衡二叉树的平衡旋转 平衡旋转 如果在一棵平衡二叉树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。 LL平衡旋转 RR平衡旋转 LR平衡旋转 RL平衡旋转 在平衡旋转过程中要 保证二叉排序树的性质不变

平衡旋转 1）LL型平衡旋转： 若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴） C B A C

平衡旋转 2）RR型平衡旋转： 若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴） C

平衡旋转 3）LR型平衡旋转： 若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。 C A B C A B C A B

4）RL型平衡旋转： 若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。 A C B A

练习：请将下面序列构成一棵平衡二叉排序树 （ 13，24，37，90，53） 练习：请将下面序列构成一棵平衡二叉排序树 （ 13，24，37，90，53） 需要RL平衡旋转(先顺后逆） -1 13 13 37 24 13 -2 13 -1 24 24 -1 24 37 90 53 -1 37 -2 37 90 37 需要RR平衡旋转 1 90 53 90 53 37

第9章 查找 第2讲 结束 习题册 9.2 作业：