7.3.2 平衡二叉树

  • 平衡二叉树的定义

    • 又称AVL树
    • 一棵平衡二叉树或者是空树，或者是具有以下性质的二叉排序树：
      • 左子树与右子树的高度之差的绝对值小于等于1；
      • 左子树和右子树也是平衡二叉排序树。

  • 为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子

    • 根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1，0，或1

    • 对于一棵有n个结点的AVL树，其高度保持在$O(log_2n)$数量级，ASL也是保持在$O(log_2n)$量级

    • 当我们在一个平衡二叉树上插入结点时，可能导致失衡

      • 平衡调整的四种类型：

        LR型和RL型左右要看B和A哪个大

        • 调整原则：1. 降低高度 2. 保持二叉排序树性质

7.4 哈希表的查找

7.4.1 散列表的基本概念

  • 基本思想：记录的存储位置与关键字之间存在对应关系

​ 对应关系——hash函数（hash:散列）

​ Loc(i)=H(keyi)

  • 散列表的查找
    • 根据散列函数H(key)=k
      • 查找key=9，直接访问H(9)=9号地址，若内容为9则成功
        若查不到，则返回一个特殊值，如空指针或空记录。
    • 优点：查找效率高
      缺点：空间效率低
  • 散列函数和散列地址：在记录的存储位置p和其关键字key 之间建立一个确定的对应关系H, 使 p=H(key ), 称这个对应关系H为散列函数，p为散列地址。
  • 散列表：一个有线连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标
  • 冲突：不同的关键码映射到同一个散列地址
    • key1≠key2，但是H(key1)=H(key2)
    • 冲突是不可避免的，但可以减少
  • 同义词：具有相同函数值的多个关键字

7.4.2 散列函数的构造方法

  • 构造散列函数的考虑因素：

    • 散列表的长度
    • 关键字的长度
    • 关键字的分布情况
    • 计算散列函数所需的时间
    • 记录的查找频率

  • 构造号的散列函数要遵循以下两条原则

    • 函数计算要简单，每一个关键字只能有一个散列地址与之对应
    • 函数的值域需在表长的范围内， 计算出的散列地址的分布应均匀，尽可能减少冲突。

  • 根据数据元素的集合特性构造

    • 要求一: n个数据原仅占用n个地址虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小
    • 要求二:无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
7.4.2.1 直接定址法
  • Hash(key)=a.key+b
  • 优点：以关键码key的某个线性函数值为散列地址，不会产生冲突
    缺点：要占用连续的地址空间，空间效率低
7.4.2.2 除留余数法

  • Hash(key)=key mod p

    • 技巧：设：表长为m，取p<=m且为质数

      • 例：{15,23,27,38,53,61,70}

        散列函数：Hash(key)=key mod 7

        0 1 2 3 4 5 6
        70 15 23 38 53 61 27

7.4.3 处理冲突的方法

7.4.3.1 开放地址法（开地址法）

  • 基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入

    • 列入：除留余数法：$H_i=(Hash(key)+d)mod \ m$
    • 常用方法：
      • 线性探测法 $d_i为1,2,……，m-1线性序列$
      • 二次探测法 $d_i为1^2,-1^2,2^2,-2^2……，q^2二次序列$
      • 伪随机探测法 $d_i为伪随机数序列$

  • 例：关键码集为：{47，7，29，11，16，92，22，8，3}，散列表长m=11，散列函数为$Hash(key)=key \ mod \ 11$,拟用线性探测法处理冲突

    0 1 2 3 4 5 6 7 8 9 10
    11 22 47 92 16 3 7 29 8
    • 使用线性探测法解释：
    1. 47、7均是由散列函数得到的没有冲突的散列地址;
    2. Hash(29)=7，散列地址有冲突，需寻找下一个空的散列地址由$H=(Hash(29)+1) mod \ 11=8$，散列地址8为空，因此将29存入。
    3. 11、16、92均是由散列函数得到的没有冲突的散列地址:
    4. 另外，22、8、3同样在散列地址上有冲突，也是由H,找到空的散列地址的。
      • 平均查找长度ASL=(1+2 +1 +1 +1 +4 +1 +2 +2)/9=1.67
    0 1 2 3 4 5 6 7 8 9 10
    11 22 3 47 92 16 7 29 8
    • 使用二次探测法解释：
      • Hash(3)=3散列地址有冲突，由于$H_1=(Hash(3)+1^2)mod \ 11=4$，仍然冲突；
      • $H_2=(Hash(3)-1^2)mod \ 11=2$找到空的散列地址，存入
7.4.3.2 链地址法（拉链法）

  • 基本思想：相同散列地址的记录链成一单链表

  • m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态结构。

  • 链地址法建立散列表的步骤

    • step1：取数据元素的关键字key，计算其散列函数值 (地址)。若该地址对应的链表为空，则将该元素插入此链表；否则执行Step2解决冲突。
    • step2：根据选择的冲突处理方法，计算关键字key的下一个存储地址若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表

  • 链地址法的优点：

    • 非同义词不会冲突，无“聚集”现象
      • 链表上的结点空间动态申请，更适合于表长不确定的情况

7.4.4 散列表的查找

  • 给定值查找值k，查找过程：
1
2
3
4
5
6
7
8
9
graph TD
A[给定k值]==>B(计算H)
B==>C{此地址为空}
C-->|N|D{关键字==k}
C-->|Y|G[查找失败]
D-->|N|E[案处理冲突方法计算Hi]
D-->|Y|H[查找成功]
E-->C
F[竖向流程图]

  • $ASL=(16+2+33+4+9)/12=2.5$

  • 用连地址法处理冲突：

  • $ASL=(16+24+3+4)/12=1.75$

  • 使用平均查找长度ASL来衡量查找算法，ASL取决于

    • 散列函数
    • 处理冲突的方法
    • 散列表的装填因子α
      • $\Large α=\dfrac {表中填入的记录数}{哈希表的长度}$
      • α越大，表中的记录数越多，表越满，发生冲突的可能性就越大，查找时比较次数就越多
    • 无冲突时才能达到O(1)
    • $\large ASL≈1+\dfrac {α}{2}$
    • $\large ASL≈\dfrac {1}{2}(1+\dfrac{1}{1-α})$
    • $\large ASL≈-\dfrac{1}{α}ln(1-α)$

  • 结论

    • 链地址法优于开地址法
    • 散列表技术具有很好的平均性能，优于一些传统的技术
    • 除留余数法作散列函数优于其它类型函数