柠檬哥整理了50本盘算机相关的电子书，关注民众号「后端技术学堂」，回复「1024」我发给你，回复「进群」拉你进百人读者技术交流群，一起学习配合发展。数据结构这门课程是盘算机相关专业的基础课，数据结构指的是数据在盘算机中的存储、组织方式。我们在学习数据结构时候，会遇到种种各样的基础数据结构，好比客栈、行列、数组、链表、树...这些基本的数据结构类型有各自的特点，差别数据结构适用于解决差别场景下的问题。

树形结构相比数组、链表、客栈这些数据结构来说，稍微庞大一点点，但树形结构可以用于解决许多实际问题，因为现实世界事物之间的关系往往不是线性关联的，而「树」恰好适合形貌这种非线性关系。今天就带大家一起学习下，数据结构中的种种「树」，这也是面试中经常考察的内容，手撕二叉树是通例套路，对候选人也很有区分度，学完这篇文章，相信大家都市心中有「树」了。从树说起什么是树？现实中的树大家都见过，在数据结构中也有树，此树非彼树，不外数据结构的树和现实中的树在形态上确实有点相像。

树是非线性的数据结构，用来模拟具有树状结构性质的数据荟萃，它是由n个有限节点组成的具有条理关系的荟萃。在数据结构中树是非线性数据结构，那我们先来相识下，什么是线性与非线性数据结构？线性结构「线性结构」是一个有序数据元素的荟萃。其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的，常用的线性结构有：线性表，栈，行列，双端行列，数组，串。

可以想象，所谓的线性结构数据组织形式，就像一条线段一样笔直，元素之间首尾相接。好比现实中的火车进站、食堂打饭排队的行列。

非线性结构简而言之，线性结构的对立面就是「非线性结构」。树线性结构中节点是首位相接一对一关系，在树结构中节点之间不再是简朴的一对一关系，而是较为庞大的一对多的关系，一个节点可以与多个节点发生关联，树是一种条理化的数据组织形式，树在现实中是可以找到例子的，好比现实中的族谱，亲戚之间的关系是条理关联的树形关系。数据结构中的「树」的名字由来，是因为如果把节点之间的关系直观展示出来，由于长得和现实世界中的树很像，由此得名。如图：树的关键观点人们对树形结构的研究比力深入，为了利便研究树的种种性质，抽象出了一些树相关的观点，以便清晰简介的形貌一颗树。

下面几个基础观点必须相识，否则你当你刷LeetCode树相关题目时候，或者面试官向你形貌问题时，你会连题目都看不懂事什么意思。先来上一个图解，下面的术语和观点对照着看，更容易明白。

❝什么是节点的度？❞度很好明白，直观来说，数一下节点有几个分叉就说这个节点的度是几多。❝什么是根节点？❞在一颗树形结构中，最顶层的谁人节点就是根节点了，所有的子节点都源自它发散开来。❝什么是父节点？❞树的父子关系和现实中很相似，若一个节点含有子节点，则这个节点称为其子节点的父节点。❝什么是叶子节点？❞直观来看叶子节点都位于树的最底层，就是没有分叉的节点，严格的界说是度为 0 的节点叫叶子节点。

❝什么是节点的高度？❞高度是从叶子节点开始「自底向上」逐层累加的路径长度，树叶的高度为 0（有些书上也说是 0，不用纠结）❝什么是节点的深度？❞深度是从根节点开始「自顶向下」逐层累加的路径长度，根的深度为1（有些书上也说是 0，问题不大）小技巧：高度和深度，一个从下往上数，一个从上往下数。树的特点树形数据结构，具有以下的结构特点：每个节点都只有有限个子节点或无子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；树内里没有环路，意思就是从一个节点出发，除非往返，否则不能回到起点。二叉树有了前面「树」的基础铺垫，二叉树是一种特殊的树，还记的上面我们学过「节点的度」吗？二叉树中每个节点的度不大于 2 ，即它的每个节点最多只有两个分支，通常称二叉树节点的左右两个分支为左右子树。

