算法—查找


  • 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

  • 算法第四版

查找

  • 基于符号表的抽象来组织查找有关内容.分为 key-value ,有时又称字典.
  • 分别介绍 二叉查找树 红黑树 及 散列表 3种经典的实现.

符号表

  • 定义: 存储键值对的数据结构,支持put插入 及 get查找操作.

  • API:

    1
    2
    3
    4
    5
    6
    7
    void put(Key key,Value val)
    Value get(Key key)
    void delete(Key key)
    boolean contains(Key key)
    boolean isEmpty()
    int size()
    Iterable<Key> keys()
  • 规则

    • 没有重复key
    • key不能为空
    • value不能为空
    • 删除操作即使实现.
    • key为不可变类型数据.
  • 成本

    • 使用比较次数来统计成本.
    • 内循环不进行比较时,统计数组访问次数.

其他

  • 有序符号表

    • 额外API
    1
    2
    3
    4
    main()
    max()
    floor(Key key)
    select(int k)
  • 无序符号表

    • 经典的基于链表实现.

二叉查找树BST

  • 数据结构:结点

    • 一个唯一key
    • 对应value
    • 一条左链接
    • 一条右链接
    • 一个节点计数器(该节点的子节点总数)
  • get方法
    表中存在对应方法即返回对应值,否则返回空.
    代码:递归实现

    • 实现get(Node x,Key key)
      • 查找Key 对应值,没有返回null
      • 对比 x 与 key 值.
      • 根据结果返回 get(x.right,key) or get(x.left,key)
    • get由传入根节点调用 get(Node x,Key key)
  • put方法
    存在则更新值,不存在则插入新值.
    代码:递归实现

    • 实现Node put(Node x,Key key,Value val)
      • x为空,则创建新节点并插入key val
      • 对比x key 值
      • x = key,则更新值.
      • 根据结果返回 put(x.right,key,val) or put(x.left,key,val)
      • 更新节点计数器
    • put传入根节点 调用Node put(Node x,Key key,Value val)
  • 分析

    • 如同union-find问题,二叉树生长的方式及平均深度对查找及插入的影响很大.二叉查找树性能非常依赖于 key分布足够随机.

有序符号表

  • 最大最小

    • 传入节点左链接是否为空? 返回传入节点 : 递归调用min(x.left)
    • 传入节点左链接是否为空? 返回传入节点 : 递归调用mam(x.right)
  • 向上/下取整

    • 递归
      • 传入节点左链接 为空.返回 null
      • 传入节点左链接 = key-value 返回 传入节点
      • 传入节点左链接 < key-value 返回 递归传入左链接
      • 传入节点左链接 > key-value 递归传入右链接
        • 判断返回值t 为空?
          • 不为空返回 t
          • 为空返回传入节点.
    • 递归调用.
  • 排名

    • 与节点计数器有关.
    • key = 传入节点,返回左子树节点总数.
    • key < 传入节点,返回 递归左子树.
    • key > 传入节点,返回 递归右子树.
  • 删除最大/最小键

    • 删除最大/最小值,因其子链接均为空,无妨.
  • 删除 -二叉树中间呢?

    • 查找到要删除的节点
    • 保存 父链接 左右子链接.
    • 选择右子树,查找最小节点.(不断选择左子树,直到遇到左子链接为空元素)
    • 将 右子树最小元素 移植到 已删除元素位置.
    • 处理 右子树最小元素 右子链接(直接链接到父节点)
    • 可能存在性能问题.
  • 范围查找

    • 首先遍历操作
      • 递归要不要简单
      • x为空? 返回
      • 过程处理.
      • 不为空, 递归左节点 递归右节点.
    • 在过程处理中进行过滤操作.
    • 因二叉树数值相对有序,舍弃掉不存在想要值的子树.

平衡查找树


  • 只使用二叉树而保持树生长的平衡,代价很高.
  • so,对节点的基础数据结构动一些手脚,引入 2-3 树.
  • 最大的变化在于插入新元素.但随之带来的完美平衡的 2-3 树,让数据结构复杂度很值.

  • 节点可以保存2个key,3个子链接.代表 <a ,a< <b ,>b 3种.

  • 随之带来的好处,树可以一直保持为 完美平衡.所有空链接,到根节点的距离相同.

  • 查找

    • 相对二叉树变动不大.依旧是递归实现.
    • 在判断时加入了2 3节点的指向判断,难度不大,直到遇到空链接为止.
  • 插入

    • 我们所设想的依旧是通过递归的方式实现.尽量统一实现方式.

    • 过程类似,查找插入位置->插入数据->恢复

      • 空节点

        • 直接插入数据即可
      • 2节点

        • 将2节点,变更为3节点.
      • 3节点(比较麻烦)

        • 父节点为空: 直接存入数据->节点变为4节点->4节点分解为3个 2节点,深度+1.
        • 父节点为2节点: 直接存入数据->节点变为4节点->将父节点变为3节点->4节点分解为两个 2节点.
        • 父节点为3节点: 直接存入数据->节点变为4节点->将父节点变为4节点->父节点向上反推过程,直到遇到2节点为止->4节点分解为两个2节点.
        • 整个过程: 存入变4节点,向上反推 直到遇到空节点/2节点为止.分解恢复2-3树.
      • 性能

        • 即使最坏情况下,大小为N的 2-3 树,插入及查找操作访问节点必然不超过 lgN ,因为2-3树保持了完美的平衡.
        • 但额外的维护代码冗余,由此引出红黑树.

红黑树

  • 将2-3树中 1个 3节点 拆分为 2个2节点,中间使用红色链接.

  • 插入/删除 相较于2-3树,复杂.但基础数据结构简单.

  • 牺牲一些平衡性,换来 程序设计的便利.

  • 前置要求

    • 节点是红色或黑色。
    • 根是黑色。
    • 所有叶子都是黑色(叶子是NIL节点)。
    • 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
    • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
  • 数据结构

    • 在二叉树基础上增加了节点颜色一项.其他不变.

方法实现

基础操作

  • 右/左旋

  • 颜色变化

  • 查找

    • 与二叉树查找相同.
  • 插入

    • 类比2-3树,更加复杂,但基本过程一致.
    • 查找位置->插入节点->修复红黑树.
    • 插入

散列表