神奇的树

发表于 | 分类于 | 阅读次数
字数统计 6673 | 阅读时长 33

    上次谈到了树，今天我们就来详细探讨一下各种树的特性。当然，此树非深山老林或是大街上绿油油的树，而是数据结构中非常重要的一部分。内容包括：二叉树(Binary Tree)、哈弗曼树(Huffman Tree)、查找树(Search Tree)、字典树(Trie Tree)

树的定义(Define)

    我们先来看看书本上对树的定义：

树（Tree）是$n(n\geq0)$个结点的有限集，$n=0$时称为空树。对于任意一棵非空树有：

  1. 有且仅有一个特定的称为根（Root）的结点；
  2. 当$n＞1$时，其余结点可分为$m(m＞0)$个互不相交的有限集$T_1$、$T_2$、……、$T_m$，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

还有一些节点的定义也了解一下：

  1. 根节点：也称树根，可任意选定一个节点作为树的根节点，非空树中有且只有一个，这个节点只有子节点没有父节点。
  2. 内部节点：非根非叶子节点，既有子节点也有父节点。
  3. 叶节点（终端节点）：树的末梢节点，只有父节点，没有子节点。
  4. 节点的度：理论上度是有入度和出度两个概念的，但是对于树来说我们说一个节点的度就是说他的出度，也就是子节点数量。这里另外还补充一个概念，树的度指的是树中度最大的节点的度。
  5. 节点关系：
    • 父节点（双亲节点）：一个节点具有孩子节点，相对于孩子节点来说他是父节点
    • 祖先节点：一个节点的父节点到根节点这一条路径上的所有节点都是这个节点的祖先节点
    • 子节点（孩子节点）：一个节点具有父节点，相对于父节点来说他是子节点
    • 兄弟节点：同一个父节点下的所有子节点互为兄弟节点。
  6. 路径与路径长度：从树中一个结点到另一个结点之间的分支构成两个结点的路径，路径上的分支数目叫做路径长度。树的路径长度是从树根到每一个结点的路径长度之和。

    通俗地说，就是树可以为空，空树是存在的，这个要注意和图区别开来，图是没有空图的说法的。然后每棵树都有且仅有一个根，然后往下呢又会分叉，一直分叉到叶子节点。下面放一张图来直观理解一下。     对于树的一些特殊性质以及节点计算不要死记硬背，要学会自己推理，记得话是记不过来的还会记错。

二叉树(Binary Tree)

二叉树定义

    二叉树是树的一种特殊情况，对任意一颗二叉树有：

  1. 每个结点最多有两颗子树，结点的度最大为2。
  2. 左子树和右子树是有顺序的，次序不能颠倒。
  3. 即使某结点只有一个子树，也要区分左右子树。
特殊二叉树
  • 斜树

    所有节点都只有左子树或者右子树的二叉树，了解就好，很少用到。

  • 完全二叉树

     对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树肯定是完全二叉树，但反过来不一定成立。 其性质为：

  1. 叶子结点只能出现在最下一层（满二叉树继承而来）
  2. 最下层叶子结点一定集中在左 部连续位置。
  3. 倒数第二层，如有叶子节点，一定出现在右部连续位置。
  4. 同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。

  • 满二叉树

    所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上。这样的树每一层节点都是满的，很好看。 其性质为：

  1. 叶子只能出现在最下一层。
  2. 非叶子结点度一定是2.
  3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

通过下面这张图来加深一下了解与区分：

遍历方法

    从树的根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问仅且一次，按照从左到右的方式共有4种常见遍历方法。

  • 层序遍历 基本思想：先访问根结点，再从上往下依次遍历每一层的节点，为了保证层序的性质，需要一个队列存储当前节点的子节点。 伪代码： 
    1
    2
    3
    4
    5
    6
      while Q:
      now = Q.pop()
      visit(now)
      if now.has_child:
          push(now.l_child)
          push(now.r_child)
  • 前序遍历 基本思想：先访问父节点，再访问左节点，再访问右节点。 伪代码： 
    1
    2
    3
      print(root.value)
  visit(root.left)
  visit(root.right)
  • 中序遍历 基本思想：先访问左节点，再访问父节点，再访问右节点。 伪代码： 
    1
    2
    3
      visit(root.left)
  print(root.value)
  visit(root.right)
  • 后序遍历 基本思想：先访问左节点，再访问右节点，再访问父节点。 伪代码： 
    1
    2
    3
      visit(root.right)
  visit(root.left)
  print(root.value)

        建议自己代码实现一遍，加深理解。同时自己在纸上推导一下是否正确，如果理解不到位很容易弄混的。下面的线索二叉树就是基于前面这几种遍历得来的。而且由于中序的性质，可以确定其左右子树的位置，因此通过中序和前序（后序）两种遍历可以唯一确定一颗二叉树，这个也自己纸上推导一遍吧。

