红黑树

性质:

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 每个叶子节点都是黑色的空节点
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

Red Black Tree

Knuth-Morris-Pratt算法

字符串BBC ABCDAB ABCDABCDABDE，想知道，里面是否包含另一个字符串ABCDABD？

CopyOnWrite

写入时复制（CopyOnWrite）核心思想是如果有多个调用者同时要求相同的资源，他们会共同获取相同的指针指向相同的资源，直到某个调用者视图修改资源内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。主要优点是如果调用者没有修改资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。

Reference:

  1. 漫画算法：什么是红黑树？
  2. 字符串匹配的KMP算法
  3. 字符串匹配的Boyer-Moore算法