6-3树表的查找技术

6-3树表的查找技术v第六章查找技术树表的提出如何在一个大型的数据集合上进行动态查找？顺序查找：不要求元素的有序性，插入、删除的性能是O(1)

查找性能是O(n)折半查找：查找性能是O(log2n)

为保证元素的有序性，插入、删除要移动元素，性能是O(n)有没有一种查找结构，使得插入、删除、查找均具有较好效率？树表：将查找集合组织成树的结构二叉搜索树二叉搜索树学什么？平衡二叉树B树6-3-1二叉搜索树v第六章查找技术二叉搜索树的定义二叉搜索树（二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值（3）它的左右子树也都是二叉搜索树6360554258254565857063905542582545658570二叉搜索树是记录之间满足某种大小关系的二叉树写出二叉搜索树的中序遍历序列？中序遍历序列：25424555586365708590升序序列二叉排序树63905542582545658570二叉搜索树的定义二叉搜索树的存储如何存储二叉搜索树？二叉链表45635590425870256585∧∧∧∧∧∧∧∧∧∧∧63905542582545658570二叉搜索树的类定义classBiSortTree

{public:BiSortTree(inta[],intn);~BiSortTree(){Release(root);}BiNode<int>*InsertBST(intx){returnInsertBST(root,x);}voidDeleteBST(BiNode<int>*p,BiNode<int>*f);BiNode<int>*SearchBST(intk){returnSearchBST(root,k);}private:

BiNode<int>*InsertBST(BiNode<int>*bt,intx);

BiNode<int>*SearchBST(BiNode<int>*bt,intk);

voidRelease(BiNode<DataType>*bt);

BiNode<int>*root;};不失一般性，假定待查找集合的记录为int型二叉搜索树的查找在二叉搜索树中查找给定值k

的过程是（1）若bt是空树，则查找失败；（2）若k＝bt->data，则查找成功；（3）若k＜bt->data，则在bt的左子树上查找；（4）若k>

bt->data，在bt的右子树上查找。二叉搜索树的查找效率在于只需查找二个子树之一63554265854525907058554245BiNode<int>*BiSortTree::SearchBST(BiNode<int>*bt,intk){if(bt==nullptr)returnnullptr;if(bt->data==k)returnbt;elseif(bt->data>k)returnSearchBST(bt->lchild,k);elsereturnSearchBST(bt->rchild,k);}如何在二叉搜索树中插入一个元素？例如，插入986355905870∧∧∧6390557058∧∧∧9898∧∧若二叉搜索树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。二叉搜索树的插入BiNode<int>*BiSortTree::InsertBST(BiNode<int>*bt,intx){if(bt==nullptr){BiNode<int>*s=newBiNode<int>;s->data=x;s->lchild=s->rchild=nullptr;bt=s;returnbt;}elseif(bt->data>x)bt->lchild=InsertBST(bt->lchild,x);elsebt->rchild=InsertBST(bt->rchild,x);}63root∧∧55∧∧90∧∧二叉搜索树的插入插入元素63插入元素90插入元素55BiSortTree::BiSortTree(inta[],intn){root=nullptr;for(inti=0;i<n;i++)root=InsertBST(root,a[i]);}63554265854525907058例1给定查找集合{63,55,42,45,58,90,70,25,85,65}，构造二叉搜索树（1）每次插入的新结点都是二叉搜索树上新的叶子结点;（2）找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；（3）在左子树/右子树的查找过程与在整棵树上查找过程相同；（4）新插入的结点没有破坏原有结点之间的关系。二叉搜索树的构造如何在二叉搜索树中删除一个元素？（1）从二叉搜索树中删除一个结点之后，要仍然保持二叉搜索树的特性；63554265854525907058（2）当删除分支结点时破坏了二叉搜索树中原有结点之间的链接关系，需要重新修改指针，使得删除结点后仍为一棵二叉搜索树。二叉搜索树的删除63554265854525907058情况1——被删除的结点是叶子结点不失一般性，设待删除结点为p，其双亲结点为f，且p是f的左孩子pf操作：将双亲结点中相应指针域的值改为空。f->lchild=nullptr;6355428545259070f58二叉搜索树的删除635542854525907058情况2——被删除的结点只有左子树或者只有右子树pf操作：将双亲结点中相应指针域指向被删除结点的左子树（或右子树）f->lchild=p->rchild;63554245259085pf二叉搜索树的删除不失一般性，设待删除结点为p，其双亲结点为f，且p是f的左孩子635542854525907058情况3——被删除的结点既有左子树也有右子树p操作：以其左子树中的最大值结点替换之，然后再删除该结点sparBiNode*par=p,*s=p->lchild;while(s->rchild!=nullptr){par=s;s=s->rchild;}585542854525907056ppar56p->data=s->data;par->rchild=s->lchild;二叉搜索树的删除不失一般性，设待删除结点为p，其双亲结点为f，且p是f的左孩子6355428545259070pspar特殊情况：左子树中的最大值结点是被删结点的孩子55428545259070psif(p==par)par->lchild=s->lchild;情况3——被删除的结点既有左子树也有右子树二叉搜索树的删除操作：以其左子树中的最大值结点替换之，然后再删除该结点不失一般性，设待删除结点为p，其双亲结点为f，且p是f的左孩子二叉搜索树的性能分析在二叉搜索树中执行插入和删除操作查找插入和删除的位置修改相应指针插入、删除、查找的时间复杂度相同二叉搜索树的查找性能取决于什么？63554265854525907058554245比较次数不超过树的深度二叉搜索树的深度是多少？取决于什么？对于查找集合{40,35,30,25,20,15}，构造的二叉搜索树深度为n403530152520平均比较次数=(1+2+3+4+5+6)/6=21/6对于查找集合{15,20,25,30,35,40}，构造的二叉搜索树深度为403530152520平均比较次数=(1×1+2×2+3×3)/6=14/6最坏情况：退化为线性查找最好情况：相当于折半查找平均情况：O(n)~O(log2n)查找集合的初始排列二叉搜索树的性能分析6-3-2平衡二叉树v第六章查找技术平衡二叉树的提出完全二叉树的深度：1234568910712345689107左右子树的深度相同二叉搜索树的深度取决于给定查找集合的排列，即结点的插入顺序具有n