二叉树是许多其他树型结构的基础结构，好比下面要讲的 AVL 树、二叉查找树，他们都是由二叉树增加一些约束条件进化而来。三种遍历方式二叉树的遍历就是逐个会见二叉树节点的数据，常见的二叉树遍历方式有三种，划分是前中后序遍历，初学者分不清这几个顺序的差异。「有个简朴的影象方式，这里的「前中后」都是对于根节点而言」。先会见根节点后会见左右子树的遍历方式是前序遍历，先会见左右子树最后会见根节点的遍历方式是后序遍历，先会见左子树再会见根节点最后会见右子树的遍历方式是中序遍历，下面详细说明：前序遍历遍历顺序是根节点->左子树->右子树遍历的获得的序列是：1 2 4 5 3 6 7中序遍历遍历顺序是左子树->根节点->右子树遍历的获得的序列是：4 2 5 1 6 3 7后序遍历遍历顺序是左子树->右子树->根节点遍历的获得的序列是：4 5 2 6 7 3 1二叉查找树由于最基础的二叉树节点是无序的，想象一下如果在二叉树中查找一个数据，最坏情况可能要要遍历整个二叉树，这样的查找效率是很是低下的。

由于基础二叉树倒霉于数据的查找和插入，因此我们有须要对二叉树中的数据举行排序，所以就有了「二叉查找树」，可以说这种树是为了查找而生的二叉树，有时也称它为「二叉排序树」，都是同一种结构，只是换了个叫法。查找二叉树明白了也不难，简朴来说就是二叉树上所有节点的，左子树上的节点都小于根节点，右子树上所有节点的值都大于根节点。这样的结构设计，使得查找目的节点很是利便，可以通过关键字和当前节点的对比，很快就能知道目的节点在该节点的左子树还是右子树上，利便在树中搜索目的节点。

如果对排序二叉树执行中序遍历，因为中序遍历的顺序是：左子树->根节点->右子树，最终可以获得一个节点值的有序列表。举个栗子：对上图的排序二叉树执行中序遍历，我们可以获得一个有序序列：1 2 3 4 5 6 7查询效率二叉查找树的查询庞大度取决于目的节点的深度，因此当节点的深度比力大时，最坏的查询效率是O(n)，其中n是树中的节点个数。实际应用中有许多革新版的二叉查找树，目的是尽可能使得每个节点的深度不要过深，从而提高查询效率。

好比AVL树和红黑树，可以将最坏效率降低至O(log n)，下面我们就来看下这两种革新的二叉树。AVL树AVL 也叫平衡二叉查找树。AVL 这个名字的由来，是它的两个发现者G. M. Adelson-Velsky 和 Evgenii Landis 的缩写，AVL最初是他们两人在1962 年的论文「An algorithm for the organization of information」中提出来一种数据结构。界说AVL 树是一种平衡二叉查找树，二叉查找树我们已经知道，那平衡是什么意思呢？我们举个天平的例子，天平两头的重量要差不多才气平衡，否则就会泛起向一边倾斜的情况。

把这个观点迁移到二叉树中来，根节点看作是天平的中点，左子树的高度放在天平左边，右子树的高度放在天平右边，当左右子树的高度相差「不是特别多」，称为是平衡的二叉树。AVL树有更严格的界说：在二叉查找树中，任一节点对应的两棵子树的最大高度差为 1，这样的二叉查找树称为平衡二叉树。其中左右子树的高度差也有个专业的叫法：平衡因子。AVL树的旋转一旦由于插入或删除导致左右子树的高度差大于1，此时就需要旋转某些节点调整树高度，使其再次到达平衡状态，这个历程称为旋转再平衡。

