RB-Tree 红黑树

红黑树是一棵”黑平衡“的二叉树，任意叶子节点到根节点所经过的黑节点个数相等。红黑树的本质是一棵 2-3树。

红黑树是一个相对平衡的二叉树，其平衡程度介于 二分搜索树 和 AVL 之间。由于AVL是一棵绝对平衡的二叉树，所以维护它的平衡的开销将会非常大。而实际情况中，数据的来源并不会特别极端(比如完全有序插入二叉树中)，过于注重二叉树的平衡性会变得性价比很低。这时红黑树就派上用场了，既可以防止二叉树退化成一个链表，同时维护起来的开销也不如 AVL。要弄清楚红黑树，可以从2-3树开始理解起。