二叉树相关

树 ...


一致性哈希

一致性哈希是一种特殊的哈希过程,它被用于bucket数量会动态变化的场景中。所谓的“一致性”是指当bucket数量发生改变时,绝大多数的key-value映射关系都不会改变。若使用不具备“一致性”特性的哈希过程,几乎所有的key-value映射关系都将遭到破坏。

哈希的一般过程是:用户输入一个key,由哈希函数计算得出哈希值,然后基于这个值再算出一个索引号,最后用该索引号在一组bucket中检索出一个特定的bucket,在该bucket中读写value:

上图假设4个字符串类型的key ...


循环式code queue

Push code back

将code排到队尾,用四个字节来记录该code的长度。

Pop ...


红黑BST的基本操作过程

红黑BST是2-3查找树的一种具体实现方式,它将2-3查找树中的3-节点视为两个相连的2-节点,并对链接设定了颜色(红,黑)属性以描述这些特殊的2-节点。这样就不用再为3-节点定义专门的数据结构,基础操作直接复用BST的逻辑即可,基于基础操作可方便地实现更多更高级的操作。

红黑BST的基本设定:

  • 红色链接一律为左链接
  • 不可出现同时与两条红链接相连的节点

《2-3查找树的基本操作过程》中讨论删除操作的时候,把3-节点视为两个2-节点相连,且规定后来的那个节点为子节点,于是得到了下图。此时的链接就不都是左链接。

一个节点与两条红色链接相连的情况 ...


2-3查找树的基本操作过程

假设一组key:{ 9, 3, 8, 1, 2, 10, 4, 5, 7, 6 }

执行操作:put(key)、del(key)、get(key),只考虑key,不考虑value ...


二叉树的几个术语

根(root)节点、内部(inner)节点、叶子(leaf)节点。

边 ...