T18-基于树的查找算法

基于树的查找算法第九章主讲：周翔二叉排序树（二叉查找树）二叉排序树（BinarySortTree）又称为二叉查找树、二叉搜索树，它或者是一棵空树，或者是具有下列性质的二叉树：（1）如果左子树不为空，则左子树上所有结点的值均小于它根结点的值；（2）如果右子树不为空，则右子树上所有结点的值均大于它根结点的值；（3）左、右子树也分别为二叉排序树；（4）树中没有值相同的结点；二叉排序树（二叉查找树）图例二叉排序树（二叉查找树）结构定义dataleftChildrightChild二叉排序树（二叉查找树）二叉排序树的插入二叉排序树的查找二叉排序树的删除二叉排序树（二叉查找树）二叉排序树的插入已知一关键字值为key的结点S：若二叉树是空树，则S成为二叉排序树的根；若二叉树非空，则将S.key与二叉排序树根结点的关键字进行比较：if(key的值等于根结点的值)，则停止插入；elseif(key的值小于根结点的值)，则将S插入左子树；elseif(key的值大于根结点的值)，则将S插入右子树。二叉排序树（二叉查找树）输入数据，反复执行二叉排序树的插入过程输入数据{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981二叉排序树（二叉查找树）新结点作为叶结点插入例如：插入新结点2835154550402510203028时间复杂度为：O(log2n)二叉排序树（二叉查找树）创建：创建过程实质上就是反复执行插入的过程输入数据{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981时间复杂度为：O(nlog2n)二叉排序树（二叉查找树）n个结点，按不同的输入顺序组成二叉排序树最短的二叉排序树高度是？最长的二叉排序树高度是？log2n(取下整数)＋1n二叉排序树（二叉查找树）二叉排序树的查找根据二叉排序树的特点首先将待查关键字key与根结点关键字t进行比较，如果：key=t：则返回根结点地址；key<t：则进一步查左子树；key>t：则进一步查右子树。二叉排序树（二叉查找树）351545504025102030搜索28搜索45搜索失败搜索成功图例二叉排序树（二叉查找树）二叉排序树的查找：平均查找长度（ASL）若查找成功，则是从根结点出发走了一条从根结点到待查结点的路径若查找不成功，则是从根结点出发走了一条从根到某个叶子结点的路径所以，二叉排序树的查找与折半查找过程类似，查找长度与树的高度有关！！！二叉排序树（二叉查找树）二叉排序树的查找：最坏情况：二叉排序树是把一个有序表的n个结点依次插入生成的，由此得到一棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，是二叉排序树（二叉查找树）二叉排序树的查找：最好情况：得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是二叉排序树（二叉查找树）与折半查找的比较区别：折半查找对应的判定树是惟一的，而二叉排序树却不是！！！折半查找采用顺序存储结构，作插入、删除时，需移动大量元素；而二叉排序树则不需要。二叉排序树（二叉查找树）二叉排序树的删除：从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且保证删除后所得的二叉树仍然满足二叉排序树的性质不变。二叉排序树（二叉查找树）二叉排序树的删除的算法思想：若删除结点不在二叉排序树中，则不做任何操作。否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子（右孩子的情况类似），分三种情况讨论：若p为叶结点若p只有左子树（或只有右子树）p既有左子树，又有右子树二叉排序树（二叉查找树）二叉排序树的删除的算法思想：若p为叶结点：则可直接删除537865091787pf5378651787二叉排序树（二叉查找树）二叉排序树的删除的算法思想：若p只有左子树（或只有右子树），可将p的左子树（或右子树）直接改为其双亲结点f的左子树只有左子树：只有右子树：537865091787pf5378650987二叉排序树（二叉查找树）二叉排序树的删除的算法思想：p既有左子树，又有右子树方法1：找到p结点在中序序列中的前驱结点s，将p的左子树改为f的左子树，将p的右子树改为s的右子树：二叉排序树（二叉查找树）二叉排序树的删除的算法思想：将p的左子树改为f的左子树将p的右子树改为s的右子树53786587sp173040091215055378650917873040121505二叉排序树（二叉查找树）二叉排序树的删除的算法思想：p既有左子树，又有右子树方法2：找到p结点在中序序列中的前驱结点s，用s的值替代p结点的值，将s删除，原s的左子树改为s的双亲结点q的右子树。537865091787304012150515sfq5378650917873040121505psfqp12二叉排序树（二叉查找树）二叉排序树（二叉查找树）总结：二叉排序树的查找与折半查找过程类似，查找长度与树的高度有关！！因此，控制二叉排序树的高度在比较低的状态，对查找比较有利！平衡二叉排序树（AV树）1989奥斯卡是最佳短片奖--《Balance》世界需要平衡，破坏平衡的一方，也许会一时很强势的称霸，最终的结局逃不过孤立和落空平衡二叉排序树（AV树）定义：平衡二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：左子树与右子树的深度之差的绝对值小于等于1；左子树和右子树也是平衡二叉排序树；平衡二叉排序树（AV树）性质：

1：含有n个结点的AV树的高度为O(log2n)；2：在含有n个结点的AV树中搜索一个元素需要为O(log2n)时间；3：将一个新元素插入一棵n个结点的AV树中，可得到一棵n+1个结点的AV树，且插入所需的时间为O(log2n)；4：从一棵n个结点的AVL树删除一个元素，可得到一棵n-1个结点的AV树，且删除所需的时间为O(log2n)；平衡二叉排序树（AV树）结点的平衡因子——BF定义：结点左子树深度与右子树深度之差。AV树任一结点平衡因子只能取-1,0,1如果一个结点的平衡因子的绝对值大于1，则这棵二叉排序树就失去了平衡，不再是AV树。平衡二叉排序树（AV树）写出以下二叉树各结点的平衡因子值：左子树的深度－右子树的深度是平衡二叉排序树0351545504025102030000-10001平衡二叉排序树（AV树）写出以下二叉树各结点的平衡因子值：不是平衡二叉搜索树010-10-2000351545504025102030282平衡二叉排序树（AV树）以插入为例：如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。平衡化旋转有两类：单旋转（LL旋转和RR旋转）双旋转（LR旋转和RL旋转）平衡二叉排序树（AV树）输入关键码序列为

{16,3,7,11,9,26,18,14,15}，插入和调整过程如下：平衡二叉排序树（AV树）160163100-12LR双旋731600001-1731116012右单旋0-1-1-2-2163737112691673161190037169000-111000平衡二叉排序树（AV树）1-2RL双旋011左单旋1816000732611900031609-171126-11837161426911118261673911平衡二叉排序树（AV树）LR双旋18730011116150-12614915318162071491126-1从空树开始的建平衡二叉排序树的过程B树B树是为磁盘或其他外存设备而设计的一种多叉平衡查找树，因此它也叫多路平衡查找树，在读取外存文件时许多数据库系统都使用B树或者B树的各种变形结构，如B+树，B*树。B树一棵m阶的B树（注意m阶的树并不是简单的有m个叉树）或者是一棵空树，或者在定义中要满足以下要求：（1）树中每个结点最多有m棵子树（m>=2）；（2）根结点至少有两个子结点；（空树除外）（3）除根结点外，结点中关键字的个数取值范围为(m/2)-1到m-1；（m/2向上取整）；（4）所有叶子结点都在同一层；（5）除根结点和叶子结点外，如果结点有k-1个关键字，那么这个结点就有k个子结点，关键字按递增次序排列；B树18331248233010152021243145475051B树在B树中查找数据主要分为两步：（1）把根结点读出来，在根结点所包含的关键字k1、k2….kj中查找给定的关键字值（当结点包含的关键字值不多时，可用顺序查找；当结点包含的关键字数目较多时可用折半查找），找到则查找成功；（2）否则，确定要查找的关键字值的大小范围，根据指针指向的子结点，在子结点中继续查找。如果查找到叶子结点仍未找到，表示查找失败。B树在此B树中查找值31：1833124823301015202124314547505118<31<33查找18~33范围的子结点B树在此B树中查找值31：1833124823301015202124314547505118<31<33查找18~33范围的子结点在子结点中31>30，查找最右边的结点找到值31B树在B树中插入：在B树中插入元素时，首先要确定此元素在B树中是否存在，如果不存在则在合适位置插入，否则不能插入，因为B树中不允许有重复值。在插入时，如果要插入的结点空间足够，即结点中的关键字数量没有达到最大，则可顺利插入；B树在此B树中插入元素11：1833124823301015202124314547505111<1811<12且结点有足够空间11B树在此B树中插入元素11：1833111248233010152021243145475051B树在B树中插入：如果要插入的结点空间不足，则将结点进行“分裂”，将一半数量的关键字分裂到新的相邻右结点中，中间关键字则上移到父结点中（如果父结点空间也不足，需要继续“分裂”），同时若结点中关键字向右移动，相关的指针也需要向右移动。B树在此B树中插入元素54：1833111248233010152021243145475051B树在此B树中插入元素54：183311124851233010152021243145475054B+树和B*树B+树：B树的一种变形，一棵m阶的B+树与一棵m阶的B树的差异在于：（1）有k个子结点的B+树中含有