红黑树

一种自平衡的二叉树

定义：
根节点和叶子节点（虚拟出来的）都是黑色的，其他的要么黑要么红；
红节点的子节点必须是黑色的；
每个节点到其叶子节点的所有简单路径上的黑色节点数目相同。

插入：
先按二叉查找树的方法插入，插入后染成红色，然后看一下父节点的颜色，如果是黑色，那么插入后符合红黑树的定义，这个节点不用做修改。如果父节点是红色的，那么就需要进行调整，目标就是把父节点调成黑色的。父节点是红色的，则祖父节点是黑色的，因此叔父节点可以为红色也可以为黑色甚至叔父节点不存在，具体需要分为 3 种情况：
1 如果叔父节点存在且为红色，这样子的话父节点和叔父节点都是红色，祖父节点是黑色，直接让祖父节点变成红色，父节点和叔父节点变成黑色就行了；
2 如果叔父节点不存在或者叔父节点存在且为黑色，插入的节点和它的父节点、祖父节点都在一条斜线上，就通过左旋或右旋调整，然后把原来它的父节点和祖父节点交换一下颜色；
3 如果叔父节点不存在或者叔父节点存在且为黑色，插入的节点和它的父节点、祖父节点不在一条斜线上，就通过两次旋转调整，然后把原来它的父节点和祖父节点交换一下颜色。
这个节点调整完毕后回溯看其他节点是否因为这次调整而连带地需要调整，直到根节点为止。

删除：
先按二叉查找树的方法删除，如果删除的节点颜色是红色或者删除的节点是根节点的，那么直接删除即可，如果是红色的，那么需要