序

承接上文淺談大型網站的算法和架構（一） ，我們繼續(xù)聊我們的話題。

上文中很多人提到不扣題，這只是一部分資料，所以會感覺到不扣題，主要是題目太大了，而且內容太多了，我只能一部分一部分的寫出來，望大家見諒。

我們老大也只講到上，還有中和下呢！

上偏重于基礎部分——就是算法部分。里面包括現(xiàn)今架構中的產品使用的算法，讓我們了解產品本質的一些東西。需要到伸展樹這一篇開始才能真正講到相關架構產品。

中和下他還沒開始呢！估計也夠我研究一段時間了。大家就權當了解下算法吧！

二叉樹

上文中提到的兩個結構（數(shù)組和鏈表）各有弊端。

1》數(shù)組在更新的時候比較消耗資源，需要挨個挪動后面的元素。

2》而鏈表在查詢的時候需要從頭挨個對比之后選擇出要查詢的內容。

綜上我們需要一個查詢更快，更新更快的結構，于是我們有了二叉樹。

特點:

每個結點最多有兩棵子樹。

找80

我們來看看代碼實踐:

[[94946]]讓我們運行起來看看

插入82

我們來看看代碼實踐（注意:在原有的代碼上加了一個方法insert_bit_tree):

[[94946]]讓我們運行起來看看

#p#

二叉樹的煩惱

我們不難發(fā)現(xiàn)如果在一個很極端的情況下，查找某個數(shù)據(jù)，那么會出現(xiàn)上圖的情況。你猜想一下，如果是幾千萬條數(shù)據(jù)，會出現(xiàn)什么情況呢?

由于上述原因，我們想到了平衡二叉樹，又叫AVL樹。

平衡二叉樹:AVL Tree(1962)

讓我們看看代碼實踐。

主要理解一下這段代碼　

[[94946]]對該函數(shù)進行圖解。

原文鏈接：http://www.cnblogs.com/baochuan/archive/2012/10/08/2713700.html