红黑树详解

1、每个节点或者是红色或者黑色。

2、根节点是黑色。

3、红色节点的两个子节点都是黑色。（从每个叶子到根的路径不会出现两个连续的红色）

4、对于每个节点，从该节点到其叶子节点构成的所有路径上黑节点个数相同。

5、所有的叶子节点都是null节点，并且是黑色。

这里先介绍一下O（1），O（n），O（logn），O（nlogn），O（n^2）。

O（1）常数阶：最低的时空复杂度，也就是耗费的时间或者空间与输入的数据大小无关。哈希算法就是典型的O（1）复杂度。

O（logn）对数阶：当数据增大n倍的时候，耗时则值增大了8倍，比线性的耗能更低，二分查找法就是利用这个原理。

O（n）线性阶：代表数据量增大几倍，也就耗时增大几倍。

O（nlogn）对数阶乘以n，这个需要乘以n，所以比线性阶的耗时大。

O（n^2）平方阶：代表着数据增大n倍时，也就消耗n的平方倍。

平方阶上面还有立方阶，指数阶，同理耗时越来越长。

排序二叉树：排序二叉树是有序的，特殊结构的二叉树，可以对所有节点进行检索，但是缺点是当插入的数据正好都是有序的时候，他会退化成链表。这时候时间复杂度就会增加。

平衡树二叉树（AVL）是什么呢，最重要的特性就是最坏的情况下能保证O(logN)的时间复杂度查找，不具备的话可能退化成单链表，时间复杂度会到O（N）。

1、每个节点最多只有两个子节点。（二叉）

2、有序：每个节点的值比他左边树所有节点都大。(必须是排序的)

3、每个节点左边树的高度与右边高度不会超过1。

为什么会出现红黑树呢，为了防止在极端情况下，二叉树退化成链表导致检索效率大大降低的问题。他肯定是排序二叉树，然后在其基础上，加上了red和black，通过变色和左旋右旋来保持他的特征。