红黑树

红黑树是二叉平衡树的一种，包括 5 种性质

1. 根节点是黑色
2. 节点颜色要么黑色，要么红色
3. 每个叶子节点是黑子
4. 任意节点到每个叶子节点的路径中包含的黑节点树 相等
5. 每个红色节点的两个子节点的一定都是黑色（不能有两个连续的红节点）

红色树通过左旋，右旋，变色来实现平衡

• 左旋: 旋转节点的右节点变成父节点，选择节点变成右节点的左节点，右节点的左节点变成选择节点的右节点

• 右旋: 旋转节点的左节点变成父节点，旋转节点变成左节点的右节点，左节点的右节点变成旋转节点的左节点

插入流程