动态查找表(练习题) ■设关键字集合为:{22,12,30,38,25,28}和{38, 30,28,25,22,12},请画出它们的二叉排序树, 成功查找的平均查找长度ASL?结论?
动态查找表（练习题） ◼ 设关键字集合为：{22，12，30，38，25，28}和{38， 30，28，25，22，12} ，请画出它们的二叉排序树， 成功查找的平均查找长度ASL？结论？
动态查找表(练习题参考答案)
动态查找表（练习题参考答案） 22 38 12 30 30 25 38 28 28 … 12
动态查找表 平衡二又树(AⅥL树) 它或者是一棵空树,或者是具有下列性质的二叉 树 它的左子树和右子树都是平衡二叉树,并且左子 树和右子树的深度之差的绝对值不超过1。 平衡因子:定义为该左子树的深度减去它的右子树的 深度。 (参见:P233图91.1:平衡二叉树于不平衡二叉树
动态查找表 ◼ 平衡二叉树（AVL树） 它或者是一棵空树，或者是具有下列性质的二叉 树： 它的左子树和右子树都是平衡二叉树，并且左子 树和右子树的深度之差的绝对值不超过1。 ◼ 平衡因子：定义为该左子树的深度减去它的右子树的 深度。 （参见：P233-图91.1：平衡二叉树于不平衡二叉树）
动态查找表 平衡二叉树的构造? Adelson、 Jelskii和 Landis提出了一个动态地保持 二叉排序树平衡的方法:在构造二叉排序树的过程中 每当插入一个结点时,首先检查是否因插入而破坏了 树的平衡性,若是,则找出其中最小不平衡子树,在 保持排序树特性的前提下,调整最小不平衡子树中各 结点之间的连接关系,以达到新的平衡 (通常将这样得到的平衡的二叉排序树简称为AⅥL树) (参见:P234图912:平衡二叉树的生成过程)
动态查找表 ◼ 平衡二叉树的构造？ Adelson、Velskii和Landis提出了一个动态地保持 二叉排序树平衡的方法：在构造二叉排序树的过程中， 每当插入一个结点时，首先检查是否因插入而破坏了 树的平衡性，若是，则找出其中最小不平衡子树，在 保持排序树特性的前提下，调整最小不平衡子树中各 结点之间的连接关系，以达到新的平衡。 （通常将这样得到的平衡的二叉排序树简称为AVL树） （参见：P234-图9.12：平衡二叉树的生成过程）
动态查找表 不平衡的四种情况 L型:在A的左孩子(L)的左子树(L)上插入结点,使A的平衡 因子由1变为2而失去平衡。(平衡处理:单向右旋) LR型:在A的左孩子(L)的右子树(R)上插入结点,使A的平衡 因子由1变为2而失去平衡。 (平衡处理:双向旋转(先左后右)) RR型:在A的右孩子(R)的右子树(R)上插入结点,使A的平 衡因子由-1变为-2而失去平衡。(平衡处理:单向左旋) RL型:在A的右孩子(R)的左子树(L)上插入结点,使A的平衡 因子由-1变为-2而去平衡。 (平衡处理:双向旋转(先右后左)) (参见:P235-图913)
动态查找表 ◼ 不平衡的四种情况： LL型：在A的左孩子（L）的左子树（L）上插入结点，使A的平衡 因子由1变为2而失去平衡。（平衡处理：单向右旋） LR型：在A的左孩子（L）的右子树（R）上插入结点，使A的平衡 因子由1变为2而失去平衡。 （平衡处理：双向旋转（先左后右）） RR型：在A的右孩子（R）的右子树（R）上插入结点，使A的平 衡因子由-1变为-2而失去平衡。（平衡处理：单向左旋） RL型：在A的右孩子（R）的左子树（L）上插入结点，使A的平衡 因子由-1变为-2而去平衡。 （平衡处理：双向旋转（先右后左）） （参见：P235-图9.13）