平衡二叉树(AVL树)和红黑树区别

1.二叉搜索树，平衡二叉树，红黑树的算法效率
操作	二叉查找树	平衡二叉树	红黑树
查找	O(n)	     O(logn)	O(log2 n)
插入	O(n)	     O(logn)	O(log2 n)
删除	O(n)	     O(logn)	O(log2 n)
Olog(n)怎么算出来的?
在一个树中查找一个数字，第一次在根节点判断，第二次在第二层节点判断,
以此类推,树的高度是多少就会判断多少次,树的高度和节点的关系就是以2为底,树的节点总数n的对数!

2.为什么工程中都用红黑树，而不是其他平衡二叉树?
<1>.红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保
证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单.一种二叉查找树，但在每个节
点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。
  通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其
它路径长出两倍，因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同的节点情况
下，AVL树的高度低于红黑树），相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插
入，删除操作较多的情况下，我们就用红黑树。


<2>.AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平
衡，左右子树树高不超过1，和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足（所有节
点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要
通过旋转来保持平衡，而的英文旋转非常耗时的，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况.
  由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地
方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是
对查找要求较高，那么AVL还是较优于红黑树。

3.红黑树使用场景?
假设你计算机里存有十亿个身份证信息，你要用计算机在这些身份证信息里进行增加、删除、查找等
操作，应该怎样设计程序实现这些功能？
  最简单的笨办法,当然是逐条比对,但是这样的操作要进行平均1/2x10000000次比对,也就是平均5亿次.
  如果应用红黑树，就只要最多log₂1000000000 = 29.897次比对,也就是最多30次.
  30次 vs 5亿次，程序性能提升了1600多万倍。