个结点的二叉搜索树，最小深度是多少？有什么特征？对于查找集合的任意排列，如何得到一棵深度尽可能小的二叉搜索树？二叉搜索树的深度取决于给定查找集合的排列，即结点的插入顺序具有n

个结点的二叉搜索树，最小深度是多少？有什么特征？左右子树的深度相同维护最小深度的二叉搜索树的代价太大左右子树的深度相差1完全二叉树的深度：平衡二叉树的深度：平衡二叉树的提出平衡因子：该结点的左子树的深度减去右子树的深度5482548210110-12200平衡二叉树：是一棵空的二叉搜索树，或者具有下列性质的二叉搜索树：（1）根结点的左子树和右子树的深度最多相差1;（2）根结点的左子树和右子树也都是平衡二叉树在平衡二叉树中，结点的平衡因子是1、0或-1平衡二叉树非平衡二叉树平衡二叉树的定义最小不平衡子树最小不平衡子树：以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树3-1210如何调整最小不平衡子树呢？插入一个结点会影响哪些结点的平衡因子？548269010000且入且判断，一旦失衡立即调整只调整最小不平衡子树，并且不影响其他结点4平衡调整算法算法：平衡调整输入：平衡二叉树，新插入结点A输出：新的平衡二叉树1.找到最小不平衡子树的根结点D2.根据结点A和结点D之间的关系，判断调整类型3.根据类型、遵循扁担原理和旋转优先原则进行相应调整

（1）LL型、RR型：调整一次

（2）LR型、RL型：调整两次LL型的平衡调整403520012例1设序列{40,35,20}，构造平衡二叉树40352040新插入结点20和最小不平衡子树根结点40之间的关系——LL型扁担原理：将根结点看成是扁担中肩膀的位置hBLhBRhARABX插入结点X失去平衡调整后重新平衡h+1BLhARBRhBAX例2设序列{40,35,20,15,25,10}，构造平衡二叉树40352001240352040新插入结点10和最小不平衡子树根结点35之间的关系——LL型扁担原理：将根结点看成是扁担中肩膀的位置152510101235旋转优先：旋转下来的结点作为新根结点的孩子402015103525LL型的平衡调整2035400-1-2例3设序列{20,35,40}，构造平衡二叉树20203540新插入结点40和最小不平衡子树根结点20之间的关系——RR型扁担原理：将根结点看成是扁担中肩膀的位置RR型的平衡调整例4设序列{20,35,40,38,45,50}，构造平衡二叉树2035400-1-220352040新插入结点50和最小不平衡子树根结点35之间的关系——RR型扁担原理：将根结点看成是扁担中肩膀的位置38455035旋转优先：旋转下来的结点作为新根结点的孩子204045503538RR型的平衡调整例5设序列{35,40,20,15,30,25}，构造平衡二叉树352040新插入结点25和最小不平衡子树根结点35之间的关系——LR型扁担原理：将根结点看成是扁担中肩膀的位置15302535旋转优先：旋转下来的结点作为新根结点的孩子20152530354035第1次调整LR型的平衡调整第2次调整252015304035例6设序列{35,20,30}，构造平衡二叉树3520新插入结点30和最小不平衡子树根结点35之间的关系——LR型扁担原理：将根结点看成是扁担中肩膀的位置3035203035第1次调整第2次调整203035LR型的平衡调整例7设序列{35,45,20,50,40,38}，构造平衡二叉树352045新插入结点38和最小不平衡子树根结点35之间的关系——RL型扁担原理：将根结点看成是扁担中肩膀的位置4050383538402035第1次调整4550RL型的平衡调整第2次调整404550203538旋转优先：旋转下来的结点作为新根结点的孩子6-3-3B树v第六章查找技术B树的定义B树：一棵m阶的B树或者为空树，或者为满足下列特性的m叉树：（1）每个结点至多有

