文章目錄

• 關于我的倉庫
• 前言
• 21講哈希算法（上）：如何防止數據庫中的用戶信息被脫庫
• • 哈希算法
  • MD5初識
  • 哈希算法七應用【前四】
  • • 應用一：安全加密
    • 應用二：唯一標識
    • 應用三：數據校驗
    • 應用四：散列函數
    • 解答開篇：守護最好的用戶數據庫
  • 課后題：現在，區塊鏈是一個很火的領域，它被很多人神秘化，不過其底層的實現原理并不復雜。其中，哈希算法就是它的一個非常重要的理論基礎。你能講一講區塊鏈使用的是哪種哈希算法嗎？是為了解決什么問題而使用的呢？
• 22講哈希算法（下）：哈希算法在分布式系統中有哪些應用
• • 哈希算法七應用【后三】
  • • 應用五：負載均衡
    • 應用六：數據分片
    • • 如何統計“搜索關鍵詞”出現的次數？
      • 如何快速判斷圖片是否在圖庫中？
    • 應用七：分布式存儲
• 23講二叉樹基礎（上）：什么樣的二叉樹適合用數組來存儲
• • 基礎概念
  • 疑點
  • 二叉樹（Binary Tree）
  • 二叉樹的遍歷
  • 課后題
  • • 給定一組數據，比如1，3，5，6，9，10。你來算算，可以構建出多少種不同的二叉樹？
    • 我們講了三種二叉樹的遍歷方式，前、中、后序。實際上，還有另外一種遍歷方式，也就是按層遍歷，你知道如何實現嗎？
• 24講二叉樹基礎（下）：有了如此高效的散列表，為什么還需要二叉樹
• • 二叉查找樹（Binary Search Tree）
  • • 二叉查找樹的查找操作
    • 二叉查找樹的插入操作
    • 二叉查找樹的刪除操作
    • 二叉查找樹的其他操作
  • 支持重復數據的二叉查找樹
  • 二叉查找樹的時間復雜度分析
  • 解答開篇：二叉樹相對于散列表優勢所在
  • 課后題：如何通過編程，求出一棵給定二叉樹的確切高度呢？
• 25講紅黑樹（上）：為什么工程中都用紅黑樹這種二叉樹
• • 平衡二叉查找樹
  • 定義一棵“紅黑樹”
  • 紅黑樹->靜態平衡？
  • 解答開篇：為什么都喜歡使用紅黑樹，而不是其他平衡二叉查找樹呢？
  • 課后思考：動態數據結構支持動態地數據插入、刪除、查找操作，除了紅黑樹，我們前面還學習過哪些呢？能對比一下各自的優勢、劣勢，以及應用場景嗎？

關于我的倉庫

• 這篇文章是我為面試準備的學習總結中的一篇
• 我將準備面試中找到的所有學習資料，寫的Demo，寫的博客都放在了這個倉庫里iOS-Engineer-Interview
• 歡迎star??
• 其中的博客在簡書，CSDN都有發布
• 博客中提到的相關的代碼Demo可以在倉庫里相應的文件夾里找到

前言

• 該系列為學習《數據結構與算法之美》的系列學習筆記
• 總結規律為一周一更，內容包括其中的重要知識帶你，以及課后題的解答
• 算法的學習學與刷題并進，希望能真正養成解算法題的思維
• LeetCode刷題倉庫：LeetCode-All-In
• 多說無益，你應該開始打代碼了

21講哈希算法（上）：如何防止數據庫中的用戶信息被脫庫

• 哦，開局就是上古秘辛，2011年CSDN還是用明文保存的賬戶密碼，這也忒靠譜了
• 幸好那個時候還不知道CSDN是個蝦米玩意呢

哈希算法

• 從哈希值不能反向推導出原始數據（所以哈希算法也叫單向哈希算法）
• 對輸入數據非常敏感，哪怕原始數據只修改了一個Bit，最后得到的哈希值也大不相同
• 散列沖突的概率要很小，對于不同的原始數據，哈希值相同的概率非常小
• 哈希算法的執行效率要盡量高效，針對較長的文本，也能快速地計算出哈希值

MD5初識

