第十八章 關(guān)聯(lián)數(shù)組

　　“你看這顆滿(mǎn)二叉樹(shù)”。

　　“假設(shè)它的高度為k，那么，它擁有的總節(jié)點(diǎn)數(shù)為：2^k-1”。

　　楊成邊走邊向科勒文介紹道。

　　這種樹(shù)每一層的元素?cái)?shù)量像這樣：1，2，4，8...

　　它是等比數(shù)列，其公比為2，首項(xiàng)為1，項(xiàng)數(shù)為k，所以能夠推導(dǎo)出來(lái)總數(shù)。

　　隨著他們深入二叉樹(shù)森林，越來(lái)越多奇形怪狀的樹(shù)出現(xiàn)在他們眼前。

　　其中，有一種樹(shù)，它的枝干上面紅黑相間，葉子全部都是黑色的。

　　“節(jié)點(diǎn)是紅色與黑色交替出現(xiàn)？”

　　“紅黑樹(shù)！”

　　楊成很快就認(rèn)出來(lái)了。

　　（associative array）

　　這種樹(shù)的應(yīng)用很廣，常常用來(lái)實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。

　　比如在Java中，TreeMap這個(gè)類(lèi)就是用紅黑樹(shù)作為底層實(shí)現(xiàn)的。

　　再比如JavaScript，它的對(duì)象本質(zhì)上就是一個(gè)關(guān)聯(lián)數(shù)組。

　　有意思的是，在論壇上，某些開(kāi)發(fā)者認(rèn)為，手打一棵紅黑樹(shù)出來(lái)能夠展現(xiàn)其技藝...

　　“哥們兒，你很棒棒喔！”

　　科勒文不明覺(jué)厲，豎起了大拇指。

　　“我突然有個(gè)想法”。

　　“植物學(xué)家”看了看四周。

　　“反正還早著哪”。

　　“不如，咋們來(lái)調(diào)查一下，這塊區(qū)域的二叉樹(shù)密度，怎么樣？”

　　“可以?。　?p>　　楊成表示贊成。

　　“怎么做呢？”