时间复杂度
O(1) 表示一次操作即可直接取得目标元素（比如字典或哈希表），
O(n) 意味着先要检查 n 个元素来搜索目标
常见的时间复杂度有：
常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),k次方阶O(nk),指数阶O(2n)。
O(log n)
二分搜索一定有某种行为使其时间复杂度为 log n。
最好情况下二分搜索的时间复杂度是 O(1)，最坏情况（平均情况）下 O(log n)。
设有 16 个元素的有序数组，最坏情况下
| 次数搜索 | 范围缩小至 | 计算 | 是否找到值 |
|---|---|---|---|
| 一 | 8 | 16*1/2 = 8 | 否 |
| 二 | 4 | 8*1/2 = 4 | 否 |
| 三 | 2 | 4*1/2 = 2 | 否 |
| 四 | 1 | 2*1/2 = 1 | 是 |
n就是我们所需要遍历的数组个数（16），底数是2，k就是时间复杂度（4）
但是 O(log2n)为什么会变成O(log n) 呢
logcA（c为底数）为常数，由O的运算规则"O(C×f(N))=O(f(N))，其中C是一个正的常数"得O（logaB）=O（logcB）可知算法的时间复杂度与不同底数只有常数的关系，均可以省略自然可以用logN代替。
例
Binary Search Tree(时间复杂度 O(log n) )
最坏情况下的时间复杂度
| 操作 | 二叉查找树 | 平衡二叉树 | 红黑树 |
|---|---|---|---|
| 查找 | O(n) | O(log n) | O(log n) |
| 插入 | O(n) | O(log n) | O(log n) |
| 删除 | O(n) | O(log n) | O(log n) |
二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和位置数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NULL）。根结点是树中唯一父指针为NULL的结点，而叶子结点的孩子结点指针也为NULL。
在二叉搜索树中：
1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树。
AVL树（最先发明的自平衡二叉查找树）
在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树
引入对左右子树高度差有限制的平衡二叉树，保证查找操作的最坏时间复杂度也为O(logN)
红黑树是一种特化的AVL树（平衡二叉树）
红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。
有了平衡二叉树，为什么还需要红黑树？
AVL的左右子树高度差不能超过1，每次进行插入/删除操作时，几乎都需要通过旋转操作保持平衡
在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL的性能大打折扣
红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，整体性能优于AVL
红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决
红黑树的红黑规则，保证最坏的情况下，也能在O(log_{2}N)时间内完成查找操作。
节点不是红色就是黑色，根节点是黑色
红黑树的叶子节点并非传统的叶子节点，红黑树的叶子节点是null节点（空节点）且为黑色
同一路径，不存在连续的红色节点
B树
M阶B树性质：
- 根节点至少有两个子节点。
- 其他节点至少有M / 2个子节点。
- 每个节点最少2个key，最多M - 1个key。
- 位于父节点两个key之间的子节点的值位于父节点两个key对应的value之间。
B树的弊端
除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。
（其他关联数组的实现，例如三元搜索树或者开散列哈希表，可以动态适应任意长度的键值）。
B+树
B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:
(1)每个结点至多有m个子女；
(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；
(3)有k个子女的结点必有k个关键字。
B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。
B+树是B树的一种变形，比B树具有更广泛的应用，m阶 B+树有如下特征:
(1)每个结点的关键字个数与孩子个数相等，所有非最下层的内层结点的关键字是对应子树上的最大关键字，最下层内部结点包含了全部关键字。
(2)除根结点以外，每个内部结点有 到m个孩子。
(3)所有叶结点在树结构的同一层，并且不含任何信息(可看成是外部结点或查找失败的结点)，因此，树结构总是树高平衡的。
B树和B+树的区别
1.B树每个节点都会有数据域和关键字，而B+树是在非叶子节点是没有数据域的，所有数据与都在叶子节点中，并且各个叶子节点之间通过指针相连接。
2.B树的查询最好时间复杂度为O(1）最差O（log n），B+树的查询时间复杂度固定为O（log n）。
3.B树更适合查找某一频繁出现的数据，同时B树无法进行范围查找，而B+树可以进行范围查找，只需要找到叶子节点最小的数据然后通过链表O(N)的时间复杂度就能查找整个数据的范围。
4.B+树只需要遍历叶子节点便可以实现整棵树的遍历，包含关键字并有序存储，增删效率更高。
