红黑树

一、为什么会有红黑树？       

红黑树也是一种二叉查找树。对于普通的二叉查找树来说，如果不经任何处理，左右子树的高度相差严重时，查找的效率会退化为链表。为了维护左右子树高度的平衡，引入了AVL二叉树。AVL树严格符合平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过1，是一种高度平衡的二叉查找树。平衡二叉树中平衡的意思，其实就是让整棵树左右看起来比较对称、比较平衡，降低树的高度，相应的插入、删除、查找等操作的效率高一些。红黑树是一种近似平衡的二叉树，之所以说近似平衡，是因为它对平衡的要求比AVL要低，因此维护平衡的成本也要低一些，实际开发过程中红黑树的应用范围要较AVL树较广。

二、红黑树的定义

1. 根节点是黑色的
2. 每个叶子节点都是黑色的空节点，也就是说，叶子节点不存储数据
3. 任何相邻的节点不能同时为红色
4. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。

三、红黑树的时间复杂度

红黑树的高度近似log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是O(logn)。

四、关于红黑树

对于一般开发人员来说，了解红黑树的来历、时间复杂度和应用就足够了。至于红黑树左旋右旋及着色操作等不是需要硬性了解的内容。个人观点而已。