数据结构

排序

红黑树
1）每个节点都只能是红色或者黑色
2）根节点是黑色
3）每个叶节点（NIL节点，空节点）是黑色的。
4）如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，红黑树是相对是接近平衡的二叉树。。检索的时间复杂度是O(log n)。
左旋和右旋：https://www.cnblogs.com/skywang12345/p/3245399.html

堆排序
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
1）STEP1：构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

B树和B+树：
B树是一种多路搜索树

B+ 树的优点在于：
由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。