这里先介绍一下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)。
为什么会出现红黑树呢,为了防止在极端情况下,二叉树退化成链表导致检索效率大大降低的问题。他肯定是排序二叉树,然后在其基础上,加上了red和black,通过变色和左旋右旋来保持他的特征。