红黑树

红黑树的定义

每个节点要么是红色，要么是黑色。
根节点是黑色。
每个叶子节点（NIL节点，即空节点）是黑色。
如果一个节点是红色，则它的两个子节点都是黑色。
对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点（即，从根节点到叶子节点的所有路径上的黑色节点数目相同，这也是保证树的平衡性的关键规则）。

这些规则确保了红黑树具有以下特征：
任意节点到其后代节点的最长简单路径不超过最短简单路径的两倍。
任意节点到其后代节点的最长简单路径不超过最短简单路径的两倍。