m棵子树；（2）根结点至少有两棵子树；（3）除根结点和叶子结点外，所有结点至少有

m/2

棵子树；1181112

213013924753199342

58701351654阶B树子树个数2~4（4）所有结点都包含以下数据：

（n，A0，K1，A1，K2，…，Kn，An）其中，n（

m/2

1≤n≤m

1）为关键码的个数，Ki（1≤i≤n）为关键码，且Ki＜Ki+1（1≤i≤n-1），Ai（0≤i≤n）为指向子树根结点的指针，且指针Ai所指子树中所有结点的关键码均小于Ki+1大于Ki。1181112

21301392

4753199342

58

701351654阶B树关键码个数1~3B树：一棵m阶的B树或者为空树，或者为满足下列特性的m叉树：B树的定义（5）叶子结点都在同一层；叶子结点都在同一层树高平衡具有较高的查找效率失败结点叶子结点1181112

213013924753199342

5870135165FFFFFFFFFFFFFFB树的定义B树：一棵m阶的B树或者为空树，或者为满足下列特性的m叉树：假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：（1）定位：确定关键码key应该插入哪个叶子结点并返回该结点的指针p。

若

p中的关键码个数小于n，则直接插入关键码key；

否则，结点

p的关键码个数溢出，执行“分裂——提升”过程。B树是多少阶？m=3,

n=2656020408010222850759096新关键码插入到相应的叶子结点B树的插入（1）定位：确定关键码key应该插入哪个终端结点并返回该结点的指针p。

若

p中的关键码个数小于n，则直接插入关键码key；

否则，结点

p的关键码个数溢出，执行“分裂——提升”过程。60204080102228509096657570发生溢出假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入B树是多少阶？m=3,n=26020401022285090966575分裂—提升（2）分裂——提升：将结点

p“分裂”成两个结点，分别是p1和p2，把中间的关键码k“提升”到父结点，并且k的左指针指向p1，右指针指向p2。7080B树是多少阶？m=3,n=2假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入60204010222850909665757080（2）分裂——提升：如果父结点的关键码个数也溢出，则继续执行“分裂——提升”过程。显然，这种分裂可能一直上传，如果根结点也分裂了，则树的高度增加了一层。30B树是多少阶？m=3,n=2发生溢出假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入602028401050909665757080（2）分裂——提升：如果父结点的关键码个数也溢出，则继续执行“分裂——提升”过程。显然，这种分裂可能一直上传，如果根结点也分裂了，则树的高度增加了一层。分裂——提升，再次溢出2230假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入B树是多少阶？m=3,n=21050909665757080（2）分裂——提升：如果父结点的关键码个数也溢出，则继续执行“分裂——提升”过程。显然，这种分裂可能一直上传，如果根结点也分裂了，则树的高度增加了一层。再次分裂——提升22302040假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入B树是多少阶？m=3,n=22860如果在B树中插入一个元素时导致根结点发生溢出，则B树产生一个新的根结点并且树高增加了一层，此时，新根只有一个关键码和两棵子树。为什么B树的根结点最少有两棵子树？105090966575708022302860204095105065752230204090967095288060B树的插入如何删除二叉搜索中的一个结点？情况1——被删除的结点是叶子结点65635542854525907058情况3——被删除的结点既有左子树也有右子树585542854525907055428545259070586363B树的删除假定在

m阶B树中删除关键码key，删除过程如下：（1）定位：确定关键码key在哪个结点并返回该结点的指针q。

假定key是结点

q中的第

i个关键码Ki，有以下两种情况：1.1若结点

q

是叶子结点，则删除key；

1.2若结点

q

不是叶子结点，则用

Ai所指子树中的最小值

x

替换Ki；删除x；

602040801022285090966575删除操作归结为在叶子结点中删除关键码B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；602040801022285090966575关键码个数是多少？

-1=1假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；60204080105090962.2否则，删除操作涉及到兄弟结点2.2.1兄弟结点的关键码个数大于，则向兄弟结点借一个关键码；222875假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；2.2否则，删除操作涉及到兄弟结点2.2.1兄弟结点的关键码个数大于，则向兄弟结点借一个关键码，并且借来的关键码“上移”到双亲结点，双亲结点相应关键码“下移”；6020

2880104090967522假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；2.2否则，删除操作涉及到兄弟结点2.2.2兄弟结点的关键码个数不大于，则执行“合并”兄弟操作；6020

2880104090967522假定在

m阶B树中删除关键码key