• 之前在寫網絡下載的時候就大概了解過這個算法，這里正好講到了，我就多查了點資料看了下
• 首先MD5被稱之為不可逆算法，無法從哈希值逆推出原始數據，為什么MD5源碼開放的情況下我們會無法逆推呢？因為在哈希過程中，我們不會去刻意保存原數據
• 比如我們進行了>>操作，將一個二進制數右移了兩位，這樣子必然會丟失掉最左邊的兩位，在這樣的情況下就算我們有源碼知道它進行了右移操作，進行左移，也無法得到原來的那兩位，也就無法推倒到原來的數據【這只是一個很簡單的例子】
• 所以對于這樣的單向哈希算法，我們在意的只是加密這一過程，因此很多人說MD5不能算加密算法，因為加密會包括加密和解密，而MD5只管殺，不管埋，跟多的是視作一個生成數字簽名的算法，從這個角度可能會更好理解這一部分
• 而我查到的資料提到2004年山東大學一位教授已經破譯MD5，是說能夠加快碰撞，就是說假如A哈希完結果是B，我現在能找到一個C哈希完也是B，加快了碰撞
• MD5“解密”過程正確來說不應該叫做“解密”，應該叫做MD5碰撞算法，只是拿到一個原始值再做一次MD5算法，看得到的的MD5值和你之前的MD5是不是一致，如果一致，我們就大體認為是原始值一致。為什么說大體呢？老師也說過了，會有HASH碰撞，可能不一樣的原始值長生一樣的HASH值，概率為1/2^128

哈希算法七應用【前四】

應用一：安全加密

• 加密哈希算法舉例：MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法）、SHA（Secure Hash Algorithm，安全散列算法）、 DES（Data Encryption Standard，數據加密標準）、AES（Advanced Encryption Standard，高級加密標準）
• 加密哈希算法的兩個特點：
  • 第一點是很難根據哈希值反向推導出原始數據
  • 第二點是散列沖突的概率要很小
• 首先散列沖突一定會出現，這基于鴿巢原理【如果有10個鴿巢，有11只鴿子，那肯定有1個鴿巢中的鴿子數量多于1個，換句話說就是，肯定有2只鴿子在1個鴿巢內】
• 而以MD5舉例，其哈希值是固定的128位二進制串，最多只有2^128個數據，而我們要哈希的數據是無限的
• 所有的安全措施，只是增加攻擊的成本而已

應用二：唯一標識

• 這里假如我們要在圖庫里搜索一張圖片是否存在，我們知道所有圖片的本質是二進制，如果我們是根據二進制碼一個一個對照搜索顯然十分耗時【圖片大的會有數MB，會很大】
• 我們可以給每一個圖片取一個唯一標識，或者說信息摘要。比如，我們可以從圖片的二進制碼串開頭取100個字節，從中間取100個字節，從最后再取100個字節，然后將這300個字節放到一塊，通過哈希算法（比如MD5），得到一個哈希字符串，用它作為圖片的唯一標識。通過這個唯一標識來判定圖片是否在圖庫中，這樣就可以減少很多工作量
• 如果還想繼續提高效率，我們可以把每個圖片的唯一標識，和相應的圖片文件在圖庫中的路徑信息，都存儲在散列表中。當要查看某個圖片是不是在圖庫中的時候，我們先通過哈希算法對這個圖片取唯一標識，然后在散列表中查找是否存在這個唯一標識

應用三：數據校驗

• BT下載的原理是基于P2P協議的。我們從多個機器上并行下載一個2GB的電影，這個電影文件可能會被分割成很多文件塊（比如可以分成100塊，每塊大約20MB）。等所有的文件塊都下載完成之后，再組裝成一個完整的電影文件就行了
• 這樣就會存在，在某臺機器上的資源看你是被惡意修改過的，或者是在下載過程中出現過問題，導致其文件塊是不完整的
• 我們通過哈希算法，對100個文件塊分別取哈希值，并且保存在種子文件中。我們在前面講過，哈希算法有一個特點，對數據很敏感。只要文件塊的內容有一丁點兒的改變，最后計算出的哈希值就會完全不同。所以，當文件塊下載完成之后，我們可以通過相同的哈希算法，對下載好的文件塊逐一求哈希值，然后跟種子文件中保存的哈希值比對。如果不同，說明這個文件塊不完整或者被篡改了，需要再重新從其他宿主機器上下載這個文件塊
• 有趣啊，我感覺計算機最有意思的地方就是很多東西完全不是你空想能想到的，想這個數據校驗會出現的情況就那么復雜

