红黑树(RB-Tree)

定义

红黑树是一种二叉平衡树。

性质

• 每个节点要么是黑色，要么是红色；

• Root 节点是黑色；

• 每个叶子节点（NIL）是黑色；

• 每个红色结点的两个子结点一定都是黑色；

• 任意一结点到每个叶子结点的路径都包含数量相同的黑结点；

旋转

• 右旋

• 左旋

参考

1. https://zhuanlan.zhihu.com/p/63272157

2. https://zhuanlan.zhihu.com/p/92761639

3. https://mp.weixin.qq.com/s/pwBnKfgivdE5EzBCXubZww