红黑树

红黑树的主要规则

1. 每个节点不是红色就是黑色
2. 根节点总是黑色的
3. 如果节点是红色的，则它的字节点必须是黑色的（反之不一定）
4. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

红-黑树主要通过三种方式对平衡进行修正，改变节点颜色、左旋和右旋。

log
lg

手写红黑树
网站
二叉平衡树
二叉搜索树