关于数据结构中树结构的相关分享

本文参考： 树结构参考文献

一、传统的数据结构中的树结构

• 树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

• 其中，讨论较多的是二叉树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

1.1 二叉查找树

• 二叉查找树定义：又称二叉排序树或二叉搜索树。二叉排序树或者是一棵空树，具有下列性质：

1. 左子树上所有结点的值均小于它的根结点的值；右子树均大于或等于它的根结点的值；有序
2. 左、右子树也分别为二叉排序树；递归有序

• 特点：
  • 二叉查找树的性质：对二叉查找树进行中序遍历，即可得到有序的数列。
  • 二叉查找树的高度决定了二叉查找树的查找效率。

1.2 平衡二叉树

• 为了让二叉搜索树的期望高度为 log2n，即使得各操作的时间复杂度为 O(log2n), 于是有了平衡二叉树(即 AVL树)。
• 定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
• 最小二叉平衡树的节点的公式如下： F(n)=F(n-1)+F(n-2)+1

1.3 平衡二叉树之红黑树

• 定义：红黑树是一种自平衡二叉查找树，其典型的用途是实现关联数组(比如 C++ 中的 STL 中的map,和 set 等关联式容器都是基于红黑树的，如 boost::multi_index 的底层实现)。
• 它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。这使得它可以适用于实时应用（real time application）。
• 红黑树还是2-3-4树的一种等同，它们的思想是一样的，只不过红黑树是2-3-4树用二叉树的形式表示的。

• 2-3-4 树把数据存储在叫做元素的单独单元中。它们组合成节点。每个节点都是下列之一：
  • 2-节点，就是说，它包含 1 个元素和 2 个儿子；
  • 3-节点，就是说，它包含 2 个元素和 3 个儿子；
  • 4-节点，就是说，它包含 3 个元素和 4 个儿子。
• 如下图(所示)：

• 红黑树的性质：
  红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。除了二叉查找树特有性质之外，红黑树还增加了如下要求:

性质1. 节点是红色或黑色，根是黑色，所有叶子都是黑色

性质2. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点，即红黑相间)，从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(简称黑高)。

• 红黑树的图例，如下：

• 性质分析：

  • 有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。但是，仅仅避免这种情况还不够，这里还要考虑某个节点到其每个叶子节点路径长度的问题。如果某些路径长度过长，那么，在对这些路径上的及诶单进行增删查操作时，效率也会大大降低。这个时候性质4和性质5用途就凸显了，有了这两个性质作为约束，即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。
  • 原因如下：
  • 当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（性质限定了不能出现两个连续的红色节点）。而性质又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。(如下图)
    

• 红黑树的自平衡调整操作：

  • 因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。
  • 此外，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转结构变更(对于插入操作是两次)。
  • 虽然插入和删除很复杂，但操作时间仍可以保持为 O(logn) 次。
  • 具体的插入、构建、删除、和调整操作(代码相关的)，可参见维基百科。
  • 红黑树调整

1.4 B 树

• B树也是一种用于查找的平衡树，但是它不是二叉树，它是多路搜索树。
• 定义： B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树即一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实现上。
  
  
• B树作为一种多路搜索树（并不是二叉的）的性质：
  • 1. 定义任意非叶子结点最多只有M个儿子；且M>2；
  • 1. 根结点的儿子数为[2, M], 非根非叶子结点的儿子数为[M/2, M]；
  • 1. 每个结点存放至少 M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
  • 1. 非叶子结点的关键字个数 = 指向儿子的指针个数-1；
  • 1. 非叶子结点的关键字有序：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  • 1. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，
  • P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  • 1. 所有叶子结点位于同一层；
       
       
• M=3 的 B 树示例图：
  
  
  
• 比起正常的平衡二叉树，B树每个节点显然能存储的数据更多，在查找数据方面也显得比较高效。
• B树创建的示意图：
  
  
  

1.5 B+树

B+树是B树的变体，也是一种多路搜索树：

1. 其定义基本与B-树相同，除了：
2. 非叶子结点的子树指针与关键字个数相同；
3. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
4. 为所有叶子结点增加一个链指针；
5. ****所有关键字都在叶子结点出现****；

• 下图为 M=3 的 B+ 树的示意图

• B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+ 树的性质：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统。

• B + 树的创建示意图：
  
  
  