线索二叉树

    基于上面的遍历我们知道了遍历之后每个节点有他的前驱也有他的后继，而对于有的节点来说，他可能并没有左孩子或者右孩子，这时我们可以把这些空指针利用起来，左孩子指向其前驱，右孩子指向其后继，这样就很很方便地获取节点的前驱后继而不用整个再次遍历一遍了。因此又可分为基于遍历顺序的线索二叉树。同时，为了区分其左右孩子，我们引入两个tag来标记到底指向孩子还是指向前驱后继，其结构定义如下。

         
lchild ltag data rtag rchild 
1
2
3
4
5
6
7
struct Node{
    Node *lchild;
    bool ltag;
    T data;
    bool rtag;
    Node *rchild;
}

哈弗曼树(Huffman Tree)

    讲哈弗曼树之前，我们有必要了解一下哈弗曼编码。在计算机数据处理中，哈弗曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的，在早期的数据通信中起到了重要作用。同时，这种编码在查找中也能够具有一定的效率提升。
    哈夫曼树，又称最优树，是一类带权路径长度最短的树。在压缩数据，提升查找效率上有着重要作用，下面我们举个例子。给出一组字母在通信中出现的频率：

字母 A B C D E F
次数 27 8 15 15 30 5
常规编码 000 001 010 011 100 101
哈弗曼编码 01 1001 101 00 11 1000

    如果按照以上常规方法进行编码，那么对于6个数据字符则每个都需要$log_2 6=3$位编码，共需要位数： \((27+8+15+15+30+5)*3=300\) 但是采用哈弗曼编码我们只需要传输位数： \((27*2+8*4+15*3+15*2+30*2+5*4)=241\) 从上面的数据明显可以看出效率的提升，下面我们看下编码方式的图。     自己手动编码也简单，对于二叉哈弗曼（对，还有多叉），每次选择两个频率最小的数据，作为兄弟节点合成一个父节点，父节点的值为两个子节点的和，然后删除原来数据中拿出的两个数据，把这个新的节点数据放回原来的数据组里面，接着又选两个，直到取完所有数据。然后进行编码，左节点编码为0，右节点编码为1，就可以得到所有的编码数据了。

查找树(Search Tree)

    由于树的结构特性，如果我们按照一定的序列规律来建立一棵树，那么这棵树就可以具有查找功能，下面是一些按照特殊规定来进行查找的树。

BS树 (二叉查找树)

    二叉查找树又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

  1. 若左子树不空，则左子树上所有结点的值均小于成效它的根结点的值；
  2. 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
  3. 左、右子树也分别为二叉排序树；
  4. 没有键值相等的节点。 对二叉查找树进行中序遍历，可得到有序的数列，它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。所以，二叉排序树就是按照左小右大（左大右小也可以）的规律建立的树，这样就可以进行查找，下面我们来看一幅图加深直观了解。

AVL树（平衡二叉查找树）

    由于BS树最差情况会退化到O(n)复杂度，因此AVL的出现就是为了优化他。在AVL中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
    对于AVL树来说，旋转这块刚学可能有点糊，由于AVL树始终要保持左右子树高度差不超过1，因此当树不平衡时就要通过旋转来保持平衡，就我理解的情况来介绍一下AVL的四种旋转。 首先，定义某个子树根节点上的平衡因子为： \(平衡因子 = 左子树高度 - 右子树高度\) 那么出现不平衡的情况会有四种（注意这个孩子节点是相对于哪个节点的）：

  • LL：左孩子的左孩子插入左节点导致不平衡
  • RR：右孩子的右孩子插入右节点导致不平衡
  • LR：左孩子的左孩子插入右节点导致不平衡
  • RL：右孩子的左孩子插入左节点导致不平衡 放张图片直观感受一下：

我们从导致不平衡的插入节点开始往上找到第一个不平衡的位置，然后进行操作：

  • LL旋转：左孩子直接往上提
  • RR旋转：右孩子直接往上提
  • LR旋转：左孩子先左旋，保持平衡因子符号统一成正的，然后像LL一样往上提，即为右旋
  • RL旋转：右孩子先右旋，保持平衡因子符号统一成负的，然后像RR一样往上提，即为左旋 （注：如果插入的孩子节点还有兄弟节点那么把兄弟节点变成父节点的兄弟节点）
红黑树（自平衡二叉查找树）

    红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制的一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色（叶子是NIL节点）。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

放张图片直观感受一下：

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

    我们首先以二叉查找树的方法增加节点并标记它为红色。如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的（违背性质5）。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。下面要进行什么操作取决于其他临近节点的颜色。

