1、红黑树概述

红黑树是一种近似平衡的树，没有像AVL树那样严格的平衡，但是AVL树为了保证它的绝对平衡，对插入和删除的效率有一定的影响，而红黑树插入和删除的效率就要高的多。同时，它又是一颗二叉查找树，使得它查找的效率也很高，查找的时间复杂度为O(logn)，所以红黑树要优于AVL树。

2、红黑树特性

1. 根结点为黑
2. 结点为红或黑
3. 不能有连续的两个红结点(红结点的子结点必须为黑)
4. 任一结点到它们子孙结点的所有路径上黑结点的数量相等
5. 叶子结点为黑(这里的叶子结点指的是null结点)

3、补充特性

1. 最长路径上的结点数量不大于最短路径上结点数量的两倍
2. 若结点只有一个子结点，则子结点的子结点为叶子结点，且子结点为红

4、左旋

5、右旋

6、查找

7、插入

8、删除

9、总结