檸檬哥整理了50本計算機相關的電子書，關注公眾號「后端技術學堂」枫攀，回復「1024」我發(fā)給你括饶，回復「進群」拉你進讀者技術交流群。
本文首發(fā)個人技術微信公眾號来涨，點擊閱讀全文
面試愛問二叉樹图焰、B樹、紅黑樹蹦掐、字典樹技羔，你心里有數(shù)嗎？
數(shù)據結構中的這6種「樹」卧抗，你心中有數(shù)嗎堕阔？
數(shù)據結構這門課程是計算機相關專業(yè)的基礎課，數(shù)據結構指的是數(shù)據在計算機中的存儲颗味、組織方式超陆。
我們在學習數(shù)據結構時候，會遇到各種各樣的基礎數(shù)據結構浦马，比如堆棧时呀、隊列、數(shù)組晶默、鏈表谨娜、樹...這些基本的數(shù)據結構類型有各自的特點，不同數(shù)據結構適用于解決不同場景下的問題磺陡。
樹形結構相比數(shù)組趴梢、鏈表漠畜、堆棧這些數(shù)據結構來說，稍微復雜一點點坞靶，但樹形結構可以用于解決很多實際問題憔狞，因為現(xiàn)實世界事物之間的關系往往不是線性關聯(lián)的，而「樹」恰好適合描述這種非線性關系彰阴。
今天就帶大家一起學習下瘾敢，數(shù)據結構中的各種「樹」，這也是面試中經衬蛘猓考察的內容簇抵，手撕二叉樹是常規(guī)套路，對候選人也很有區(qū)分度射众，學完這篇文章碟摆，相信大家都會心中有「樹」了。
從樹說起
什么是樹叨橱？現(xiàn)實中的樹大家都見過典蜕，在數(shù)據結構中也有樹，此樹非彼樹雏逾，不過數(shù)據結構的樹和現(xiàn)實中的樹在形態(tài)上確實有點相像嘉裤。
樹是非線性的數(shù)據結構，用來模擬具有樹狀結構性質的數(shù)據集合栖博，它是由n個有限節(jié)點組成的具有層次關系的集合屑宠。在數(shù)據結構中樹是非線性數(shù)據結構，那我們先來了解下仇让，什么是線性與非線性數(shù)據結構典奉？
線性結構
線性結構是一個有序數(shù)據元素的集合。 其中數(shù)據元素之間的關系是一對一的關系丧叽，即除了第一個和最后一個數(shù)據元素之外卫玖，其它數(shù)據元素都是首尾相接的，常用的線性結構有：線性表踊淳，棧假瞬，隊列，雙端隊列迂尝，數(shù)組脱茉，串。
可以想象垄开，所謂的線性結構數(shù)據組織形式琴许，就像一條線段一樣筆直，元素之間首尾相接溉躲。比如現(xiàn)實中的火車進站榜田、食堂打飯排隊的隊列益兄。
非線性結構
簡而言之，線性結構的對立面就是非線性結構箭券。
樹
線性結構中節(jié)點是首位相接一對一關系净捅，在樹結構中節(jié)點之間不再是簡單的一對一關系，而是較為復雜的一對多的關系邦鲫，一個節(jié)點可以與多個節(jié)點發(fā)生關聯(lián)灸叼，樹是一種層次化的數(shù)據組織形式神汹，樹在現(xiàn)實中是可以找到例子的庆捺，比如現(xiàn)實中的族譜，親戚之間的關系是層次關聯(lián)的樹形關系屁魏。
數(shù)據結構中的「樹」的名字由來滔以，是因為如果把節(jié)點之間的關系直觀展示出來，由于長得和現(xiàn)實世界中的樹很像氓拼，由此得名你画。如圖：
樹的關鍵概念
人們對樹形結構的研究比較深入，為了方便研究樹的各種性質桃漾，抽象出了一些樹相關的概念坏匪，以便清晰簡介的描述一顆樹。下面幾個基礎概念必須了解撬统，否則你當你刷LeetCode樹相關題目時候适滓，或者面試官向你描述問題時，你會連題目都看不懂事什么意思恋追。
先來上一個圖解凭迹，下面的術語和概念對照著看，更容易理解苦囱。
什么是節(jié)點的度嗅绸？
度很好理解，直觀來說撕彤，數(shù)一下節(jié)點有幾個分叉就說這個節(jié)點的度是多少鱼鸠。
什么是根節(jié)點？
在一顆樹形結構中羹铅，最頂層的那個節(jié)點就是根節(jié)點了蚀狰，所有的子節(jié)點都源自它發(fā)散開來。
什么是父節(jié)點睦裳？
樹的父子關系和現(xiàn)實中很相似造锅，若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點廉邑。
什么是葉子節(jié)點哥蔚？
直觀來看葉子節(jié)點都位于樹的最底層倒谷，就是沒有分叉的節(jié)點，嚴格的定義是度為 0 的節(jié)點叫葉子節(jié)點糙箍。
什么是節(jié)點的高度渤愁？
高度是從葉子節(jié)點開始「自底向上」逐層累加的路徑長度，樹葉的高度為 0（有些書上也說是 0深夯，不用糾結）
什么是節(jié)點的深度抖格？
深度是從根節(jié)點開始「自頂向下」逐層累加的路徑長度，根的深度為1（有些書上也說是 0咕晋，問題不大）
小技巧：高度和深度雹拄，一個從下往上數(shù)，一個從上往下數(shù)掌呜。
樹的特點
樹形數(shù)據結構滓玖，具有以下的結構特點：
- 每個節(jié)點都只有有限個子節(jié)點或無子節(jié)點；
- 沒有父節(jié)點的節(jié)點稱為根節(jié)點质蕉；
- 每一個非根節(jié)點有且只有一個父節(jié)點势篡；
- 除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹模暗；
- 樹里面沒有環(huán)路禁悠，意思就是從一個節(jié)點出發(fā)，除非往返兑宇，否則不能回到起點碍侦。
二叉樹
有了前面「樹」的基礎鋪墊，二叉樹是一種特殊的樹顾孽，還記的上面我們學過「節(jié)點的度」嗎祝钢？二叉樹中每個節(jié)點的度不大于 2 ，即它的每個節(jié)點最多只有兩個分支若厚，通常稱二叉樹節(jié)點的左右兩個分支為左右子樹拦英。
二叉樹是很多其他樹型結構的基礎結構，比如下面要講的 AVL 樹测秸、二叉查找樹疤估，他們都是由二叉樹增加一些約束條件進化而來。
三種遍歷方式
二叉樹的遍歷就是逐個訪問二叉樹節(jié)點的數(shù)據霎冯，常見的二叉樹遍歷方式有三種铃拇，分別是前中后序遍歷，初學者分不清這幾個順序的差別沈撞。
有個簡單的記憶方式慷荔，這里的「前中后」都是對于根節(jié)點而言。
先訪問根節(jié)點后訪問左右子樹的遍歷方式是前序遍歷缠俺，先訪問左右子樹最后訪問根節(jié)點的遍歷方式是后序遍歷显晶，先訪問左子樹再訪問根節(jié)點最后訪問右子樹的遍歷方式是中序遍歷贷岸，下面詳細說明：
前序遍歷
遍歷順序是根節(jié)點->左子樹->右子樹
遍歷的得到的序列是：1 2 4 5 3 6 7
中序遍歷
遍歷順序是左子樹->根節(jié)點->右子樹
遍歷的得到的序列是：4 2 5 1 6 3 7
后序遍歷
遍歷順序是左子樹->右子樹->根節(jié)點
遍歷的得到的序列是：4 5 2 6 7 3 1
二叉查找樹
由于最基礎的二叉樹節(jié)點是無序的，想象一下如果在二叉樹中查找一個數(shù)據磷雇，最壞情況可能要要遍歷整個二叉樹偿警，這樣的查找效率是非常低下的。
由于基礎二叉樹不利于數(shù)據的查找和插入唯笙，因此我們有必要對二叉樹中的數(shù)據進行排序螟蒸，所以就有了「二叉查找樹」，可以說這種樹是為了查找而生的二叉樹崩掘，有時也稱它為「二叉排序樹」七嫌，都是同一種結構，只是換了個叫法呢堰。
查找二叉樹理解了也不難抄瑟，簡單來說就是二叉樹上所有節(jié)點的凡泣，左子樹上的節(jié)點都小于根節(jié)點枉疼，右子樹上所有節(jié)點的值都大于根節(jié)點。
這樣的結構設計鞋拟，使得查找目標節(jié)點非常方便骂维，可以通過關鍵字和當前節(jié)點的對比，很快就能知道目標節(jié)點在該節(jié)點的左子樹還是右子樹上贺纲，方便在樹中搜索目標節(jié)點航闺。
如果對排序二叉樹執(zhí)行中序遍歷，因為中序遍歷的順序是：左子樹->根節(jié)點->右子樹猴誊，最終可以得到一個節(jié)點值的有序列表潦刃。
舉個栗子：對上圖的排序二叉樹執(zhí)行中序遍歷，我們可以得到一個有序序列：1 2 3 4 5 6 7
查詢效率
二叉查找樹的查詢復雜度取決于目標節(jié)點的深度懈叹，因此當節(jié)點的深度比較大時乖杠，最壞的查詢效率是O(n)，其中n是樹中的節(jié)點個數(shù)澄成。
實際應用中有很多改進版的二叉查找樹胧洒，目的是盡可能使得每個節(jié)點的深度不要過深，從而提高查詢效率墨状。比如AVL樹和紅黑樹卫漫，可以將最壞效率降低至O(log n)，下面我們就來看下這兩種改進的二叉樹肾砂。
AVL樹
AVL 也叫平衡二叉查找樹列赎。AVL 這個名字的由來，是它的兩個發(fā)明者G. M. Adelson-Velsky 和 Evgenii Landis 的縮寫镐确，AVL最初是他們兩人在1962 年的論文「An algorithm for the organization of information」中提出來一種數(shù)據結構包吝。
定義
AVL 樹是一種平衡二叉查找樹肛根，二叉查找樹我們已經知道，那平衡是什么意思呢漏策？
我們舉個天平的例子派哲，天平兩端的重量要差不多才能平衡，否則就會出現(xiàn)向一邊傾斜的情況掺喻。把這個概念遷移到二叉樹中來芭届，根節(jié)點看作是天平的中點，左子樹的高度放在天平左邊感耙，右子樹的高度放在天平右邊褂乍，當左右子樹的高度相差「不是特別多」，稱為是平衡的二叉樹即硼。
AVL樹有更嚴格的定義：在二叉查找樹中逃片，任一節(jié)點對應的兩棵子樹的最大高度差為 1，這樣的二叉查找樹稱為平衡二叉樹只酥。其中左右子樹的高度差也有個專業(yè)的叫法：平衡因子褥实。
AVL樹的旋轉
一旦由于插入或刪除導致左右子樹的高度差大于1，此時就需要旋轉某些節(jié)點調整樹高度裂允，使其再次達到平衡狀態(tài)损离，這個過程稱為旋轉再平衡。
保持樹平衡的目的是可以控制查找绝编、插入和刪除在平均和最壞情況下的時間復雜度都是O(log n)僻澎，相比普通二叉樹最壞情況的時間復雜度是 O(n) ，AVL樹把最壞情況的復雜度控制在可接受范圍十饥，非常合適對算法執(zhí)行時間敏感類的應用窟勃。
B樹
B樹是魯?shù)婪颉ぐ轄枺≧udolf Bayer）1972年在波音研究實驗室（Boeing Research Labs）工作時發(fā)明的，關于B樹名字的由來至今是個未解之謎逗堵，有人猜是Bayer的首字母秉氧，也有人說是波音實驗室（Boeing Research Labs）的Boeing首字母縮寫，雖然B樹這個名字來源撲朔迷離砸捏，我們心里也沒點 B 樹谬运，但不影響今天我們來學習它。
定義
一個 m 階的B樹是一個有以下屬性的樹
- 每一個節(jié)點最多有 m 個子節(jié)點
- 每一個非葉子節(jié)點（除根節(jié)點）最少有 ?m/2? 個子節(jié)點垦藏，?m/2?表示向上取整梆暖。
- 如果根節(jié)點不是葉子節(jié)點，那么它至少有兩個子節(jié)點
- 有 k 個子節(jié)點的非葉子節(jié)點擁有 k ? 1 個鍵
- 所有的葉子節(jié)點都在同一層
如果之前不了解掂骏，相信第一眼看完定義肯定是蒙圈轰驳，不過多看幾遍好好理解一下就好了，畫個圖例，對照著看看：
特點
B樹是所有節(jié)點的平衡因子均等于0的多路查找樹（AVL樹是平衡因子不大于 1 的二路查找樹）级解。
B 樹節(jié)點可以保存多個數(shù)據冒黑，使得 B 樹可以不用像 AVL 樹那樣為了保持平衡頻繁的旋轉節(jié)點。
B樹的多路的特性勤哗，降低了樹的高度抡爹，所以B樹相比于平衡二叉樹顯得矮胖很多。
B樹非常適合保存在磁盤中的數(shù)據讀取芒划，因為每次讀取都會有一次磁盤IO冬竟，高度降低減少了磁盤IO的次數(shù)。
B樹常用于實現(xiàn)數(shù)據庫索引民逼，典型的實現(xiàn)泵殴，MongoDB索引用B樹實現(xiàn)，MySQL的Innodb 存儲引擎用B+樹存放索引拼苍。
說到B樹不得不提起它的好兄弟B+樹笑诅，不過這里不展開細說，只需知道疮鲫，B+樹是對B樹的改進吆你，數(shù)據都放在葉子節(jié)點，非葉子節(jié)點只存數(shù)據索引棚点。
紅黑樹
紅黑樹也是一種特殊的「二叉查找樹」早处。
到目前為止我們學習的 AVL 樹和即將學習的紅黑樹都是二叉查找樹的變體，可見二叉查找樹真的是非常重要基礎二叉樹瘫析，如果忘了它的定義可以先回頭看看。
特點
紅黑樹中每個結點都被標記了紅黑屬性默责，紅黑樹除了有普通的「二叉查找樹」特性之外贬循，還有以下的特征：
- 節(jié)點是紅色或黑色。
- 根是黑色桃序。
- 所有葉子都是黑色（葉子是NIL節(jié)點）杖虾。
- 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點媒熊。）
- 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點奇适。
這些性質有興趣可以自行研究，不過芦鳍，現(xiàn)在你只需要知道嚷往，這些約束確保了紅黑樹的關鍵特性：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。
而節(jié)點的路徑長度決定著對節(jié)點的查詢效率柠衅，這樣我們確保了皮仁，最壞情況下的查找、插入、刪除操作的時間復雜度不超過O(log n)贷祈，并且有較高的插入和刪除效率趋急。
應用場景
紅黑樹在實際應用中比較廣泛，有很多已經落地的實踐势誊，比如學習C++的同學都知道會接觸到 STL 標準庫呜达，而STL容器中的map、set粟耻、multiset闻丑、multimap 底層實現(xiàn)都是基于紅黑樹。
再比如勋颖，Linux內核中也有紅黑樹的實現(xiàn)嗦嗡，Linux系統(tǒng)在實現(xiàn)EXT3文件系統(tǒng)、虛擬內存管理系統(tǒng)饭玲，都有使用到紅黑樹這種數(shù)據結構侥祭。
Linux內核中的紅黑樹定義在內核文件如下的位置：
如果找不到，可以 find / -name rbtree.h 搜索一下即可茄厘，有興趣可以打開文件看下具體實現(xiàn)矮冬。
紅黑樹 VS 平衡二叉樹（AVL樹）
插入和刪除操作，一般認為紅黑樹的刪除和插入會比 AVL 樹更快次哈。因為胎署，紅黑樹不像 AVL 樹那樣嚴格的要求平衡因子小于等于1，這就減少了為了達到平衡而進行的旋轉操作次數(shù)窑滞，可以說是犧牲嚴格平衡性來換取更快的插入和刪除時間琼牧。
紅黑樹不要求有不嚴格的平衡性控制，但是紅黑樹的特點哀卫，使得任何不平衡都會在三次旋轉之內解決巨坊。而 AVL 樹如果不平衡，并不會控制旋轉操作次數(shù)此改，旋轉直到平衡為止趾撵。
查找操作，AVL樹的效率更高共啃。因為 AVL 樹設計比紅黑樹更加平衡占调，不會出現(xiàn)平衡因子超過 1 的情況，減少了樹的平均搜索長度移剪。
Trie樹（前綴樹或字典樹）
Trie來源于單詞 retrieve（檢索）究珊，Trie樹也稱為前綴樹或字典樹。利用字符串前綴來查找指定的字符串挂滓，縮短查找時間提高查詢效率苦银，主要用于字符串的快速查找和匹配啸胧。
為什么要稱其為字典樹呢？因為Trie樹的功能就像字典一樣幔虏，想象一下查英文字典纺念，我們會根據首字母找到對應的頁碼，接著根據第二想括、第三...個單詞陷谱，逐步查找到目標單詞，Trie樹的組織思想和字典組織很像瑟蜈，字典樹由此得名烟逊。
定義
Trie的核心思想是空間換時間，有 3 個基本性質：
- 根節(jié)點不包含字符铺根，除根節(jié)點外每一個節(jié)點都只包含一個字符宪躯。
- 從根節(jié)點到某一節(jié)點，路徑上經過的字符連接起來位迂，為該節(jié)點對應的字符串访雪。
- 每個節(jié)點的所有子節(jié)點包含的字符都不相同。
比如對單詞序列lru, lua, mem, mcu 建立Trie樹如下：
Trie樹建立和查詢是可以同步進行的掂林，可以在還沒建立出完成的 Trie 樹之前就找到目標數(shù)據臣缀，而如果用 Hash 表等結構存儲是需要先建立完成表才能開始查詢，這也是 Trie 樹查詢速度快的原因泻帮。
應用
Trie樹還用于搜索引擎的關鍵詞提示功能精置。比如當你在搜索框中輸入檢索單詞的開頭幾個字，搜索引擎就可以自動聯(lián)想匹配到可能的詞組出來锣杂，這正是Trie樹的最直接應用脂倦。
這種結構在海量數(shù)據查詢上很有優(yōu)勢，因為不必為了找到目標數(shù)據遍歷整個數(shù)據集合蹲堂，只需按前綴遍歷匹配的路徑即可找到目標數(shù)據狼讨。
因此，Trie樹還可用于解決類似以下的面試題：
給你100000個長度不超過10的單詞柒竞。對于每一個單詞，我們要判斷他出沒出現(xiàn)過播聪，如果出現(xiàn)了朽基，求第一次出現(xiàn)在第幾個位置。
有一個1G大小的一個文件离陶，里面每一行是一個詞稼虎，詞的大小不超過16字節(jié)，內存限制大小是1M招刨，求頻數(shù)最高的100個詞
1000萬字符串霎俩，其中有些是重復的，需要把重復的全部去掉，保留沒有重復的字符串打却，請問怎么設計和實現(xiàn)杉适？
一個文本文件，大約有一萬行柳击，每行一個詞猿推，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞，請給出思想捌肴，給出時間復雜度分析蹬叭。
絮絮叨叨
樹形數(shù)據結構有許多變種，這篇文章我們從樹開始状知，把幾種常見樹形數(shù)據結構學習了一遍秽五，包括二叉樹、二叉查找樹（二叉搜索樹）饥悴、AVL樹坦喘、紅黑樹、B樹铺坞、Trie樹起宽。
文章構思的時候想聊聊數(shù)據結構中的樹，沒想到步子跨的有點大济榨，大到不知從何說起蓖柔，因為數(shù)據結構中各種樹的變體非常多，一篇文章實難細數(shù)尉辑，篇幅有限积瞒，也只能說是淺嘗輒止，作為樹形數(shù)據結構入門丐一，如果要深入的學習藻糖，每個知識點還能寫出一篇文章，比如 B+ 樹原理及其在數(shù)據庫索引中的應用库车、紅黑樹的詳細分析等等巨柒，這次檸檬只是粗略帶大家走一遍。
在后端開發(fā)中柠衍，數(shù)據結構與算法是后端程序員的基本素養(yǎng)洋满，除了基礎架構部的后端開發(fā)同學，雖然我們平常不會經常造輪子珍坊，但是掌握基本的數(shù)據結構與算法仍然是非常有必要牺勾，面試也對相關能力有要求≌舐回顧往期文章驻民，數(shù)據結構的內容寫的比較少翻具，如果大家有興趣，檸檬會再多寫一些相關主題的文章回还！
感謝各位的閱讀裆泳，文章的目的是分享對知識的理解，技術類文章我都會反復求證以求最大程度保證準確性懦趋，若文中出現(xiàn)明顯紕漏也歡迎指出晾虑，我們一起在探討中學習。
Hi仅叫，我是檸檬帜篇，熱愛技術，也愛生活诫咱！一枚一線互聯(lián)網大廠后端程序員笙隙，個人技術公眾號主要分享后端開發(fā)相關的技術文章，每篇文章都是我精心創(chuàng)作坎缭，如果文章對你有幫助竟痰，請幫點亮「在看」也可以「分享」給需要的小伙伴，你的分享和在看對檸檬很重要掏呼，在此先行謝過各位了坏快！我是lemon，我們下期再見憎夷！
如果文章對你有幫助莽鸿，答應我不要白piao好嗎？ 「點贊拾给、評論祥得、轉發(fā)」激勵我持續(xù)創(chuàng)作。
可以微信搜索公眾號「 后端技術學堂 」回復「1024」獲取50本計算機電子書蒋得，回復「進群」拉你進讀者技術交流群级及，文章每周持續(xù)更新，我們下期見额衙！