B树（多路平衡查找树）

    这个，其实B树是B-Tree，但是不要念成B-树了。而且，他其实是个K叉树。
    B树的定义：B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。
    在B树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。 性质：

  1. 定义任意非叶子结点最多只有M个儿子；且M>2；
  2. 根结点的儿子数为[2, M]；
  3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
  5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
  6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  8. 所有叶子结点位于同一层；

放张动图感受下：

B+树

    B+树是B树的改版，基本性质相同，有些细微区别，最大的区别就是节点不存储实际数据，都存放在叶子节点中，叶子节点也只存放指针指向实际数据。这样的话当数据很多的时候，查找不需要调入很大一堆数据到内存，直接把树调入进来是消耗内存很小的。
    其区别于B树的性质如下：

  1. 非叶子节点的子树指针与关键字个数相同；
  2. 非叶子节点的子树指针p[i],指向关键字值属于[k[i],k[i+1]]的子树.(B树是开区间,也就是说B树不允许关键字重复,B+树允许重复)；
  3. 为所有叶子节点增加一个链指针；
  4. 所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的)；
  5. 非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层；
  6. 更适合于文件系统；

其优点大概分三种：

  1. B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
  2. B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
  3. 由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

    但是面试的时候我把这些说出来之后面试官还是问我为什么选择B+树而不选B树，比如Mysql里面还会有一些其他性质的查询，我。。。由于当时被他的气场震慑到，真的尴尬。你要是查什么开头或者结尾，用字典树做索引不就ok了？联合查询用笛卡尔啊，一颗B+树我刚毕业还能玩出花来？然后被无情嘲讽。唉，还是好好学习吧。不说了，放张动图感受下：

B*树

    B* 树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。其定义了非叶子结点关键字个数至少为(2/3)* M，即块的最低使用率为2/3（代替B+ 树的1/2)。
    B+ 树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
    B* 树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
    所以，B* 树分配新结点的概率比B+ 树要低，空间使用率更高。 放张图感受下：

哈希树(Hash Tree)

    在各种数据结构（线性表、树等）中，记录在结构中的相对位置是随机的。因此在机构中查找记录的时需要进行一系列和关键字的比较。这一类的查找方法建立在“比较”的基础上。查找的效率依赖于查找过程中所进行的比较次数。常见的基于比较的树查找算法的效率都将随着数据记录数的增长而下降。仅仅是有的比较慢（时间复杂度为O(n)），有的比较快（时间复杂度是O(logn)）而已。这些查找算法的平均查找长度是在一种比较理想的情况下获得的。在实际应用当中，对数据结构中数据的频繁增加和删除将不断地改变着数据的结构。这些操作将可能导致某些数据结构退化为链表结构，那么其性能必然将下降。
    理想的情况是希望不经过任何比较，一次存取便能得到所查的记录，那就必须在记的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和一个唯一的存储位置相对应。哈希树(HashTree)算法就是要提供一种在理论上和实际应用中均能有效地处理冲突的方法。一般的哈希(Hash)算法都是O(1)的，而且基本是以空间换时间。这很容易导致对存储空间无限制的需求。哈希树(HashTree)算法在实际操作中使用了一些技巧使得对空间的需求控制在一定范围内。即空间需求仅和所需要存储的对象个数有关，不会无限制地“膨胀”下去。

【质数分辨定理】 简单地说就是：n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。

例如：

从2起的连续质数，连续10个质数就可以分辨大约M(10) =23571113171923*29= 6464693230 个数，已经超过计算机中常用整数（32bit）的表达范围。连续100个质数就可以分辨大约M(100) = 4.711930 乘以10的219次方。 而按照目前的CPU水平，100次取余的整数除法操作几乎不算什么难事。

定义数据结构如下：

1
2
3
4
5
6
7
struct Node
{
    HashType           value;    //存储hash值
    char*               data;    //存储数据
    bool                used;    //表示此位是否被使用
    struct Node* subNodes[i];    //表示节点的第i个子节点的地址。
} ;

图解：

字典树(Trie Tree)

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

I have a pen ,I have a apple. en~apple pen

请统计里面每个单词出现的次数，并且我问你某个前缀的时候你得告诉我这个前缀的单词有哪些，出现了多少次，不可能直接扫描一遍又一遍吧，效率太低。那么就可以请出我们的字典树了，定义结构如下。

1
2
3
4
5
6
7
8
struct TrieNode // 字典树节点
{
    int num;             // 统计当前结尾的单词有多少个
    TrieNode next[26];   // 所有的子节点
    bool isEnd;          // 是不是最后一个节点
    char* val;           // 节点的值

}

图解如下：

目前我接触过的树就这些了，以后接触到再更新。这次也只是浅谈，具体一些性质和推导还是要多搜索一下，做具体了解，最好自己纸上推导一遍再代码实现一遍才能加深理解。