红黑树

性质

1. 是一种特殊的**二叉查找树**（任意节点的左子树上的节点小于该节点，右子树上的节点大于该节点）
2. 每个节点都是红色或黑色
3. 每个叶子节点的子节点（NULL节点）为黑色
4. 红色节点的子节点都是黑色
5. 从一个结点到其所有的后代叶子结点的路径上包含的黑色结点数量相同。

性质5确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

应用

主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。

例如：

• Java集合中的TreeSet和TreeMap
• C++ STL中的set、map
• Linux虚拟内存的管理

基本操作

左旋&右旋

添加

1. 将红黑树当作一颗二叉查找树，将节点插入，着色为红色。

2. 由于可能违背了性质4，故需要调整。分三种情况：

   • 叔叔是红色

     

   • 叔叔是黑色，且当前节点是右孩子

     

   • 叔叔是黑色，且当前节点是左孩子

     

删除