关于二叉树、平衡二叉树、红黑树
目录
参考文章：记一次腾讯面试：有了二叉查找树、平衡树（AVL）为啥还需要红黑树？
1、二叉树缺点
二叉查找树，相信大家都接触过，二叉查找树的特点就是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大，如图
缺点：
- 一般情况下，查找基于二分查找，查找的时间复杂度为O(logn);
- 当二叉树不够平衡，甚至退化成类似链表结构的时候，查找的时间复杂度为O(n)。耗时。
2、平衡二叉树
平衡二叉树就是为了解决二叉查找树退化成链表。
平衡树具有如下特点：
1、具有二叉查找树的全部特性。
2、每个节点的左子树和右子树的高度差至多等于1。
- 平衡树基于这种特点-----就可以保证不会出现大量节点偏向于一边的情况了。
- 关于平衡树如何构建、插入、删除、左旋、右旋等操作这里不在说明，具体可以看我之前写的一篇文章：【漫画】以后在有面试官问你AVL树，你就把这篇文章扔给他。
时间复杂度：
对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。
3、为什么有了平衡二叉树，还要红黑树？
答：因为平衡二叉树在增删场景较多的场景下，性能表现不好，涉及到多次左旋、右旋。而红黑树适合插入、删除较多的场景，其性能在插入、删除的场景下表现更好。
虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树。
红黑树和平衡树的比较：
1. AVL树比红黑树更为平衡，其搜索效率也好于红黑树, 经过我们之前的分析可以知道, 红黑树在最坏的情况下搜索时间复杂度为2logn，大于AVL树的logn。AVL树是严格平衡，红黑树只能达到“黑平衡”，即从任意节点出发到叶子节点经过的黑节点数量相同，但经过的红色节点数量不确定，最差的情况下，经过的红色节点和黑色节点一样多。
2. 红黑树增删节点的性能优于AVL树，当我们往红黑树增加节点或删除节点引起红黑树不平衡，我们只需要最多三次旋转就能解决，而相同条件下，AVL树的旋转次数要多于红黑树，因此红黑树在增删节点上相较于AVL树更优
- 具体实现原理：https://zhuanlan.zhihu.com/p/95892351（讲述2-3树、红黑树）
- 时间复杂度：
查找：作为红黑树，存在着最坏的情况，也就是查找的过程中，经过的节点全都是原来2-3树里的3-节点，导致路径延长两倍，时间复杂度为O(2logn)。
由于时间复杂度的计算可以忽略系数，因此红黑树的搜索时间复杂度依然是O(logn)，当然，由于这个系数的存在，在实际使用中，红黑树会比普通的平衡二叉树（AVL树）搜索效率要低一些。
调整：红黑树的创建
- 红黑树特点？
- 具有二叉查找树的特点；
- 节点是红色或黑色；
- 根是黑色；
- 所有叶子都是黑色（叶子是NIL节点）；
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。