序

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

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

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

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

中和下他還沒開始呢！估計(jì)也夠我研究一段時(shí)間了。大家就權(quán)當(dāng)了解下算法吧！

二叉樹

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

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

2》而鏈表在查詢的時(shí)候需要從頭挨個(gè)對(duì)比之后選擇出要查詢的內(nèi)容。

綜上我們需要一個(gè)查詢更快，更新更快的結(jié)構(gòu)，于是我們有了二叉樹。

特點(diǎn):

每個(gè)結(jié)點(diǎn)最多有兩棵子樹。

找80

我們來(lái)看看代碼實(shí)踐:

[[94946]]讓我們運(yùn)行起來(lái)看看

插入82

我們來(lái)看看代碼實(shí)踐（注意:在原有的代碼上加了一個(gè)方法insert_bit_tree):

[[94946]]讓我們運(yùn)行起來(lái)看看

#p#

二叉樹的煩惱

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

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

平衡二叉樹:AVL Tree(1962)

讓我們看看代碼實(shí)踐。

主要理解一下這段代碼　

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

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