應用四：散列函數

• 散列函數是設計一個散列表的關鍵。它直接決定了散列沖突的概率和散列表的性能。不過，相對哈希算法的其他應用，散列函數對于散列算法沖突的要求要低很多。即便出現個別散列沖突，只要不是過于嚴重，我們都可以通過開放尋址法或者鏈表法解決
• 散列函數對于散列算法計算得到的值，是否能反向解密也并不關心。散列函數中用到的散列算法，更加關注散列后的值是否能平均分布，也就是，一組數據是否能均勻地散列在各個槽中。除此之外，散列函數執行的快慢，也會影響散列表的性能，所以，散列函數用的散列算法一般都比較簡單，比較追求效率

解答開篇：守護最好的用戶數據庫

• 選擇相對安全的加密算法
• 引入一個鹽（salt），跟用戶的密碼組合在一起，增加密碼的復雜度。我們拿組合之后的字符串來做哈希算法加密，將它存儲到數據庫中，進一步增加破解的難度
• 現在大多公司都采用無論密碼長度多少，計算字符串hash時間都固定或者足夠慢的算法如PBKDF2WithHmacSHA1，來降低硬件計算hash速度，減少不同長度字符串計算hash所需時間不一樣而泄漏字符串長度信息，進一步減少風險

課后題：現在，區塊鏈是一個很火的領域，它被很多人神秘化，不過其底層的實現原理并不復雜。其中，哈希算法就是它的一個非常重要的理論基礎。你能講一講區塊鏈使用的是哪種哈希算法嗎？是為了解決什么問題而使用的呢？

• 區塊鏈是一塊塊區塊組成的，每個區塊分為兩部分：區塊頭和區塊體。
• 區塊頭保存著 自己區塊體 和 上一個區塊頭 的哈希值。
• 因為這種鏈式關系和哈希值的唯一性，只要區塊鏈上任意一個區塊被修改過，后面所有區塊保存的哈希值就不對了。
• 區塊鏈使用的是 SHA256 哈希算法，計算哈希值非常耗時，如果要篡改一個區塊，就必須重新計算該區塊后面所有的區塊的哈希值，短時間內幾乎不可能做到。

22講哈希算法（下）：哈希算法在分布式系統中有哪些應用

哈希算法七應用【后三】

• 個人認為這三點基本上都是一個東西本質上
• 就是說，怎么追求極致的均衡，方便擴容，縮容
• 所以思想都一樣，注意下應用的場景吧，話說，我覺得這個網課真沒白學，是挺有意思的，有一種世界開闊了的感覺

應用五：負載均衡

• 實現一個會話粘滯（session sticky）的負載均衡算法，我們需要在同一個客戶端上，在一次會話中的所有請求都路由到同一個服務器上
• 。我們可以通過哈希算法，對客戶端IP地址或者會話ID計算哈希值，將取得的哈希值與服務器列表的大小進行取模運算，最終得到的值就是應該被路由到的服務器編號。 這樣，我們就可以把同一個IP過來的所有請求，都路由到同一個后端服務器上

應用六：數據分片

• 這個很像sideTables和sideTable的設計思想，面試的時候可以提一下，我覺得會高端很多，哈希真的運用很廣泛，很有意思

如何統計“搜索關鍵詞”出現的次數？

• 假如我們有1T的日志文件，這里面記錄了用戶的搜索關鍵詞，我們想要快速統計出每個關鍵詞被搜索的次數
• 難點有兩個，第一個是搜索日志很大，沒辦法放到一臺機器的內存中。第二個難點是，如果只用一臺機器來處理這么巨大的數據，處理時間會很長
• 針對方法就是先對數據分片，采用多臺機器處理的方法，提高處理速度
• 為了提高處理的速度，我們用n臺機器并行處理。我們從搜索記錄的日志文件中，依次讀出每個搜索關鍵詞，并且通過哈希函數計算哈希值，然后再跟n取模，最終得到的值，就是應該被分配到的機器編號
• 這樣能保證的是哈希值相同的機器會被分配到同一臺機器

