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

　　“你看這顆滿二叉樹”。

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

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

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

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

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

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

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

　　“紅黑樹！”

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

　?。╝ssociative array）

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

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

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

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

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

　　科勒文不明覺厲，豎起了大拇指。

　　“我突然有個想法”。

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

　　“反正還早著哪”。

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

　　“可以??！”

　　楊成表示贊成。

　　“怎么做呢？”