红黑树
要了解红黑树，首先要知道二叉查找树，因为红黑树是特殊的二叉查找树
二叉查找树
首先它是一颗二叉树
- 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 左、右子树也分别为二叉排序树
来进行查找时，根据二分查找的思想，查找所需的最大次数等同于二叉查找树的高度，但是二叉查找树在极端情况下多次插入新节点会变成线性的链表，导致查找时需要遍历所有节点
红黑树
由于二叉查找树的缺点，红黑树出来了，红黑树是一种自平衡的二叉查找树，可在O(logN)时间内完成查找、增加、删除等操作。除了符合二叉查找树的特性外，还符合以下特性
- 每个节点都是黑色或者红色
- 根节点是黑色
- 每个叶子节点都是黑色的空节点
- 如果一个节点是红色的，则它的子节点必须是黑色的，且从任一节点到其每个叶子节点的所有路径中，黑色元素的数量必须相同
如果在插入和删除节点时导致不符合以上规则时，就会进行调整，调整分为变色和旋转
变色
变色就是尝试把红色节点变成黑色，或者把黑色变成红色
旋转
左旋
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子节点取代，自己成为自己的左孩子节点，也就是说左旋是将某个节点旋转为其右孩子的左孩子
右旋
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己称为自己的右孩子，也就是说右旋是将某个节点旋转为其左孩子的右孩子
插入
在插入的时候节点首先是红色的，然后在进行变色和旋转操作，如果叔叔节点是红色，则直接进行变色；如果叔叔节点是黑色，需要进行旋转然后在变色