# 各种树的复杂度和原理 * * * * [二叉树：二叉排序树、满二叉树、完全二叉树、平衡二叉树](#二叉树：二叉排序树、满二叉树、完全二叉树、平衡二叉树) * [B树：平衡多路搜索树B树（B-tree）、B+Tree、红黑树](#B树：平衡多路搜索树B树、B+Tree、红黑树) * [Trie树（Prefix Tree）介绍](#Trie树（Prefix-Tree）介绍) *** ## 二叉树：二叉排序树、满二叉树、完全二叉树、平衡二叉树 二叉树： 二叉排序树\ 满二叉树、完全二叉树、平衡二叉树 树： 二叉树（Binary Tree）：是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。 二叉树是树的一种特殊情形，是一种更简单而且应用更加广泛的树。 满二叉树：满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。 一棵深度为k，且有2^（k-1）个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。 完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。 除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。 具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2^（k-1）个叶子结点，至多有2^k-1个结点。 平衡二叉树：平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 前中后指的是根节点的位置，都是先左再右： 前序遍历：是先访问根，再访问左子树，然后访问右子树\ 后序遍历：是先访问左子树，再访问右子树，然后访问根\ 中序遍历：是先访问左子树，再访问根，然后访问右子树\ 层次遍历：即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同） 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。 二叉排序树，又称为二叉查找树。二叉排序树或者是一棵空树，或者是具有以下性质的二叉树：若其左子树不为空，则左子树上的所有节点的值均小于它的根结点的值；若其右子树不为空，则右子树上的所有节点的值均大于它的根结点的值；左右子树又分别是二叉排序树。 一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； （4）没有键值相等的结点。 二叉排序树： *** ## B树：平衡多路搜索树B树、B+Tree、红黑树 B树：平衡多路搜索树B树（B-tree）、B+Tree、红黑树 1、阶的概念 对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。 即遍观整棵树，子节点最多的个数是m，那么这棵树就是m阶树。 2、树的度 树的度就是树的高度，即树的层数。 B-树就是B树 英文名字叫做B-tree，中间的短线是英文连接符，只是翻译的时候将短线翻译成了减号。 全称Balance-tree(平衡多路查找树)，平衡的意思是左边和右边分布均匀。多路的意思是相对于二叉树而言的，二叉树就是二路查找树，查找时只有两条路，而B-tree有多条路，即父节点有多个子节点。 B-树用途 使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。这个数据结构一般用于数据库的索引，综合效率较高。 B+树的定义 B+树是B树的一种变形，它更适合实际应用中操作系统的文件索引和数据库索引。定义如下：（为和大多资料保持一致，这里使用阶数mmm来定义B+树，而不像之前的B树中，使用的是最小度ttt来定义） 根据B+树的结构，我们可以发现B+树相比于B树，在文件系统，数据库系统当中，更有优势，原因如下： 1、B+树的磁盘读写代价更低 B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。 2、B+树的查询效率更加稳定 由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。 3、B+树更有利于对数据库的扫描 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性能。 红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。 参考 *** ## Trie树（Prefix Tree）介绍 一、Trie树（Prefix Tree）介绍 Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。 Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）。 二、Trie树的优缺点 Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。 优点 1、插入和查询的效率很高，都为O(m)O(m)，其中 mm 是待插入/查询的字符串的长度。 关于查询，会有人说 hash 表时间复杂度是O(1)O(1)不是更快？但是，哈希搜索的效率通常取决于 hash 函数的好坏，若一个坏的 hash 函数导致很多的冲突，效率并不一定比Trie树高。 2、Trie树中不同的关键字不会产生冲突。 3、Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。 4、Trie树不用求 hash 值，对短字符串有更快的速度。通常，求hash值也是需要遍历字符串的。 5、Trie树可以对关键字按字典序排序。 缺点 1、当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。 2、空间消耗比较大。 三、Trie树的应用 1、字符串检索 2、词频统计 3、字符串排序 4、前缀匹配 5、作为其他数据结构和算法的辅助结构 1、字符串检索 检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较： 如果沿路比较，发现不同的字符，则表示该字符串在集合中不存在。 如果所有的字符全部比较完并且全部相同，还需判断最后一个节点的标志位（标记该节点是否代表一个关键字）。 `struct trie_node { bool isKey; // 标记该节点是否代表一个关键字 trie_node *children[26]; // 各个子节点 };` 2、词频统计 Trie树常被搜索引擎系统用于文本词频统计 。 `struct trie_node { int count; // 记录该节点代表的单词的个数 trie_node *children[26]; // 各个子节点 };` 思路：为了实现词频统计，我们修改了节点结构，用一个整型变量count来计数。对每一个关键字执行插入操作，若已存在，计数加1，若不存在，插入后count置1。 注意：第一、第二种应用也都可以用 hash table 来做。 3、字符串排序 Trie树可以对大量字符串按字典序进行排序，思路也很简单：遍历一次所有关键字，将它们全部插入trie树，树的每个结点的所有儿子很显然地按照字母表排序，然后先序遍历输出Trie树中所有关键字即可。 4、前缀匹配 例如：找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树，然后输出以a->b->开头的路径上的关键字即可。 trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。 5、作为其他数据结构和算法的辅助结构 如后缀树，AC自动机等。 参考 ***