• B 树和 B+ 树的异同：

  • 结构上
    • B树中关键字集合分布在整棵树中，叶节点中不包含任何关键字信息，而B+树关键字集合分布在叶子结点中，非叶节点只是叶子结点中关键字的索引；
    • B树中任何一个关键字只出现在一个结点中，而B+树中的关键字必须出现在叶节点中，也可能在非叶结点中重复出现；
  • 性能上（也即为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引？）
    • 不同于B树只适合随机检索，B+树同时支持随机检索和顺序检索；
    • B+树的磁盘读写代价更低。B+树的内部结点并没有指向关键字具体信息的指针，其内部结点比B树小，盘块能容纳的结点中关键字数量更多，可一次性将索引读入内存中可以查找的关键字也就越多，相对的，IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素。也就是说同样数据情况下，B+ 树会 B 树更加“矮胖”，因此查询效率更快。
    • B+树的查询效率更加稳定。B树搜索有可能会在非叶子结点结束，越靠近根节点的记录查找时间越短，只要找到关键字即可确定记录的存在，其性能等价于在关键字全集内做一次二分查找。而在B+树中，顺序检索比较明显，随机检索时，任何关键字的查找都必须走一条从根节点到叶节点的路，所有关键字的查找路径长度相同，导致每一个关键字的查询效率相当。
    • （数据库索引采用B+树的主要原因是，）B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起，只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

1.6 B* 树

• B* 树是 B+ 树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。
  
  

• 图示如下：
  

• B* 树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

• B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

• B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

二、字典树 ( Trie树 )

Tire树称为字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

Tire树的三个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3. 每个节点的所有子节点包含的字符都不相同。

Tire树的应用：

• 串的快速检索

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

• “串”排序

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

• 最长公共前缀

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为求公共祖先的问题。

三、决策树(利用信息论的熵依靠决策树做决策选择)

• 作为一个Coder,经常遇到敲if, else if, else,其实就就是决策树的思想。只是这么多条件，哪个条件特征先做if，哪个条件特征后做if比较优呢？怎么准确定量选择这个标准就是决策树算法的要做的事情。
• 信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：
• 单随机变量 X 的熵

• 双变量 X和Y 的联合熵
  
• 条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性。表达式如下：

• 根据决策树构建的过程，可以按照特征选择方式分成如下三种大类：

• 信息增益(又称为互信息),定义为： H(X) - H(X|Y) ,记为I(X,Y)。
• 在决策树 ID3 算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。
• ID3 的缺点：
  • 没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。
  • 取值比较多的特征比取值少的特征信息增益大。
  • ID3算法对于缺失值的情况没有做考虑等
  • 没有考虑过拟合的问题
• 于是提出了 C4.5
  • 对于使用信息增益作为标准容易偏向于取值较多的特征的问题。引入一个信息增益率的变量Ir(X,Y)，它是信息增益和特征熵的比值。表达式如下：

• C4.5 的缺点：
  • 决策树算法非常容易过拟合
  • C4.5生成的是多叉树，在计算机科学中二叉树往往运算效率更高。
  • C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
  • C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。是否可以通过适当的降低结果准确性来简化模型的运算强度。
• 前面两种方式都是基于信息论的熵模型，有耗时的计算问题，CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。(其实就是加了一个负号，对比信息熵的定义)
• 在分类问题中，假设有K个类别，第k个类别的概率为pk, 则基尼系数的表达式为：

• 如果是二类分类问题，概率是p，则基尼系数简化为：

四、梅克尔帕特里夏树( Merkle Patricia Tree, MPT)

• MPT: 基于加密学的，自校验防篡改的数据结构，用来存储键值对关系。MPT是确定的。确定性是指同样内容的键值，将被保证找到同样的结果，有同样的根哈希。关于效率方面，对树的插入，查找，删除的时间复杂度控制在O(log(n))。
• 前言：基数树（Radix Tree）
• 在一个标准的基数树里，要存储的数据，按下述所述：

[i0, i1, ... iN, value]

