数据结构与算法(Python语言描述)课件DS_080_字典的树型实现

第八章字典的树型实现2016Fall《数据结构》二叉排序树平衡二叉排序树（AVL树）B-树主要内容（掌握概念即可！）**二叉排序树2020/3/29第七章图3中序遍历序列是有序序列！二叉排序树或者为空树，或者是满足下列性质的二叉树：若左子树不空，则左子树上的所有结点的值都小于根结点的值；若右子树不空，则右子树上的所有结点的值都大于根结点的值左右子树也分别为二叉排序树。二叉排序树的定义（递归）2020/3/29第七章图5vLR若根结点为空，则检索失败；否则关键码与根关键码比较：=：检索成功：转到左子树继续：转到右子树继续二叉排序树的检索2020/3/29第七章图6二叉排序树的插入——为叶子希望树形不要太“偏沉”，尽可能“平衡”，使得树的深度小，从而ASL小！case1：若要删除的结点是叶子，则直接删！二叉排序树的删除pffcase2：若要删除的结点只有一棵子树，则跨越删除！二叉排序树的删除pfLqfLqCase3：若删除的结点有两棵子树，则方法1：跨越删除后，右子树挂到最右下；问题：易导致树的深度变得很大！二叉排序树的删除Case3：若删除的结点有两棵子树，则方法2：利用左子树的最右下（最大）结点，充顶被删结点的位置！好处：树的深度不会增加！二叉排序树的删除插入、删除较为简单平均的检索效率高：O(logn)致命缺点：操作效率没有保证。由插入、删除操作的自然性和简单化处理，可能出现极度“偏沉”的树形。关于平衡二叉树2020/3/2913平衡二叉排序树2020/3/2914平衡二叉树、结点的平衡因子结点的平衡因子=左子树深度-右子树深度平衡二叉树：平衡因子只能是0，1，-1平衡二叉排序树既是平衡的、又是排序的二叉树！又称AVL树前苏联GeorgyAdelson-Velsky和EvgeniiLandis，1962可以证明：含n个结点的平衡二叉排序树的深度：h≤3/2log2(n+1)，即h=O(log2n)。平衡二叉排序树的插入直观：左边沉了，往右边转；右边沉了，往左边转！基本思想：将问题限制在局部进行处理！！！先找到离插入点最近的失衡结点，就地处理！这意味着局部之外的结点的平衡因子在插入的前后保持不变！LL：左边的左边沉，直接向右转LR：左边的右边沉，先向左转，让左边的左边沉，再向右转RR：右边的右边沉，直接向左转RL：右边的左边沉，先向右转，让左边的左边沉，再向左转“局部”平衡化旋转的四种情形注意：局部平衡化旋转之后，局部子树的深度与插入之前是相同的，这意味着“祖先”结点的平衡因子不会改变！注意：局部平衡化旋转之后，局部子树的深度与插入之前是相同的，这意味着“祖先”结点的平衡因子不会改变！基本思想与插入类似，先删除而后调整检索需要删除的结点把删除任意结点的问题变成删除某棵子树的最右结点实际删除结点（就是二叉排序树的删除）调整平衡复杂性也是O(logn)平衡二叉树的删除2020/3/2921插入、删除时在局部做平衡化处理！检索效率高：O(logn)缺点：实现比较复杂。关于平衡二叉排序树2020/3/2922B树2020/3/2923是一种平衡的多叉排序树！常被用于实现大型数据库的索引数据库记录存在一批外存区块里（外存区块较大）B树里记录的是关键码到数据记录存储位置的索引B树2020/3/2924467071527304953668111233841一棵m阶B树或为空树，或满足下列特性：分支结点至多m-1个排序存放的关键码~【每个结点至多m棵子树】根结点至少一个关键码~【根结点至少两棵子树】其他结点至少(m-1)/2个关键码~【其他结点至少┌m/2┐棵子树】叶结点位于同一层，表示检索失败若分支结点有j个关键码，它就包含j+1棵子树•结点信息为：(p0,k0,p1,k1,…,kj-1,pj)，–ki为关键码，pi为子结点引用（指针）•ki大于子树pi里的所有关键码，小于子树pi+1里的所有关键码~【多路排序】M阶的B树2020/3/29254阶B树示例例：3阶B树的插入插入30注：插入位置在最下层分支结点处！例：3阶B树的插入插入26后，结点关键码总数超限了结点分裂，中间的关键码顶到双亲上！例：3阶B树的插入插入85后，结点关键码总数超限了结点分裂，中间的关键码顶到双亲上，结果双亲关键码总数也超限了结点再分裂！例：3阶B树的插入插入7例：3阶B树的删除删50，结点关键码总数不够了若兄弟有的多，将双亲拉下来，兄弟顶上去一个思考：关键字的删除总可以转换成底层关键字的删除，为什么？？？例：3阶B树的删除删53，结点关键码总数不够了兄弟也没有多的，将双亲拉下来与兄弟合并删37，结点关键码总数不够了兄弟也没有多的，将双亲拉下来与兄弟合并，若双亲关键码总数也不够了，继续！