如何快速判斷圖片是否在圖庫中？

• 假設我們的圖庫里面有上億張圖片，我們將無法簡單的在一臺機器上進行構建散列表
• 我們每次從圖庫中讀取一個圖片，計算唯一標識，然后與機器個數n求余取模，得到的值就對應要分配的機器編號，然后將這個圖片的唯一標識和圖片路徑發往對應的機器構建散列表
• 當我們要判斷一個圖片是否在圖庫中的時候，我們通過同樣的哈希算法，計算這個圖片的唯一標識，然后與機器個數n求余取模。假設得到的值是k，那就去編號k的機器構建的散列表中查找

應用七：分布式存儲

• 參考百話解析:一致性哈希算法 consistent hashing
• 假設我們有三臺機器，將其哈希值對2的32次取余，投射到環上

• 這樣的好處在于：我們不用修改我們的哈希算法，不會出現同一個文件會被先后放到不同的服務器上
• 因為在這樣的背景下，增加/去除服務器，只會影響到很小一部分的服務器，不會影響到所有人

• 同時，我們還會引入虛擬節點的概念，因為我們在環上的節點不一定均勻，有可能會導致某個服務器運作量大增

• 真他娘的妙，這也許就是傳說中的美麗的算法吧

23講二叉樹基礎（上）：什么樣的二叉樹適合用數組來存儲

• 終于到樹的章節了，沖沖沖

基礎概念

• 基本課上都講過，滑一滑

• A節點就是B節點的父節點，B節點是A節點的子節點。B、C、D這三個節點的父節點是同一個節點，所以它們之間互稱為兄弟節點。我們把沒有父節點的節點叫作根節點，也就是圖中的節點E。我們把沒有子節點的節點叫作葉子節點或者葉節點，比如圖中的G、H、I、J、K、L都是葉子節點
• 分清楚高度 深度 葉子結點之類的問題是比較重要的

• 可以這么記：高度就是數有幾樓，數的時候肯定是從下往上數的，所以根結點高度最高；深度就是從地平線往下數的，所以根結點會是0

疑點

• 這里有一個地方很奇怪在于對于樹的高度存在兩種說法，在這里做一下摘錄

• 根據《數據結構與算法（王曙燕主編，人民郵電出版社出版）》，高度就是樹的深度，為所有節點層次的最大值，也就是說對于上圖，樹的高度為4
• 而根據網課的說法，樹的高度是經過路徑最大值，也就是說是三
• 這個的區別就在于只有一個節點的時候，將其視作是高度0還是1
• 這兩種觀點據我搜索，確實都有，那么先按照王老師的觀點來寫吧

二叉樹（Binary Tree）

• 二叉樹主要分清楚完全二叉樹和滿二叉樹

• 滿二叉樹是完全二叉樹的一種

• 全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹
  

• 特點：葉子節點都在最底下兩層，最后一層的葉子節點都靠左排列，并且除了最后一層，其他層的節點個數都要達到最大

• 完全二叉樹的定義來源于數組存儲的順序存儲法，把根節點存儲在下標i = 1的位置

• 這樣也就是完全按照編號作為數組下標去存儲

• 我們不能簡單的對二叉樹進行存儲，必須要在遵循這樣的規則的基礎上去存儲，標準很簡單，就是能不能在這個數組的基礎上重構出一棵二叉樹
• 如果某棵二叉樹是一棵完全二叉樹，那用數組存儲無疑是最節省內存的一種方式。因為數組的存儲方式并不需要像鏈式存儲法那樣，要存儲額外的左右子節點的指針。這也是為什么完全二叉樹會單獨拎出來的原因，也是為什么完全二叉樹要求最后一層的子節點都靠左的原因
• 當我們講到堆和堆排序的時候，你會發現，堆其實就是一種完全二叉樹，最常用的存儲方式就是數組

二叉樹的遍歷

• codeRunner啟動，開始打代碼！

