🍕 有序表

实现方式有：

• （平衡）搜索二叉树
  • AVL 树
  • SB 树（好改）
  • 红黑树
• 链表
  • 跳表（skip list）

搜索二叉树

• 添加
• 查找
• 删除。
  • 没有孩子
  • 只有一个孩子
  • 有两个孩子

搜索二叉树 + 平衡

维持平衡时的操作：

• 左旋：头结点倒向左边
• 右旋：头结点倒向右边

如何检查是否平衡：

• 从受影响的节点（添加和删除某个节点）出发，向上检查每个节点的平衡性
• 破坏平衡性的四种情况：
  • LL型：左子树左边过长。左旋一下
  • RR型：右子树右边过长。右旋一下
  • LR型：左子树右边过长。想办法让左子树的右节点成为头部 —— 先在小局部上左旋，再在大局部上右旋
  • RL型：右子树左边过长。想办法让右子树的左节点成为头部 —— 先在小局部上右旋，再在大局部上左旋

红黑树、AVL 树和 SB 树的增删改查都是一样的，不一定的点在于对“平衡”的定义。

• AVL 树是严格的平衡 —— 每一颗子树的高度差都不超过一。
• SB 树，它判断平衡的标准是：
  • 每一颗子树的大小，不小于其兄弟的子树大小。
  • 比如：

        A
    B       C
  D   E    F  G
  .............
要求 B 包含的节点数量，大于 C 子树包含的节点数量，即大于 F 的节点数量，也大于 G 的节点数量

• 红黑树，它想要做到的是：最长路径和最短路径的长度比例不超过 2
  • 给每一个节点贴上标签：红或黑
  • 规定头结点和叶节点（在红黑树中指空节点）是黑色
  • 要求红节点不相邻（即红节点不可能直接到达红节点）
  • 要求每个节点到叶节点（空节点）的黑节点数量相同
  • 也就是说，最长的路就是红黑红黑红黑，最短的路就是黑黑黑黑黑。因为保证了黑节点数量相同，所以长度比例不会超过 2
  • 没必要深究红黑树，泛平衡的搜索二叉树很多种实现。红黑树纯粹就是智力盛宴

跳表

• 多链表结构。每传入一个数字，该数字都代表一个链表。
• 一个链表上有几个节点，表示这个链表有几层。默认一定有 0 层
• 具体有几层，通过概率计算。有 0.5 的概率增多一层。简单的说就是所有数字中：
  • 拥有 0 层的数字有 N 个
  • 拥有 1 层的数字大概有 N/2 个
  • 拥有 2 层的数字大概有 N/4 个
  • 拥有 3 层的售出大概有 N/8 个
  • ....
• 每个 0 层之间的连接是有序的。
• 存在一个默认链表，该链表的层数始终等于最高层的层数。
• 画出图来就像是高度层次不平的一排高楼

┏━┓ →  →  →  →  →     →  →  →  →  →  →  →  →  → ┏━┓
┃ ┃ →  →  →  →  → ┏━┓ →  →  →  →  →  →  →  →  → ┃ ┃
┃ ┃ →  →  → ┏━┓ → ┃ ┃ → ┏━┓ →  →  →  →  →  →  → ┃ ┃
┃ ┃ →  →  → ┃ ┃ → ┃ ┃ → ┃ ┃ →  →  →  →  →  →  → ┃ ┃
┃ ┃ →  →  → ┃ ┃ → ┃ ┃ → ┃ ┃ →  →  →  →  →  →  → ┃ ┃
┃ ┃ → ┏━┓ → ┃ ┃ → ┃ ┃ → ┃ ┃ → ┏━┓ → ┏━┓ → ┏━┓ → ┃ ┃
┃ ┃ → ┃ ┃ → ┃ ┃ → ┃ ┃ → ┃ ┃ → ┃ ┃ → ┃ ┃ → ┃ ┃ → ┃ ┃
默认    0    10    15    20    21    50    90    100

效率的提升在于，比如想找大于 14 的值时，

• 从默认节点的最顶层开始找，发现它指向 100，于是在默认链表中进入下一层
• 发现它指向 15，于是它会直接跳到 15 的最顶层。
• 这个过程中直接跨过了 0,10 两个节点。 又比如，查找大于 95 时，可以直接跳到 100，直接跨过了哪些层数比较低的层。