“嗨，阿米戈！”
“你好，瑞希！”
“我在那邊找到了我的舊筆記，給你準備了一些有趣的資料，我想你會感興趣的。”
“讓我們聽聽吧。你總能找到一些有趣的東西，後來證明它們非常有用。”
“好吧。今天我想給大家講講樹，所以我將從圖表開始。”
“圖是由點和連接它們的線組成的系統。點稱為圖的頂點，線稱為圖的邊。例如：”
“將圖用作各種現實世界過程和任務的數學模型非常方便。已經為圖發明了許多不同的任務和算法，因此它們被相當頻繁地使用。”
“例如，假設頂點是城市，邊是道路。那麼搜索城市之間的最短路線就變成了：«給定一個圖，找到兩個頂點之間的最短路徑»。 ”
“但是從 A 到 B 的路徑並不總是與從 B 到 A 的路徑相同。因此，有時有兩條不同的線是首選。為此，線（圖形的邊緣）被箭頭替換。在換句話說，圖形可以有兩個箭頭：一個從 A 到 B，另一個從 B 到 A。”
“如果圖形使用箭頭，則稱為有向圖；如果它只有線，則稱為無向圖。”
“每個頂點都可以有自己的邊數。一個頂點也可以根本沒有邊。相反，一個頂點可以通過邊連接到每個其他頂點。如果圖中的每對頂點都由一條邊連接， 則稱為完全圖。 ”
“如果你可以用邊到達圖中的每個頂點，那麼它就被稱為連通圖。具有三個獨立頂點且沒有邊的圖仍然是圖，但我們稱它為不連通圖。”
“要由 N 個頂點組成連通圖，至少需要 N-1 條邊。這種圖稱為樹。”
“此外，通常選擇一個頂點作為樹的根，其餘的頂點被聲明為分支。沒有自己分支的樹分支稱為葉子。例如：”
“如果樹的每個元素都有兩個孩子，那麼它就被稱為二叉樹。也就是說，可以有0個或2個分支。你可以在右上角看到一棵二叉樹。”
“當每個分支有 2 個孩子並且所有葉子（沒有孩子的頂點）都在同一行時，樹稱為完全二叉樹。”
“例如：”
“為什麼需要這些樹？”
“哦，樹的用處很多，一般來說，二叉樹就是排序好的結構化數據。”
“那是什麼？”
“是的，很簡單。我們在每個頂點中存儲一定的值。並且每個元素都遵循一個規則：右孩子中存儲的值必須大於頂點中存儲的值，左孩子中存儲的值必須小於存儲在頂點中的值。 這種排序可以快速找到所需的樹元素。”
“你能解釋一下這是什麼意思嗎？”
“樹元素通常是通過加法排序的，假設我們有7個元素：13、5、4、16、8、11、10”
“這是將元素添加到樹中的方式。”
“如果我們要在這棵樹中尋找數字 7，那麼這就是搜索的方式”
“0) 從根開始。”
“1a) 7 等於 13 嗎？不”
“1b) 7 是否大於 13？不，所以我們移動到左子樹。”
“2a) 7 等於 5 嗎？不。”
“2b) 7 是否大於 5？是的，所以我們移動到右子樹。”
“3a) 7 等於 8 嗎？不”
“3b) 7 是否大於 8？不，所以我們移動到左子樹。”
“4a) 沒有左子樹，這意味著數字 7 不在樹中。”
“啊，也就是說，我們只需要檢查從根到想要的數字所在位置的路徑上的頂點就可以了。嗯，確實很快。”
“而且，如果這棵樹是平衡的，那麼你只需要通過大約20個頂點就可以搜索到一百萬個元素。”
“我同意——那不是很多。”
“平衡樹是什麼意思？”
“一棵沒有扭曲的樹，即沒有長分支的樹。例如，如果我們在構建樹時已經對元素進行了排序，那麼我們就會製作一棵由一個分支組成的非常長的樹。 ”
“嗯。你說得對。那我們怎麼辦？”
“正如您可能已經猜到的那樣，最有效的樹的分支長度大致相同。然後每次比較都會丟棄剩餘子樹的最大部分。”
“所以，我們需要重建這棵樹？”
“是的。它需要“平衡”——盡可能接近完整的二叉樹。”
“為了解決這個問題，發明了自平衡樹。 如果樹在添加元素後變得扭曲，那麼它會稍微重新排列元素以使一切正常。 這是一個平衡的例子：”
“其中一些樹被稱為紅黑樹。”
“為什麼叫紅黑？”
“他們的發明者用兩種顏色繪製所有頂點。一種顏色是紅色，另一種顏色是黑色。不同的頂點遵循不同的規則。這構成了平衡程序的整個基礎。”
“例如：”
“那麼這些規則是什麼？”
“1) 紅色頂點不能是紅色頂點的子頂點。”
“2）每片葉子的黑色深度都一樣（黑色深度是指從根開始的路徑上黑色頂點的個數）。”
“3）樹的根是黑色的。”
“我不會解釋它是如何工作的——你的腦袋可能已經爆炸了。”
“是的。我的處理器冒煙了。”
“這是給你的鏈接。如果你願意，你可以在這裡閱讀更多相關信息。”
“現在，去休息一下。”
GO TO FULL VERSION