序
承接上文淺談大型網站的算法和架構（一） ，我們繼續聊我們的話題。
上文中很多人提到不扣題，這只是一部分資料，所以會感覺到不扣題，主要是題目太大了，而且內容太多了，我只能一部分一部分的寫出來，望大家見諒。
我們老大也只講到上，還有中和下呢！
上偏重于基礎部分——就是算法部分。里面包括現今架構中的產品使用的算法，讓我們了解產品本質的一些東西。需要到伸展樹這一篇開始才能真正講到相關架構產品。
中和下他還沒開始呢！估計也夠我研究一段時間了。大家就權當了解下算法吧！
二叉樹
上文中提到的兩個結構（數組和鏈表）各有弊端。
1》數組在更新的時候比較消耗資源，需要挨個挪動后面的元素。
2》而鏈表在查詢的時候需要從頭挨個對比之后選擇出要查詢的內容。
綜上我們需要一個查詢更快，更新更快的結構，于是我們有了二叉樹。
特點:每個結點最多有兩棵子樹。
找80
我們來看看代碼實踐:
讓我們運行起來看看
插入82
我們來看看代碼實踐（注意:在原有的代碼上加了一個方法insert_bit_tree):
讓我們運行起來看看
二叉樹的煩惱
我們不難發現如果在一個很極端的情況下，查找某個數據，那么會出現上圖的情況。你猜想一下，如果是幾千萬條數據，會出現什么情況呢?
由于上述原因，我們想到了平衡二叉樹，又叫AVL樹。
平衡二叉樹:AVL Tree(1962)
讓我們看看代碼實踐。
主要理解一下這段代碼
對該函數進行圖解。
由于篇幅太長，下篇將繼續介紹。
推薦
喜歡編程
浙公網安備 33010602011771號