#include <iostream> #include <string> #include <time.h> #include <stack> #include <queue> #define random(x) (rand()%x)char words[15] = {'A', 'B', 'D', '#', 'G', '#', '#', '#', 'C', 'E', '#', '#', 'F', '#', '#'}; //char words[15] = {ABD#G###CE##F##}; int p = 0;typedef struct BTNode {int data;struct BTNode *lChild;struct BTNode *rChild; }BTNode;using namespace std;// 工具：輸出結點函數 void PrintBTNodeData(BTNode *root) {if (root) {cout << root -> data << endl;} }// 先序創建二叉樹 BTNode * CreateBiTree(BTNode *root) {char ch = 0;cout << "輸入希望生成的二叉樹結構：" << endl;cin >> ch;if (ch == '#') {root = NULL;} else {root = (BTNode *)malloc(sizeof(BTNode));root -> data = random(100);cout << "生成隨機數：" << root -> data << endl;root -> lChild = CreateBiTree(root -> lChild);root -> rChild = CreateBiTree(root -> rChild);}return root; }// 遞歸版先序遍歷 void PreOrderInternally(BTNode *root) {if (root == NULL) {return;}PrintBTNodeData(root);PreOrderInternally(root -> lChild);PreOrderInternally(root -> rChild); }// 遞歸版中序遍歷 void InOrderInternally(BTNode *root) {if (root == NULL) {return;}InOrderInternally(root -> lChild);PrintBTNodeData(root);InOrderInternally(root -> rChild); }// 遞歸版后序遍歷 void PostOrderInternally(BTNode *root) {if (root == NULL) {return;}PostOrderInternally(root -> lChild);PostOrderInternally(root -> rChild);PrintBTNodeData(root); }// 借助隊列的層次遍歷 void LevelOrder(BTNode *root) {if (root == NULL) {return;}BTNode *p = root;queue<BTNode *> s;s.push(p);while (!s.empty()) {p = s.front();s.pop();PrintBTNodeData(p);if (p->lChild != NULL) {s.push(p->lChild);}if (p->rChild != NULL) {s.push(p->rChild);}} }// 非遞歸版先序遍歷 void PreOrder(BTNode *root) {BTNode *p = root;stack<BTNode *> st;while (p != NULL || !st.empty()) {while (p != NULL) {PrintBTNodeData(p);st.push(p);p = p->lChild;}if (!st.empty()) {p = st.top();st.pop();p = p -> rChild;}} }// 非遞歸版中序遍歷 void InOrder(BTNode *root) {BTNode *p = root;stack<BTNode *> st;while (p != NULL || !st.empty()) {while (p != NULL) {st.push(p);p = p->lChild;}if (!st.empty()) {p = st.top();PrintBTNodeData(p);st.pop();p = p -> rChild;}} }// 非遞歸版后序遍歷 void PostOrder(BTNode *root) {BTNode *p = root;BTNode *q = NULL;stack<BTNode *> st;while (p != NULL || !st.empty()) {while (p != NULL) {st.push(p);p = p->lChild;}if (!st.empty()) {p = st.top();if (p->rChild == NULL || p->rChild == q) {p = st.top();st.pop();PrintBTNodeData(p);q = p;p = NULL;} else {p = p->rChild;}}} }int main(int argc, char *argv[]) {srand((int)time(0));BTNode *T;T = CreateBiTree(T);cout << "構造完成" << endl;cout << "開始遞歸版先序遍歷" << endl;PreOrderInternally(T);cout << "開始遞歸版中序遍歷" << endl;InOrderInternally(T);cout << "開始遞歸版后序遍歷" << endl;PostOrderInternally(T);cout << "開始層次遍歷" << endl;LevelOrder(T);cout << "開始非遞歸版先序遍歷" << endl;PreOrder(T);cout << "開始非遞歸版中序遍歷" << endl;InOrder(T);cout << "開始非遞歸版后序遍歷" << endl;PostOrder(T);cout << "end" << endl; }

• CodeRunner退出，開始自閉！

課后題

給定一組數據，比如1，3，5，6，9，10。你來算算，可以構建出多少種不同的二叉樹？

