0402 - 数据结构

用于二级制表示字符串

二叉搜索树满足这样的条件，每个节点包含一个值，每个节点至多有两个子树。每个节点左子树节点的值都小于自身的值，每个节点右子树节点的值都大于自身的值。

二叉树的查询时间复杂度是 log(N)，但是随着不断的插入、删除节点，二叉树的树高可能会不断变大，当一个二叉搜索树所有节点都只有左子树或者都只有右子树时，其查找性能就退化成线性的了

红黑树是一种更加实用的非严格的平衡二叉树。红黑树更关注局部平衡而非整体平衡，确保没有一条路径会比其他路径长出 2 倍，所以是接近平衡的，但减少了许多不必要的旋转操作，更加实用。前面提到过，Java 8 的 HashMap 中就应用了红黑树来解决散列冲突时的查找问题。TreeMap 也是通过红黑树来保证有序性的。

（1）每个节点不是红色就是黑色。
（2）根节点是黑色。
（3）每个叶子节点都是黑色的空节点，如图中的黑色三角。
（4）红色节点的两个子节点都是黑色的。
（5）任意节点到其叶节点的每条路径上，包含相同数量的黑色节点。

B 树是一种多叉树，也叫多路搜索树。B 树中每个节点可以存储多个元素，非常适合用在文件索引上，可以有效减少磁盘 IO 次数。B 树中所有结点的最大子节点数称为 B 树的阶，如下图所示是一棵 3 阶 B 树，也叫 2-3 树。

B 树的关键字分布在整颗树中，一个关键字只出现在一个节点中；
搜索可能在非叶节点停止；
B 树一般应用在文件系统。

节点中的关键字与子树数目相同，比如节点中有 3 个关键字，那么就有 3 棵子树；
关键字对应的子树中的节点都大于或等于关键字，子树中包括关键字自身；
所有关键字都出现在叶子节点中；
所有叶子节点都有指向下一个叶子节点的指针。

与 B 树不同，B+ 树在搜索时不会在非叶子节点命中，一定会查询到叶子节点；另外一个，叶子节点相当于数据存储层，保存关键字对应的数据，而非叶子节点只保存关键字和指向叶节点的指针，不保存关键字对应的数据，所以同样数量关键字的非叶节点，B+ 树比 B 树要小很多。

B+ 树更适合索引系统，MySQL 数据库的索引就提供了 B+ 树实现。原因有三个：
（1）由于叶节点之间有指针相连，B+ 树更适合范围检索；
（2）由于非页节点只保存关键字和指针，同样大小非叶节点，B+ 树可以容纳更多的关键字，可以降低树高，查询时磁盘读写代价更低；
（3）B+ 树的查询效率比较稳定。任何关键字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，效率相当。

最后可以简单了解，还有一种 B* 树的变种，在 B+ 树的非叶节点上，也增加了指向同一层下一个非叶节点的指针。

直接插入排序

希尔排序

简单选择排序

堆排序

冒泡排序

快速排序