大家好，我是不会写代码的纯序员——Chunel Feng。刷leetcode的童鞋，肯定写过二叉树的遍历、递归、查询等逻辑，面试的时候6的飞起，人均ssp。但很多童鞋也会有一种感觉：这些东西只能应付面试，不实用，工作了好好几年了，根本没用过。
其实，我们在工作中接触到的很多东西，底层的本质就是一颗树型结构，只是有很多大神为我们造好了屏蔽了实现细节的轮子，才让我们的工作变得如此丝滑。说个大家应该都知道的例子：C++里的set和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树有一个常见的应用，就是文件路径查找或匹配，这一点做前后端交互的朋友应该有所涉及。
/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 ，讲的非常通俗易懂，墙裂推荐。
| 本章小节 |
本章是这个系列的第一篇内容，主要是聊了我写这个系列的文章的出发点和目的，也简单介绍了几种类型的树，并梳理了他们的使用场景和异同。都比较常见的，希望大家能够了解、熟悉、精通。
在这个系列接下来的几篇文章中，我们还会继续给大家介绍一些常见的树结构，比如lsm树，kd树、哈夫曼树等等。也希望对类似话题感兴趣的朋友，可以加我微信，一起讨论相关的内容。
嗯嗯，如果能顺便给我讲两个段子，那就更好了哦。
[2021.11.18 by Chunel]
个人信息
微信: ChunelFeng
邮箱: chunel@foxmail.com
个人网站：www.chunel.cn
github地址: https://github.com/ChunelFeng