• 其中的i0到iN的表示一般是二进制或十六进制的格式的字母符号。value表示的是树节点中存储的最终值。每一个i0到iN槽位的值，要么是NULL，要么是指向另一个节点的指针（在当前这个场景中，存储的是其它节点的哈希值）。这样我们就实现了一个简单的键值对存储。举个例子来说，如果你想在这个基数树中，找到键dog所对应的值。首先需要将dog转换为比如ascii码值（十六进制表示是646f67）。然后按字母序形成一个逐层向下的树。沿着字母组成的路径，在树的底部叶节点上，即找到dog对应的值。具体来说，首先找到存储这个键值对数据的根节点，找到下一层的第6个节点，然后再往下一层，找到节点4，然后一层一层往下找，直到完成了路径 root -> 6 -> 4 -> 6 -> f -> 6 -> 7。这样你将最终找到值的对应节点。
• 基数树的缺点:
  • 基数树另一个主要的缺陷是低效。即使你只想存一个键值对，但其中的键长度有几百字符长，那么每个字符的那个层级你都需要大量的额外空间。每次查找和删除都会有上百个步骤。在这里我们引入Patricia树来解决这个问题。
• Patricia 树
• Patricia树，或称Patricia trie，或 crit bit tree，压缩前缀树，是一种更节省空间的Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。

• Merkle 树
• Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。
• Merkle Tree 由 Hash List演化而来：
• 在点对点网络中作数据传输的时候，会同时从多个机器上下载数据，而且很多机器可以认为是不稳定或者不可信的。为了校验数据的完整性，更好的办法是把大的文件分割成小的数据块（例如，把分割成2K为单位的数据块）。这样的好处是，如果小块数据在传输过程中损坏了，那么只要重新下载这一快数据就行了，不用重新下载整个文件。
  怎么确定小的数据块没有损坏哪？只需要为每个数据块做Hash。BT下载的时候，在下载到真正数据之前，我们会先下载一个Hash列表。那么问题又来了，怎么确定这个Hash列表本身是正确的哪？答案是把每个小块数据的Hash值拼到一起，然后对这个长字符串在作一次Hash运算，这样就得到Hash列表的根Hash(Top Hash or Root Hash)。下载数据的时候，首先从可信的数据源得到正确的根Hash，就可以用它来校验Hash列表了，然后通过校验后的Hash列表校验数据块。

• Merkle Tree 可以看做Hash List的泛化（Hash List可以看作一种特殊的Merkle Tree，即树高为2的多叉Merkle Tree。
• 在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。

• 在p2p网络下载网络之前，先从可信的源获得文件的Merkle Tree树根。一旦获得了树根，就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接受到的MerkleTree。如果Merkle Tree是损坏的或者虚假的，就从其他源获得另一个Merkle Tree，直到获得一个与可信树根匹配的MerkleTree。
• Merkle Tree和HashList的主要区别是，可以直接下载并立即验证 Merkle Tree的一个分支。因为可以将文件切分成小的数据块，这样如果有一块数据损坏，仅仅重新下载这个数据块就行了。如果文件非常大，那么Merkle tree和Hash list都很到，但是Merkle tree可以一次下载一个分支，然后立即验证这个分支，如果分支验证通过，就可以下载数据了。而Hash list只有下载整个hash list才能验证。
• MPT（Merkle Patricia Tree）树****
• MPT（Merkle Patricia Tree）就是这两者混合的数据结构。
• MPT树中的节点包括空节点、叶子节点、扩展节点和分支节点:
  • 空节点，简单的表示空，在代码中是一个空串。
  • 叶子节点（leaf），表示为[key,value]的一个键值对，其中key是key的一种特殊十六进制编码，value是value的RLP编码。
  • 扩展节点（extension），也是[key，value]的一个键值对，但是这里的value是其他节点的hash值，这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。
  • 分支节点（branch），因为MPT树中的key被编码成一种特殊的16进制的表示，再加上最后的value，所以分支节点是一个长度为17的list，前16个元素对应着key中的16个可能的十六进制字符，如果有一个[key,value]对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。
  • MPT 树中另一个重要的概念是十六进制前缀(hex-prefix, HP)编码，用来对key进行编码。因为字母表是16进制的，所以每个节点可能有16个孩子。因为有两种[key,value]节点(叶节点和扩展节点)，引进一种特殊的终止符标识来标识key所对应的是值是真实的值，还是其他节点的hash。如果终止符标记被打开，那么key对应的是叶节点，对应的值是真实的value。如果终止符标记被关闭，那么值就是用于在数据块中查询对应的节点的hash。