红黑树
红黑树是从2-3-4树演变而来的，2-3-4树是一种自平衡的B树，每个节点可以有2、3、4个子节点。
特性
- 每个节点是红色或黑色
- 根节点是黑色
- 每个叶子节点是黑色
- 如果一个节点是红色的，则它的两个子节点都是黑色的
- 从根节点到叶子节点的所有路径上，黑色节点的数量是相同的
操作
插入
删除
查找
LLRB(Left-Leaning Red-Black Tree)是一种红黑树的变种，它的特点是每个节点都是红色或黑色，并且每个节点都是左倾的，即每个节点的右子节点都是黑色的。 LLRB的树属性 We now specify some properties of LLRB trees. In particular, we use the one-to-one mapping between valid LLRB trees and 2-3 trees to derive some of these properties. 现在我们来具体说明 LLRB 树的一些性质。具体来说，我们利用有效 LLRB 树与 2-3 树之间的一一映射关系来推导其中的一些性质。
Using colored nodes as our representation, the root node must be colored black. 使用彩色节点作为我们的表示，根节点必须是黑色的。 Our interpretation of red nodes is that they are in the same 2-3 node as their parent. The root node has no parent, so it cannot be red. 我们对红色节点的解释是，它们与其父节点位于同一个 2-3 节点中。根节点没有父节点，因此它不可能是红色的。 If a node has a red child, it must be on the left. 如果一个节点有一个红色的子节点，那么它一定在左边。 This makes the tree left-leaning. 这使得树向左倾斜。 No node can have two red children. 任何节点都不能有两个红色子节点。 If a node has two red children, then both children are in the same 2-3 node as the parent. This means that the corresponding 2-3 node contains 3 keys, which is not allowed. 如果一个节点有两个红色子节点，则这两个子节点都与父节点位于同一个 2-3 节点中。这意味着对应的 2-3 节点包含 3 个键，这是不允许的。 No red node can have a red parent (every red node’s parent is black). 红色节点不能有红色父节点（每个红色节点的父节点都是黑色节点）。 If a red node has a red parent, then both the red child and red parent are in the same 2-3 node as the red parent’s parent. This means that the corresponding 2-3 node contains 3 keys, which is not allowed. 如果一个红色节点有一个红色父节点，那么它的红色子节点和红色父节点都位于与红色父节点的父节点相同的 2-3 节点中。这意味着对应的 2-3 节点包含 3 个键，这是不允许的。