动态查找表 ■平衡二叉树的算法 (参见:P236、P237)
动态查找表 ◼ 平衡二叉树的算法 (参见：P236、P237)
动态查找表(练习题) 设关键字集合为:{10,20,30,50,40},依次输入 各结点,请画出平衡二叉树的构造过程
动态查找表（练习题） ◼ 设关键字集合为：{10，20，30，50，40}，依次输入 各结点，请画出平衡二叉树的构造过程
动态查找表(练习题参考答案) 0 -2 200 20-1 200 20-1 0300 00③0 00 0 (RR型) 0)0(400 300 400(LR型)
动态查找表（练习题参考答案） 10 0 10 -1 10 -2 20 0 20 -1 20 0 20 -1 10 0 30 0 10 0 30 -1 30 0 50 0 20 –2 （RR型） 20 -1 10 0 30 –2 10 0 40 0 50 1 30 0 50 0 40 0 （LR型）
散列表 散列( Hashing):是一种重要的存储方法,也是一 种 常见的査找方法。(关键字地址转换法) 基本思想:以结点的关键字k为自变量,通过一个确定 的函数关系f,计算出对应的函数值f(k),把这个值解 释为结点的存储地址,将结点存入所指的存储位置上。 查找时,再根据要查找的关键字用同样的函数计算地 址,然后到相应的地址单元里取要找的结点。 散列表:用散列法存储的线性表。 散列函数:上述的函数f。 散列地址:函数值f(k)
散列表 ◼ 散列（Hashing）：是一种重要的存储方法，也是一 种 常见的查找方法。（关键字—地址转换法） ◼ 基本思想：以结点的关键字k为自变量，通过一个确定 的函数关系f，计算出对应的函数值f(k)，把这个值解 释为结点的存储地址，将结点存入所指的存储位置上。 查找时，再根据要查找的关键字用同样的函数计算地 址，然后到相应的地址单元里取要找的结点。 ◼ 散列表：用散列法存储的线性表。 ◼ 散列函数：上述的函数f。 ◼ 散列地址：函数值f(k)
散列表 散列函数的构造方法 直接定址法 数字选择法 平方取中法 折叠法 除留余数法 基数转换法 随机数法
散列表 ◼ 散列函数的构造方法 直接定址法 数字选择法 平方取中法 折叠法 除留余数法 基数转换法 随机数法