数据结构中树的深度和高度（数据结构中常见的树）

数据结构中树的深度和高度（数据结构中常见的树）这算是搜索引擎里最最最简单的样例吧，记住哦，面试中经常问的。想继续往搜索引擎方面了解一些的童鞋，可以看一下 FST（Finite State Transducers，有限状态转移机），这个就不属于【树】的范畴了，我们不在这里讨论了。Trie 树是常见的字典树，通常被用于字符串查询和排序。它的形式，是在根节点的所有路径中，有序的依次存入一个对应字符。这样做，一方面可以降低海量字符串存储所占用的空间，另一方面也使得字符串得以有序的排列，同时也可以记录重复出现次数。于是，AVL 平衡二叉树诞生了。AVL 的名字，取自于作者 Adelson-Velskii 和 Landis 的首字母缩写（纯序员暗自感慨，如果是第一位作者独立发明的话，那数据结构课上就又多了个话题）。AVL 树通过在插入过程中的旋转逻辑，使得树的自身高度差严格控制在 1 之内，从而解决了退化成 list 的问题。但是，频繁的旋转增加

在我们工作中接触到的很多东西，底层的本质就是一棵树型结构，只是有前人为我们造好了屏蔽实现细节的轮子，才让我们的工作变得如此丝滑。举两个常见的例子：C 里的 std::set 和 std::map 结构，底层就是一颗树；常见的数据库存储引擎，底层也是树型结构。

那么，常用的数据结构里还有哪些常见树呢？它们又会被应用在哪里？用于解决什么样的问题？ 下面，我们就从以上几个问题入手，来介绍一下我所知道的一些 Tree 方面的知识，希望对大家有所帮助。在开始之前，首先说明，本文偏科普和综述，并不会对每种树做非常详细的介绍，也不会上什么类似红黑树旋转的代码。主要目的是让大家知道有这些内容，如果今后有需要用到的地方，自己查缺补漏即可。本人水平有限，如果有描述的错误或遗漏，也欢迎大家随时补充和交流。

BST 搜索二叉树 Binary Search Tree

树，最常见的用法，就是用于数值查找。通过在建树的时候，将大于 root 的值放到右边、小于 root 的值放到左边，即可在查询的时候，减少比较次数，实现加速查询。

但是，随着数据的插入越来越多，树的结构会造成扭曲（不平衡）。比如，往 bst 中插入一个递增数组的时候，普通的 BST 会退化成一个链表，从而严重影响查询性能。

AVL 平衡二叉树 Height-Balanced Binary Search Tree

于是，AVL 平衡二叉树诞生了。AVL 的名字，取自于作者 Adelson-Velskii 和 Landis 的首字母缩写（纯序员暗自感慨，如果是第一位作者独立发明的话，那数据结构课上就又多了个话题）。

AVL 树通过在插入过程中的旋转逻辑，使得树的自身高度差严格控制在 1 之内，从而解决了退化成 list 的问题。但是，频繁的旋转增加了树构建的成本。

RBT 红黑树 Red Black Tree

为了降低树构建时的成本，红黑树诞生了。红黑树通过将节点设定成 Red or Black，和同一条边中 Black 节点的数量相同等约束条件，在保证了树基本平衡的情况下，优化了自旋转流程。红黑树可以有效的平衡建树时的旋转次数和查找时的退化问题，并且也在实际编程中得到了广泛的应用。比如 C 中的 std::map 和 Java 里的 TreeMap 的底层就是一颗红黑树，nginx 和 epoll 源码中也有所使用。

Trie 前缀树

Trie 树是常见的字典树，通常被用于字符串查询和排序。它的形式，是在根节点的所有路径中，有序的依次存入一个对应字符。这样做，一方面可以降低海量字符串存储所占用的空间，另一方面也使得字符串得以有序的排列，同时也可以记录重复出现次数。

这算是搜索引擎里最最最简单的样例吧，记住哦，面试中经常问的。想继续往搜索引擎方面了解一些的童鞋，可以看一下 FST（Finite State Transducers，有限状态转移机），这个就不属于【树】的范畴了，我们不在这里讨论了。

Radix 压缩前缀树，也叫基数树

样子跟前面提到的 Trie 树有点相似。相比于 Trie 中一个一个往下追加的流程，Radix 在插入的时候通过分裂机制使得仅包含一条链路的字符【压缩】到一起。从而在保持原有查询、排序功能的前提下，进一步降低了数据的存储占用量。顺便说一句，Radix 树中的节点，还适合用于存放类似 .*? 这种正则匹配相关的信息。

一图胜千言，看到上面这个图，我想大家应该都懂了。Radix 树有一个常见的应用，就是文件路径查找或匹配，这一点做前后端交互的朋友应该有所涉及。

/usr/local/include/ (14KB)
/usr/local/bin/ (25KB)
/usr/study/book/ (3MB)
/usr/study/.video/ (380GB)
...

比如，我电脑中的文件夹分类吧，用 Radix 树存储的话，就比 Trie 节省了很多空间，因为 /usr，/local，/study这几个信息，明显是可以合并到一个节点中的。

Suffix tree 后缀树

上面聊到的两种字典树，都属于前缀树，其实还有后缀树。后缀树是对一个长字符串的详尽描述（注意，是一个 string 对应一棵后缀树，不是海量 string 放到一棵树上）。树的每条路径记录了一个后缀信息，后缀下标用于记录从第 x 个字符开始计算，从而简化的查询流程。主要用途有：字符串匹配，查找最长公共子串，查找最长重复子串等。

这个讲起来有点复杂，有兴趣的朋友可以去 B 站搜索：轻松掌握 suffix tree[1] ，讲的非常通俗易懂，转自doocs。