思想：遞歸+組合 當n=1時，只有1個根節點，則只能組成1種形態的二叉樹，令n個節點可組成的二叉樹數量表示為h(n)， 則h(1)=1； 當n=2時，1個根節點固定，還有n-1個節點，可以作為左子樹，也可以作為右子樹， 即：h(2)=h(0)*h(1)+h(1)*h(0)=2，則能組成2種形態的二叉樹。這里h(0)表示空，所以只能算一種形態，即h(0)=1; 當n=3時，1個根節點固定，還有n-1=2個節點，可以在左子樹或右子樹， 即：h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，則能組成5種形態的二叉樹。 以此類推，當n>=2時，可組成的二叉樹數量為h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)種。 即符合Catalan數的定義，可直接利用通項公式得出結果。 遞歸式： h(n)=h(n-1)*(4*n-2)/(n+1); 該遞推關系的解為： h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

我們講了三種二叉樹的遍歷方式，前、中、后序。實際上，還有另外一種遍歷方式，也就是按層遍歷，你知道如何實現嗎？

• 代碼有，其實就是借助隊列實現

24講二叉樹基礎（下）：有了如此高效的散列表，為什么還需要二叉樹

二叉查找樹（Binary Search Tree）

• 二叉搜索樹的定義要求很簡單：二叉查找樹要求，在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值
• 幾個搜索二叉樹的例子：

二叉查找樹的查找操作

• 我們先取根節點，如果它等于我們要查找的數據，那就返回。如果要查找的數據比根節點的值小，那就在左子樹中遞歸查找；如果要查找的數據比根節點的值大，那就在右子樹中遞歸查找

二叉查找樹的插入操作

• 如果要插入的數據比節點的數據大，并且節點的右子樹為空，就將新數據直接插到右子節點的位置；如果不為空，就再遞歸遍歷右子樹，查找插入位置。同理，如果要插入的數據比節點數值小，并且節點的左子樹為空，就將新數據插入到左子節點的位置；如果不為空，就再遞歸遍歷左子樹，查找插入位置

二叉查找樹的刪除操作

• 第一種情況是，如果要刪除的節點沒有子節點，我們只需要直接將父節點中，指向要刪除節點的指針置為null。比如圖中的刪除節點55
• 第二種情況是，如果要刪除的節點只有一個子節點（只有左子節點或者右子節點），我們只需要更新父節點中，指向要刪除節點的指針，讓它指向要刪除節點的子節點就可以了。比如圖中的刪除節點13
• 第三種情況是，如果要刪除的節點有兩個子節點，這就比較復雜了。我們需要找到這個節點的右子樹中的最小節點，把它替換到要刪除的節點上。然后再刪除掉這個最小節點，因為最小節點肯定沒有左子節點（如果有左子結點，那就不是最小節點了），所以，我們可以應用上面兩條規則來刪除這個最小節點。比如圖中的刪除節點18

二叉查找樹的其他操作

• 中序遍歷二叉查找樹，可以輸出有序的數據序列，時間復雜度是O(n)，非常高效

支持重復數據的二叉查找樹

• 第一種方法：鏈表拉鏈
• 通過鏈表和支持動態擴容的數組等數據結構，把值相同的數據都存儲在同一個節點上
• 第二種方法：將相等數據視作大的數，存在右子樹
• 每個節點仍然只存儲一個數據。在查找插入位置的過程中，如果碰到一個節點的值，與要插入數據的值相同，我們就將這個要插入的數據放到這個節點的右子樹，也就是說，把這個新插入的數據當作大于這個節點的值來處理

• 當要查找數據的時候，遇到值相同的節點，我們并不停止查找操作，而是繼續在右子樹中查找，直到遇到葉子節點，才停止。這樣就可以把鍵值等于要查找值的所有節點都找出來

• 對于刪除操作，我們也需要先查找到每個要刪除的節點，然后再按前面講的刪除操作的方法，依次刪除

二叉查找樹的時間復雜度分析

• 二叉搜索樹根據構造的不同的，搜索所用的時間復雜度理所應當的也是不同的

• 時間復雜度其實都跟樹的高度成正比，也就是O(height)
• 樹的高度就等于最大層數減一，為了方便計算，我們轉換成層來表示。從圖中可以看出，包含n個節點的完全二叉樹中，第一層包含1個節點，第二層包含2個節點，第三層包含4個節點，依次類推，下面一層節點個數是上一層的2倍，第K層包含的節點個數就是2^(K-1)
• 但是對于最后一層的節點個數是在1個到2^(L-1)個之間

