-
排序
红黑树
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+树好。
数据结构
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 1)这本书为什么值得看: Python语言描述,如果学的Python用这本书学数据结构更合适 2016年出版,内容...