红黑树

红黑树其实就是一种数据结构，设计它的目的就是为了高效地进行增删改查，我们可以从二叉查找树逐渐引入到红黑树：

一、二叉查找树

特性：
（1）左子树上所有结点的值均小于或等于它的根结点的值；
（2）右子树上所有结点的值均大于或等于它的根结点的值。

如果想要查找一个数：
在查找的时候，先与根节点比较，比根节点大则从右子树查找，比根节点小则从左子树查找，然后重复上面的过程，一直到找到我们需要的元素为止。
其实对于添加和删除，原理也是一样的，我们第一步就是找到我们需要插入的位置，然后把元素插入即可。

缺点：
普通的二叉查找树在极端情况下可退化成链表，此时的增删查效率都会比较低下。

例如，如果以9位根节点，当依次插入13、15、17、19后，就会发生“一边倒”的情况，二叉查找树的优势完全丧失了。
二叉搜索树退化成了链表，搜索的时间复杂度为 O(n)。
叉查找树在插入的时候变成了“一条腿”，也就是丧失了平衡，那我们干脆做出一点改进，使用平衡二叉树吧。

二、平衡二叉树

平衡二叉树，也叫作AVL树，

与二叉查找树相比，拥有以下特性：
（1）从任何一个节点出发，左右子树深度之差的绝对值不超过1；
（2）左右子树仍然为平衡二叉树。

如果需要插入一个数：
如果该树破坏了平衡，则平衡二叉树相应地会发生左旋或者右旋，二叉树就重新回到了平衡。
最终会发现一个结论，那就是平衡二叉树在插入时最多只需要两次旋转就会重新恢复平衡。

平衡二叉树在查找时既有着二叉查找树的优越性，在插入时还能通过调整继续保持着。
那么为什么还要使用到红黑树呢？我觉得可以从以下两个方面来考虑：
（1）删除：对于平衡二叉树来说，在最坏情况下，需要维护从被删节点到根节点这条路径上所有节点的平衡性，旋转的量级是O(logN)。
但是红黑树就不一样了，最多只需3次旋转就会重新平衡，旋转的量级是O(1)。
（2）保持平衡：平衡二叉树高度平衡，这也就意味着在大量插入和删除节点的场景下，平衡二叉树为了保持平衡需要调整的频率会更高。

三、红黑树

红黑树是一种自平衡的二叉查找树，是一种高效的查找树；
红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作；
红黑树和名字一样，里面涉及到两种颜色：红色和黑色。

如图可知，他有如下重要特征：
（1）每个节点只有两种颜色：红色和黑色。
（2）根节点是黑色的。
（3）每个叶子节点（NIL）都是黑色的空节点。
（4）从根节点到叶子节点，不会出现两个连续的红色节点。
（5）从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。
这段关于 红黑树 的描述来源于**《算法导论》**
这五条特征看起来真的很复杂，不过正是由于这些复杂的特征才保证了红黑树的良好特性

四、使用场景：

1、java中的HashMap和TreeMap；
2、Linux内核中一个常见的数据结构。

---

参考链接：红黑树详解