n >= 1+2+4+8+...+2^(L-2)+1 n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

• L的范圍是[log2(n+1), log2n +1]。完全二叉樹的層數小于等于log2n +1，也就是說，完全二叉樹的高度小于等于log2n

解答開篇：二叉樹相對于散列表優勢所在

• 散列表中的數據是無序存儲的，如果要輸出有序的數據，需要先進行排序。而對于二叉查找樹來說，我們只需要中序遍歷，就可以在O(n)的時間復雜度內，輸出有序的數據序列
• 散列表擴容耗時很多，而且當遇到散列沖突時，性能不穩定，盡管二叉查找樹的性能不穩定，但是在工程中，我們最常用的平衡二叉查找樹的性能非常穩定，時間復雜度穩定在O(logn)
• 籠統地來說，盡管散列表的查找等操作的時間復雜度是常量級的，但因為哈希沖突的存在，這個常量不一定比logn小，所以實際的查找速度可能不一定比O(logn)快。加上哈希函數的耗時，也不一定就比平衡二叉查找樹的效率高
• 散列表的構造比二叉查找樹要復雜，需要考慮的東西很多。比如散列函數的設計、沖突解決辦法、擴容、縮容等。平衡二叉查找樹只需要考慮平衡性這一個問題，而且這個問題的解決方案比較成熟、固定
• 為了避免過多的散列沖突，散列表裝載因子不能太大，特別是基于開放尋址法解決沖突的散列表，不然會浪費一定的存儲空間
• 綜合這幾點，平衡二叉查找樹在某些方面還是優于散列表的，所以，這兩者的存在并不沖突。我們在實際的開發過程中，需要結合具體的需求來選擇使用哪一個

課后題：如何通過編程，求出一棵給定二叉樹的確切高度呢？

• 王爭一句話，阿文做斷手

// 深度優先搜索計算二叉樹的高度 int GetHeightDFS(BTNode *root) {if (root == NULL) {// 這里存在一個問題就是對于葉子結點，他會直接視作將其高度記做1，而高度的定義是邊數，也就是說對于只有一個節點的殘疾樹，我們直接視作高度為0，這點要注意return 0;}int leftHeight = GetHeightDFS(root->lChild);int rightHeight = GetHeightDFS(root->rChild);return max(leftHeight, rightHeight) + 1; }// 后序遍歷二叉樹計算樹的高度 int GetHeightPostOrder(BTNode *root) {if (root == NULL) {return 0;}int height = 0;BTNode *p = root;BTNode *q = NULL;stack<BTNode *> st;while (p != NULL || !st.empty()) {while (p != NULL) {st.push(p);p = p->lChild;}if (!st.empty()) {p = st.top();if (p->rChild == NULL || p->rChild == q) {int tmpheight = (int)st.size();height = max(height, tmpheight);p = st.top();st.pop();q = p;p = NULL;} else {p = p->rChild;}}}return height; }// 層次遍歷二叉樹計算樹的高度 int GetHeightLevelOrder(BTNode *root) {if (root == NULL) {return 0;}int height = 0;BTNode *p = root;queue<BTNode *> s;s.push(p);while (!s.empty()) {height++;int width = s.size();for (int i = 0; i < width; i++) {p = s.front();s.pop();if (p->lChild != NULL) {s.push(p->lChild);}if (p->rChild != NULL) {s.push(p->rChild);}}}return height; }

25講紅黑樹（上）：為什么工程中都用紅黑樹這種二叉樹

• 紅黑將至

平衡二叉查找樹

• 定義：二叉樹中任意一個節點的左右子樹的高度相差不能大于1

• 這里左邊很明顯是平衡二叉樹，而右邊，對于一個節點，就算其左節點為NULL，也視作高度為零，參與比較

• 紅黑樹不是嚴格的平衡二叉搜索樹

• 平衡二叉查找樹中“平衡”的意思，其實就是讓整棵樹左右看起來比較“對稱”、比較“平衡”，不要出現左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應的插入、刪除、查找等操作的效率高一些

