一。红黑树(RB-Tree)
红黑树是每个节点都有’颜色’特征的平衡二叉查找树。
除了一般平衡二叉树做具备的条件,它还具有如下特征:
1) 节点的颜色是红色或者黑色;
2) 根节点的颜色是黑色的;
3) 如果一个节点时带红色属性的,那么它的子节点必须是黑色的;
4) 所有叶子节点是黑色的(叶子节点为NULL节点);
5) 从任一节点开始到其叶子(NULL)节点的所有简单路径中,包含相同数目的黑色节点。
基于红黑树的实现的SGI STL容器包括:set,map,multiset,multimap等。
二。B树
B树是一种平衡的多叉树,通常所说的m阶B树应该具备这些条件:
1)每个节点最多有m个子节点;
2)除根节点和叶子节点外,每个节点至少有[ceil(m/2)]个子节点,ceil()为取上限函数;
3)所有的叶子节点都在同一层,叶子节点不包含任何关键字的信息;
4)有n个关键码的非叶子节点恰好有n+1个子节点。
B树多用于磁盘数据库的索引实现方式。
三。B+树
B+树是B树的变体,也是一种多叉搜索树。它与B树的主要区别是:
1)非叶子节点的子树指针与关键字个数相同;
2)非叶子节点的相邻子树指针p[i]和p[j],p[i]指向关键字键值在v[i]~v[j-1]之间;
3)所有需要查找的关键字信息存储在叶子节点,并且在它们之间增加了链表指针;非叶子节点只作为索引的一部分,也即是所有查到要搜索到叶子节点才能结束。
B+树中叶子节点增加链表指针是方便插入元素或者删除元素时引起的裂变或者合并操作的实现。B+树更加适合于文件索引系统。
分享到:
相关推荐
C++课程信息管理系统链表STL版-(43536).pdfC++课程信息管理系统链表STL版-(43536).pdfC++课程信息管理系统链表STL版-(43536).pdfC++课程信息管理系统链表STL版-(43536).pdfC++课程信息管理系统链表STL版-(43536)....
C++ STL--数据结构与算法实现(余文溪)示例程序代码.rar
STL源码剖析--侯捷,STL源码剖析--侯捷STL源码剖析--侯捷STL源码剖析--侯捷STL源码剖析--侯捷
三十分钟掌握STL三十分钟掌握STL三十分钟掌握STL三十分钟掌握STL三十分钟掌握STL三十分钟掌握STL三十分钟掌握STL
STL详解--Database 标签库.htm
方便侧睡的stl模型,文件不大。stl模型-机器小人-测试模型
25-STL课件-235ye-c
三十分钟掌握STL三十分钟掌握STL三十分钟掌握STL三十分钟掌握STL
numpy_stl-2.16.0-cp38-cp38-win32
Effective+STL+.pdfEffective+STL+.pdfEffective+STL+.pdfEffective+STL+.pdf
19 STL初识-STL的基本概念
STL源码剖析--教程精华STL源码剖析--教程精华STL源码剖析--教程精华STL源码剖析--教程精华STL源码剖析--教程精华STL源码剖析--教程精华STL源码剖析--教程精华
Effective+STL+中文版.pdf
(源代码)基于numpy-stl操作stl文件-读取圆台z轴截面的周长
stl 的list 的C实现的中间过程,剩下的问题不解释。看不懂,说明不具有了解STL的基础前提!
STL C++ - Standard Template Library (SOURCE + COMPLETE html man document) - tutorial [shared by AESIS].zip
STL入门经典讲义,快速入门的手册。学习STL和C++有很好的指导。
STL 源码
20 STL初识-vector存放内置数据类型
02C STL总结-基于算法竞赛.pdf