数据结构课件：2-检索-动态树2012.ppt

1、1检索检索数据结构与算法2BSTBST3（1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值；二叉排序树 二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉 排序树。（2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值；4二叉排序树的查找算法1）若给定值）若给定值等于根结点的关键字，则根结点的关键字，则查找成功；2）若给定值）若给定值小于根结点的关键字，则根结点的关键字，则继续在左子树上进行查找；3）若给定值）若给定值大于根结点的关键字，则根结点的关键字，则继续在右子树上进行查找。否则，若二叉排序树为空为空，则查找不成功查找不成功；

2、550308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 ,6从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找路径查找路径： 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为止。 查找成功查找成功 查找不成功查找不成功7 根据动态查找表的定义根据动态查找表的定

3、义，“插入”操作在查找不成功时才进行；二叉排序树的插入算法 若二叉排序树为若二叉排序树为空树，则新插入的，则新插入的结点为结点为新的根结点；否则，新插入；否则，新插入的结点必为一个的结点必为一个新的叶子结点，其，其插入位置由由查找过程得到查找过程得到。8 （1）被删除的结点）被删除的结点是叶子是叶子； （2）被删除的结点）被删除的结点只有左子树只有左子树或者或者只有只有右子树右子树； （3）被删除的结点）被删除的结点既有左子树，也有右既有左子树，也有右子树子树。二叉排序树的删除算法可分三种情况讨论： 和插入相反，删除在查找成功查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍仍然保持

4、二叉排序树的特性然保持二叉排序树的特性。9（1）被删除的结点是叶子结点叶子结点其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”（2）被删除的结点只有左子树只有左子树或者只有右只有右子树子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。（3）被删除的结点既有左子树，也有右子树既有左子树，也有右子树以其前驱替代之，然后再删除该前驱结点以其前驱替代之，然后再删除该前驱结点10BST查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关

5、键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。11由关键字序列 3，1，2，5，4构造而得的二叉排序树，由关键字序列 1，2，3，4，5构造而得的二叉排序树，例如：例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.212 下面讨论平均情况下面讨论平均情况: 不失一般性，假设长度为 n 的序列中有 k 个关键字小于小于第一个关键字，则必有 n-k-1 个关键字大于大于第一个关键字,由它构造的二叉排序树：n-k-1k的平均查找长度是 n 和 k 的函数P(n, k) ( 0 k n-1 )。

