16. ADTs, Sets, Maps, BSTs

ADT

抽象数据类型（ADT）是根据操作而非实现来定义的。

BSTs

BST（Binary Search Tree）是一种用于查找的树结构。

在 BST 中：

• 最顶端的节点称为 根（root）
• 任意两个节点之间只有一条路径
• 每个节点可以有：
  • 一个 parent（父节点）
  • 最多两个 children（子节点）
• 如果一个节点没有 children，则称为 leaf（叶子节点）

性质：

• 对于任意节点：
  • 左子树中的所有节点值 小于该节点
  • 右子树中的所有节点值 大于该节点
• 左右子树中的节点值不能相同

BST 的整体关系满足：

• 完整性
• 传递性
• 反对称性

功能 1：搜索

搜索的逻辑如下：

• 从某个节点 (T) 出发：
  • 若目标值 小于 (T)，进入 左子树（T.left）
  • 若目标值 大于 (T)，进入 右子树（T.right）

搜索的时间复杂度在平衡/高度为 log N 时是 Θ(log N)，最坏情况下退化成链表是 Θ(N)

功能 2. 插入

• 如果在当前树中找到了欲插入的值，就什么都不做。
• 如果未找到：
  1. 创建新节点。
  2. 设置相应的链接。

功能 3. 删除

删除是一个较为复杂的功能，分为三种情况：

1. 目标值没有 children
   • 直接丢弃目标值
2. 目标值有一个 child
   1. 丢弃目标值
   2. 将目标值的 child 与目标值的 parent 相连接
3. 目标值有两个 children：
   • 假设有下面的数据结构：

想要删除 k，就要找到一个节点能够替代 k 的存在，即需要满足这两个情况：

1. 必须比右边的全部值都小
2. 必须比左边的全部值都大

有两个节点符合上述条件，分别被称为 predecessor 和 successor

• predecessor 指的是所有比目标节点小的节点中，值最大的那个节点
  • 在上图中，是 g
• successor 指的是所有比目标节点大的节点中，值最小的那个节点
  • 在上图中，是 m

因此，将 g 或者 m 移动到 k 的位置即可

Sets & Maps

上述的二叉树中只有键（key/item），没有值（value），因此可以在每个节点中再包含一个节点，存有相应的数据，以满足更多需求