保持树平衡的目的是可以控制查找、插入和删除在平均和最坏情况下的时间庞大度都是O(log n)，相比普通二叉树最坏情况的时间庞大度是 O(n) ，AVL树把最坏情况的庞大度控制在可接受规模，很是合适对算法执行时间敏感类的应用。B树B树是鲁道夫·拜尔（Rudolf Bayer）1972年在波音研究实验室（Boeing Research Labs）事情时发现的，关于B树名字的由来至今是个未解之谜，有人猜是Bayer的首字母，也有人说是波音实验室（Boeing Research Labs）的Boeing首字母缩写，虽然B树这个名字泉源扑朔迷离，我们心里也没点 B 树，但不影响今天我们来学习它。界说一个 m 阶的B树是一个有以下属性的树每一个节点最多有 m 个子节点每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点，⌈m/2⌉表现向上取整。

如果根节点不是叶子节点，那么它至少有两个子节点有 k 个子节点的非叶子节点拥有 k − 1 个键所有的叶子节点都在同一层如果之前不相识，相信第一眼看完界说肯定是蒙圈，不外多看几遍好好明白一下就好了，画个图例，对照着看看：图3特点B树是所有节点的平衡因子均即是0的多路查找树（AVL树是平衡因子不大于 1 的二路查找树）。B 树节点可以生存多个数据，使得 B 树可以不用像 AVL 树那样为了保持平衡频繁的旋转节点。B树的多路的特性，降低了树的高度，所以B树相比于平衡二叉树显得矮胖许多。B树很是适合生存在磁盘中的数据读取，因为每次读取都市有一次磁盘IO，高度降低淘汰了磁盘IO的次数。

B树常用于实现数据库索引，典型的实现，MongoDB索引用B树实现，MySQL的Innodb 存储引擎用B+树存放索引。说到B树不得不提起它的好兄弟B+树，不外这里不展开细说，只需知道，B+树是对B树的革新，数据都放在叶子节点，非叶子节点只存数据索引。红黑树红黑树也是一种特殊的「二叉查找树」。

到现在为止我们学习的 AVL 树和即将学习的红黑树都是二叉查找树的变体，可见二叉查找树真的是很是重要基础二叉树，如果忘了它的界说可以先转头看看。特点红黑树中每个结点都被标志了红黑属性，红黑树除了有普通的「二叉查找树」特性之外，另有以下的特征：节点是红色或玄色。根是玄色。所有叶子都是玄色（叶子是NIL节点）。

每个红色节点必须有两个玄色的子节点。（从每个叶子到根的所有路径上不能有两个一连的红色节点。

）从任一节点到其每个叶子的所有简朴路径都包罗相同数目的玄色节点。这些性质有兴趣可以自行研究，不外，现在你只需要知道，这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

红黑树而节点的路径长度决议着对节点的查询效率，这样我们确保了，最坏情况下的查找、插入、删除操作的时间庞大度不凌驾O(log n)，而且有较高的插入和删除效率。应用场景红黑树在实际应用中比力广泛，有许多已经落地的实践，好比学习C++的同学都知道会接触到 STL 尺度库，而STL容器中的map、set、multiset、multimap 底层实现都是基于红黑树。

再好比，Linux内核中也有红黑树的实现，Linux系统在实现EXT3文件系统、虚拟内存治理系统，都有使用到红黑树这种数据结构。Linux内核中的红黑树界说在内核文件如下的位置：如果找不到，可以 find / -name rbtree.h 搜索一下即可，有兴趣可以打开文件看下详细实现。

红黑树 VS 平衡二叉树（AVL树）插入和删除操作，一般认为红黑树的删除和插入会比 AVL 树更快。因为，红黑树不像 AVL 树那样严格的要求平衡因子小于即是1，这就淘汰了为了到达平衡而举行的旋转操作次数，可以说是牺牲严格平衡性来换取更快的插入和删除时间。红黑树不要求有不严格的平衡性控制，可是红黑树的特点，使得任何不平衡都市在三次旋转之内解决。而 AVL 树如果不平衡，并不会控制旋转操作次数，旋转直到平衡为止。

查找操作，AVL树的效率更高。因为 AVL 树设计比红黑树越发平衡，不会泛起平衡因子凌驾 1 的情况，淘汰了树的平均搜索长度。Trie树（前缀树或字典树）Trie泉源于单词 retrieve（检索），Trie树也称为前缀树或字典树。