定義一棵“紅黑樹”

• 紅黑樹中的節點，一類被標記為黑色，一類被標記為紅色

• 根節點是黑色的

• 每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不存儲數據

• 任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的

• 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點

• 下面是忽略了葉子節點的紅黑樹

• 這里要理解下相鄰節點不能同時是紅色的，相鄰是指有邊線連著的兩個節點，也就是說對于，兩個紅色節點想走到一起必須要經過一個黑色節點

紅黑樹->靜態平衡？

• “平衡”的意思可以等價為性能不退化。“近似平衡”就等價為性能不會退化的太嚴重
• 一棵極其平衡的二叉樹（滿二叉樹或完全二叉樹）的高度大約是log2n，所以如果要證明紅黑樹是近似平衡的，我們只需要分析，紅黑樹的高度是否比較穩定地趨近log2n就好了
• 這里的分析比較繞，需要多看幾遍才好理解
• 首先將所有紅色節點去掉看下黑樹是什么樣子的

• 前面說紅黑樹特征時講過：從任意節點到可達的葉子節點的每個路徑包含相同數目的黑色節點。我們從四叉樹中取出某些節點，放到葉節點位置，四叉樹就變成了完全二叉樹。所以，僅包含黑色節點的四叉樹的高度，比包含相同節點個數的完全二叉樹的高度還要小
• 這里理解下就是說按照同樣的節點數去構建完全二叉樹，顯然還要多幾層
• 所以黑樹的高度小于log2n【因為前面講過，完全二叉樹即平衡二叉樹的高度為log2n】
• 現在我們在加上紅點，由于要求每兩個紅點之間夾一個黑點，所以最極端的情況也就是高度翻倍，及高度小于2log2n
• 所以，紅黑樹的高度只比高度平衡的AVL樹的高度（log2n）僅僅大了一倍，在性能上，下降得并不多。這樣推導出來的結果不夠精確，實際上紅黑樹的性能更好

解答開篇：為什么都喜歡使用紅黑樹，而不是其他平衡二叉查找樹呢？

• AVL樹是一種高度平衡的二叉樹，所以查找的效率非常高，但是，有利就有弊，AVL樹為了維持這種高度的平衡，就要付出更多的代價。每次插入、刪除都要做調整，就比較復雜、耗時。所以，對于有頻繁的插入、刪除操作的數據集合，使用AVL樹的代價就有點高了。

• 紅黑樹只是做到了近似平衡，并不是嚴格的平衡，所以在維護平衡的成本上，要比AVL樹要低。

• 所以，紅黑樹的插入、刪除、查找各種操作性能都比較穩定。對于工程應用來說，要面對各種異常情況，為了支撐這種工業級的應用，我們更傾向于這種性能穩定的平衡二叉查找樹。

• 說白了，中庸就是最好的

課后思考：動態數據結構支持動態地數據插入、刪除、查找操作，除了紅黑樹，我們前面還學習過哪些呢？能對比一下各自的優勢、劣勢，以及應用場景嗎？

• 動態數據結構是支持動態的更新操作，里面存儲的數據是時刻在變化的，通俗一點講，它不僅僅支持查詢，還支持刪除、插入數據。而且，這些操作都非常高效。如果不高效，也就算不上是有效的動態數據結構了。所以，這里的紅黑樹算一個，支持動態的插入、刪除、查找，而且效率都很高。鏈表、隊列、棧實際上算不上，因為操作非常有限，查詢效率不高
• 散列表：插入刪除查找都是O(1), 是最常用的，但其缺點是不能順序遍歷以及擴容縮容的性能損耗。適用于那些不需要順序遍歷，數據更新不那么頻繁的。
• 跳表：插入刪除查找都是O(logn), 并且能順序遍歷。缺點是空間復雜度O(n)。適用于不那么在意內存空間的，其順序遍歷和區間查找非常方便。
• 紅黑樹：插入刪除查找都是O(logn), 中序遍歷即是順序遍歷，穩定。缺點是難以實現，去查找不方便。其實跳表更佳，但紅黑樹已經用于很多地方了

總結

以上是生活随笔為你收集整理的《数据结构与算法之美》21～25笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。