2018年国家电网考试备考计算机之数据结构与算法(9)

5、B+树

(图e)

B+数是B-树的一种变形，它与B-树的差别在于(图e为3阶B+树)：

(1)有n棵子树的节点含有n个关键字;

(2)所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接;

(3)所有非终端节点可以看成是索引部分，节点中仅含有其子树(根节点)中最大(或最小)关键字，所有B+树更像一个索引顺序表;

(4)对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。

6、字典树(trie树)

(图f)

字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。具有以下特点(图f)：

(1)根节点为空;

(2)除根节点外，每个节点包含一个字符;

(3)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

(4)每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。

7、后缀树

后缀树则是一个字符串的所有后缀组成的字典树。具体内容再前几章已讲过。

8、广义后缀树

广义后缀树是好几个字符串的的所有后缀组成的字典树，同样每个字符串的所有后缀都具有一个相同的结束符，不同字符串的结束符不同。

6.图 (Graph)

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

1.图的存储结构