红黑树

Red-Black Tree

红黑树是一种近似平衡的二叉搜索树（Binary Search Tree），它能够确保任何一个结点的左右子树的高度差小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树：

• 每个结点要么是红色，要么是黑色。

• 根节点是黑色。

• 每个叶结点（NIL 结点，空节点）是黑色的。

• 不能有相邻接的两个红色结点。

• 从任意节点到其每个叶子的所有路径都包含相同数目的黑色结点。

AVL 数 与 红黑树 的对比

1. AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced.

2. Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing.

3. AVL trees store balance factors or heights with each node, thus requires storage for an integer per node whereas Red Black Tree requires only 1 bit of information per node.

4. Red Black Trees are used in most of the language libraries like map, multimap, multiset in C++ whereas AVL trees are used in databases where faster retrievals are required.

参考链接

Red Black Tree vs AVL Tree - GeeksforGeeksGeeksforGeeks

• 维基百科：平衡树