6、13 假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度：10),(1)(nkknPnnPASLniiniiiCnCpknP111),(在等概率查找等概率查找的情况下，14RiLirootniiCCCnCnknP11),(1)1)1()(1()1)(11knPknkPkn)1()1()(11knPknkPkn15由此可类似于解差分方程，此递归方程有解：CnnnnPlog12)(10) 1() 1()(111)(nkknPknkPknnnP112)(21nkkPkn16AVLAVL17平衡二叉树（AVL） AVL树定义它或者是一棵空二叉树，或者是

7、具有下列特性的二叉树：它的左子树和右子树的深度之差的绝对值不大于1，且左、右子树也是平衡二叉树 结点的平衡因子二叉树中某一结点的左子树的深度与右子树的深度之差18例：例：ABDCFEG1+100011平衡二叉树ABDCFEG1+2+100221HI0不平衡的二叉树可以证明AVL树的深度和log n 同数量级平衡二叉树（AVL）19BST的平衡旋转图例ABARBRBLBAARBRBLABBRBLALBABRBLALABARCRBLCCLCBARCRBLACLABALCRBRCCLCABRCRALBCL20举例:构建AVL树 输入关键码序列（输入关键码序列（13，24，37，90，53）(a)13

8、0(b)1324-10(c)132437021(d)243713000(e)1(f)243713-2-2090530(g)2437135390539037(h)24130000-121举例:构建AVL树(续) 输入关键码序列（输入关键码序列（13，24，37，90，53，95）539037241300-1-1-29502437135390955390372413001-1-2700243713539070 输入关键码序列（输入关键码序列（13，24，37，90，53，70）22举例:构建AVL树(续) 输入关键码序列（输入关键码序列（13，24，37，90，53，40）53903724130-

9、101-240024401337539053903724130111-2300243013375390 输入关键码序列（输入关键码序列（13，24，37，90，53，30）23平衡树结构的方法 单旋转单旋转 额外的结点是额外的结点是S左子女的左子女左子女的左子女 额外的结点是额外的结点是S右子女的右子女右子女的右子女 双旋转双旋转 额外的结点是额外的结点是S左子女的右子女左子女的右子女 额外的结点是额外的结点是S右子女的左子女右子女的左子女 旋转操作的正确性容易由保持旋转操作的正确性容易由保持BST树的特性证明树的特性证明 在经过平衡处理后，新平衡树的深度与插入之前在经过平衡处理后，新平衡树的

10、深度与插入之前的子树相同。因此当的子树相同。因此当AVL树因插入结点而失去平树因插入结点而失去平衡时，仅需对最小不平衡子树进行平衡旋转处理衡时，仅需对最小不平衡子树进行平衡旋转处理即可即可24 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡 树的深度。平衡树的查找性能分析 问：含 n 个关键字的二叉平衡树可能达到的最大深度最大深度是多少？25 因此，在二叉平衡树二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字进行比较的关键字的个数和的个数和 log(n) 相当。 由此推得，深度为深度为 h 的二叉平衡树二叉平衡

11、树中所含结点的最小值含结点的最小值 Nh = h+2/5 - 1。 反之，含有含有 n 个结点的二叉平衡树能个结点的二叉平衡树能达到的最大深度达到的最大深度 hn = log ( 5 (n+1) - 2。 课堂练习课堂练习 已知已知8个元素个元素(34, 76, 45, 18, 26, 54, 92, 65), 按照按照依次插入结点的方法生依次插入结点的方法生成一棵成一棵AVLAVL树树. 请下课时，提交你的练习结果给我，谢谢。请下课时，提交你的练习结果给我，谢谢。 并请写好你的学号和姓名。并请写好你的学号和姓名。27三、三、 B - 树树1定义定义2查找过程查找过程3插入操作插入操作4删除操

12、作删除操作5查找性能的分析查找性能的分析281B-树的定义树的定义B-树是一种 平衡平衡 的 多路多路 查找查找 树： root 50 15 71 84 3 8 20 26 43 56 62 78 89 9629 在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字关键字 Ki（1 in） nm n 个指向记录的指针指向记录的指针 Di（1in） n+1 个指向子树的指针指向子树的指针 Ai（0in）多叉树的特性30 非叶结点中的非叶结点中的多个关键字均均自小至大有有序排列，即：序排列，即：K1 K2 Kn ； Ai-1 所指子树上所有关键字均所指子树上所有关键字均小于Ki ； Ai

13、所指子树上所有关键字均所指子树上所有关键字均大于Ki ；查找树的特性31平衡树的特性 树中所有叶子结点均不带信息，且在树树中所有叶子结点均不带信息，且在树中的同一层次上中的同一层次上； 根结点或为叶子结点，或至少含有两棵根结点或为叶子结点，或至少含有两棵子树子树； 其余所有非叶结点均至少含有其余所有非叶结点均至少含有 m/2 棵棵子子树，至多含有树，至多含有 m 棵子树；棵子树；32 从根结点出发，沿指针搜索结点搜索结点和在在结点内进行结点内进行顺序（或折半）查找查找 两个过程交叉进行。2.查找过程：查找过程： 若查找成功查找成功，则返回指向返回指向被查关键字所在结点的指针结点的指针和关键字在

14、结点中的位置关键字在结点中的位置；若查找不成功查找不成功，则返回插入位置返回插入位置。33在查找不成功之后，需进行插入。显然，关键字插入插入的位置位置必定在最下最下层的非叶结点层的非叶结点，有下列几种情况：3插入插入1）插入后，该结点的关键字个数nsymbol 其中: p 指向双链树中某个结点， 0 i K.num-1513. Trie树树 以多重链表作存储结构实现的键树结点结构结点结构:分支结点分支结点叶子结点叶子结点指向记录的指针0 1 2 3 4 5 24 25 26关键字关键字指向下层结点的指针每个域对应一个“字母”520 1(A) 3 4 5(E) 9(I) 268(H)4(D) 1

15、9(S) 22(V) 0 18(R) 7(G) 190 5(E)THADHAS HAVE HEHERHEREHIGHHIS叶子结点叶子结点分支结点分支结点指向记录指向记录的指针的指针53在在 Trie 树中查找记录的过程树中查找记录的过程:假设假设: T 为指向 Trie 树根结点的指针， K.ch0.K.num-1 为待查关键字(给定值)。则则查找过程中的基本操作为： 搜索和对应字母相应的指针搜索和对应字母相应的指针:若若 p 不空，且 p 所指为分支结点，则则 p = p-bh.Ptrord(K.Chi) ; ( 其中: 0 i K.num-1 )54要点回顾要点回顾 查找的方法取决于查找表的结构 熟练掌握二叉排序树二叉排序树的构造和查找方法。 理解B-树树、B+树和建树树和建树的特点以及它们的特点以及它们的建树和查找的过程。建树和查找的过程。55哈希查找 课后预习课后预习