二叉查找树(也称二叉搜索树)
- 左子树上的节点值都小于等于根节点的值
- 右子树上的节点值都大于等于根节点的值
- 左右子树也是二叉搜索树
它是基于二分查找的思想，查找最大的次数为二叉树高度
查找代价
- 当左右子树高度大致平衡时，时间复杂度在 O(logN)
- 当先后插入的关键字有序时，退化成链表，查找的时间复杂度就在 O(N)了
插入代价
新节点插入到树的叶子节点上，因此，插入节点和查找一个不存在的数据的代价相同
删除代价
- 如果被删除的节点左、右 有一个为null时，代价仅为 O(1)
- 如果左右子树都存在，时间复杂度最大也不会超过O(logN)
缺陷：
极端情况可能退化成链表，时间复杂度为 n。这主要是由于树不平衡导致的
平衡二叉查找树(平衡二叉搜索树)
是严格的平衡二叉树，它是空树或者左右两个子树的高度差 小于等于1，同时，左右两个子树也是平衡二叉搜索树
查找代价
时间很稳定，查找效率最好最坏都是 O(logN)
插入代价
由于要保证严格的平衡，插入时可能要进行再平衡(最多旋转一次)，因此插入的整体代价还在 O(logN)
删除代价
和插入一样，要考虑再平衡，但是最多需要O(logN)次旋转，所以时间复杂度为 O(2logN)
红黑树(Red-Black Tree)
它并不严格地平衡，最长路径长度不超过最短路径长度的2倍。它删除和插入引起平衡性改变的概率要远低于平衡二叉搜索树
查找代价
查找代价基本上维持在 O(logN) 级别，最差情况下肯定比平衡二叉搜索树要差，因为没有那么平衡
插入代价
不容易引起失衡，整体代价和平衡二叉搜索树差不多，也是 O(logN) 级别(虽然涉及变色，但是变色的代价很小)
删除代价
相对平衡二叉搜索树，不容易引起失衡，时间复杂度也在 O(logN) 级别
补充
平衡二叉搜索树由于插入和删除，会引起需要调整，可以通过 ：变色、左旋转、右旋转 三种方式调整。是否需要调整要根据红黑树的特性：
- 节点是红色或黑色
- 根节点是黑色
- 叶子节点都是黑色的空节点
- 红色节点的两个子节点都是黑的(红节点不能连续出现)
- 任一点到每个叶子节点的路径包含相同数目的黑节点
B-树和B+ 树
我们所谓的B-树，其实并不是B减树，中间是横线，不是减号；B + 就是 B加树了
如 os 的文件目录存储、数据库中的索引结构的存储，不可能在内存中建立查找结构，必须在磁盘中建立好结构。
在磁盘组织结构下，从任何一个节点指向其他节点都可能读取一次磁盘，再将数据写入内存比较。这回带来大量的IO操作，所以我们需要新的数据结构，即 B树和B+树。
B树是一种多路平衡查找树，每个节点最多包含k个孩子，k称为B树的阶。K大小取决于磁盘页的大小。