使用字符串前缀来查找指定的字符串，缩短查找时间提高查询效率，主要用于字符串的快速查找和匹配。为什么要称其为字典树呢？因为Trie树的功效就像字典一样，想象一下查英文字典，我们会凭据首字母找到对应的页码，接着凭据第二、第三...个单词，逐步查找到目的单词，Trie树的组织思想和字典组织很像，字典树由此得名。

界说Trie的焦点思想是空间换时间，有 3 个基天性质：根节点不包罗字符，除根节点外每一个节点都只包罗一个字符。从根节点到某一节点，路径上经由的字符毗连起来，为该节点对应的字符串。每个节点的所有子节点包罗的字符都不相同。好比对单词序列lru, lua, mem, mcu 建设Trie树如下：Trie树建设和查询是可以同步举行的，可以在还没建设出完成的 Trie 树之前就找到目的数据，而如果用 Hash 表等结构存储是需要先建设完成表才气开始查询，这也是 Trie 树查询速度快的原因。

应用Trie树还用于搜索引擎的关键词提示功效。好比当你在搜索框中输入检索单词的开头几个字，搜索引擎就可以自动遐想匹配到可能的词组出来，这正是Trie树的最直接应用。

这种结构在海量数据查询上很有优势，因为不必为了找到目的数据遍历整个数据荟萃，只需按前缀遍历匹配的路径即可找到目的数据。因此，Trie树还可用于解决类似以下的面试题：❝给你100000个长度不凌驾10的单词。对于每一个单词，我们要判断他出没泛起过，如果泛起了，求第一次泛起在第几个位置。

❞❝有一个1G巨细的一个文件，内里每一行是一个词，词的巨细不凌驾16字节，内存限制巨细是1M，求频数最高的100个词❞❝1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串，请问怎么设计和实现？❞❝一个文本文件，约莫有一万行，每行一个词，要求统计出其中最频繁泛起的前10个词，请给出思想，给出时间庞大度分析。❞总结一下树形数据结构有许多变种，这篇文章我们从树开始，把几种常见树形数据结构学习了一遍，包罗二叉树、二叉查找树（二叉搜索树）、AVL树、红黑树、B树、Trie树。文章构想的时候想聊聊数据结构中的树，没想到步子跨的有点大，大到不知从何说起，因为数据结构中种种树的变体很是多，一篇文章实难细数，篇幅有限，也只能说是浅尝辄止，作为树形数据结构入门，如果要深入的学习，每个知识点还能写出一篇文章，好比 B+ 树原理及其在数据库索引中的应用、红黑树的详细分析等等，这次柠檬只是大略带大家走一遍。

在后端开发中，数据结构与算法是后端法式员的基本素养，除了基础架构部的后端开发同学，虽然我们平常不会经常造轮子，可是掌握基本的数据结构与算法仍然是很是有须要，面试也对相关能力有要求。回首往期文章，数据结构的内容写的比力少，如果大家有兴趣，柠檬会再多写一些相关主题的文章！谢谢列位的阅读，文章的目的是分享对知识的明白，技术类文章我都市重复求证以求最大水平保证准确性，若文中泛起显着纰漏也接待指出，我们一起在探讨中学习。Hi，我是柠檬，一枚一线互联网大厂后端法式员，小我私家技术民众号主要分享后端开发相关的技术学习，每篇文章都是我经心创作，如果文章对你有资助，请帮点亮「在看」也可以「分享」给需要的小同伴，你的分享和在看对柠檬很重要，在此先行谢过列位了！我是柠檬，我们下期再见！如果以为文章写的还行，对你有所资助，动动手指「点赞」或给「转发」是对我连续创作的最大支持。

可以微信搜索民众号「 后端技术学堂 」回复「1024」获取50本盘算机电子书，回复「进群」拉你进百人读者技术百人群，文章每周连续更新，我们下期见！点击下方「相识更多」。

本文来源：BOB综合体育APP下载-www.heyinshiliu.net