引出

1.B樹，階M，數(shù)據(jù)樹葉上，根的兒子數(shù)在2和M之間，除根外，非樹葉節(jié)點兒子為M/2和M之間；
2.B樹的插入引起分裂，B樹的刪除，引起合并和領(lǐng)養(yǎng)；
3.紅黑樹，根是黑的，紅色節(jié)點的兒子必須是黑的，所有路徑的黑色節(jié)點數(shù)相同；
4.紅黑樹的插入，顏色翻轉(zhuǎn)，單旋轉(zhuǎn)，插入節(jié)點定顏色；
5.java標(biāo)準(zhǔn)庫的set和map，使用紅黑樹；

B樹

迄今為止，我們始終假設(shè)可以把整個數(shù)據(jù)結(jié)構(gòu)存儲到計算機(jī)的主存中。可是，如果數(shù)據(jù)更多裝不下主存，那么這就意味著必須把數(shù)據(jù)結(jié)構(gòu)放到磁盤上。此時，因為大O模型不再適用，所以導(dǎo)致游戲規(guī)則發(fā)生了變化。

在磁盤上，典型的查找樹執(zhí)行如下：設(shè)想要訪問佛羅里達(dá)州公民的駕駛記錄。假設(shè)有1千萬項，每一個關(guān)鍵字是32字節(jié)（代表一個名字），而一個記錄是256個字節(jié)。假設(shè)這些數(shù)據(jù)不能都裝人主存，而我們是正在使用系統(tǒng)的20個用戶中的一個（因此有1/20的資源）。這樣，在1秒內(nèi)，我們可以執(zhí)行2500萬次指令，或者執(zhí)行6次磁盤訪問。

不平衡的二叉查找樹是一個災(zāi)難。在最壞情形下它具有線性的深度，從而可能需要1千萬次磁盤訪問。平均來看，一次成功的查找可能需要1.381ogN次磁盤訪問，由于10g10000000≈24，因此平均一次查找需要32次磁盤訪問，或5秒的時間。在一棵典型的隨機(jī)構(gòu)造的樹中，我們預(yù)料會有一些節(jié)點的深度要深3倍；它們需要大約100次磁盤訪問，或16秒的時間。

AVL樹多少要好一些。1.44logN的最壞情形不可能發(fā)生，典型的情形是非常接近于logN。這樣，一棵AVL樹平均將使用大約25次磁盤訪問，需要的時間是4秒。

我們想要把磁盤訪問次數(shù)減小到一個非常小的常數(shù)，比如3或4：而且我們愿意寫一個復(fù)雜的程序來做這件事，因為在合理情況下機(jī)器指令基本上是不占時間的。由于典型的AVL樹接近到最優(yōu)的高度，因此應(yīng)該清楚的是，二叉查找樹是不可行的。使用二叉查找樹我們不能行進(jìn)到低于logN。解法直覺上看是簡單的：如果有更多的分支，那么就有更少的高度

。這樣，31個節(jié)點的理想二叉樹(perfect binary tree)有5層，而31個節(jié)點的5叉樹則只有3層，如圖4-59所示一棵M叉查找樹(M-ary search tree)可以有M路分支。隨著分支增加，樹的深度在減少。一棵完全二叉樹(complete binary tree)的高度大約為logN,而一棵完全M叉樹(complete M-ary tree) 的高度大約是logm N。

我們可以以與建立二叉查找樹大致相同的方式建立M叉查找樹。在二叉查找樹中，需要一個關(guān)鍵字來決定兩個分支到底取用哪個分支；而在M叉查找樹中需要M1個關(guān)鍵字來決定選取哪個分支。為使這種方案在最壞的情形下有效，需要保證M叉查找樹以某種方式得到平衡。否則，像二叉查找樹，它可能退化成一個鏈表。實際上，我們甚至想要更加限制性的平衡條件，即
不想要M叉查找樹退化到甚至是二叉查找樹，因為那時我們又將無法擺脫logN次訪問了。

B+樹、B樹

圖4-60顯示5階B樹的一個例子。注意，所有的非葉節(jié)點的兒子數(shù)都在3和5之間（從而有2到4個關(guān)鍵字)；根可能只有兩個兒子。這里，我們有L=5(在這個例子中L和M恰好是相同的，但這不是必需的)。由于L是5，因此每片樹葉有3到5個數(shù)據(jù)項。要求節(jié)點半滿將保證B樹不致退化成簡單的二叉樹。雖然存在改變該結(jié)構(gòu)的各種B樹的定義，但大部分在一些次要的細(xì)節(jié)上變化，而我們這個定義是流行的形式之一。

插入insert

我們首先考查插入。設(shè)想要把57插人到圖4-60的B樹中。沿樹向下查找揭示出它不在樹中。此時我們把它作為第5項添加到樹葉中。注意我們可能要為此重新組織該樹葉上的所有數(shù)據(jù)。然而，與磁盤訪問相比（在這種情況下它還包含一次磁盤寫），這項操作的開銷可以忽略不計。

當(dāng)然，這是相對簡單的，因為該樹葉還沒有被裝滿。設(shè)現(xiàn)在要插入55。圖4-61顯示一個問題：55想要插入其中的那片樹葉已經(jīng)滿了。不過解法卻不復(fù)雜：由于我們現(xiàn)在有L+1項，因此把它們分成兩片樹葉，這兩片樹葉保證都有所需要的記錄的最小個數(shù)。我們形成兩片樹葉，每葉3項。寫這兩片樹葉需要2次磁盤訪問，更新它們的父節(jié)點需要第3次磁盤訪問。注意，在父節(jié)點中關(guān)鍵字和分支均發(fā)生了變化，但是這種變化是以容易計算的受控的方式處理的。最后得到的B樹在圖4-62中給出。雖然分裂節(jié)點是耗時的，因為它至少需要2次附加的磁盤寫，但它相對很少發(fā)生。

例如，如果L是32，那么當(dāng)節(jié)點被分裂時，具有16和17項的兩片樹葉分別被建立。對于有17項的那片樹葉，我們可以再執(zhí)行15次插入而不用另外的分裂。換句話說，對于每次分裂，大致存在L/2次非分裂的插人。

前面例子中的節(jié)點分裂之所以行得通是因為其父節(jié)點的兒子個數(shù)尚未滿員?？墒?，如果滿員了又會怎樣呢？例如，假設(shè)我們想要把40插入到圖4-62的B樹中。此時必須把包含關(guān)鍵字35到39而現(xiàn)在又要包含40的樹葉分裂成2片樹葉。但是這將使父節(jié)點有6個兒子，可是它只能有5個兒子。因此，解法就要分裂這個父節(jié)點。結(jié)果在圖4-63中給出。當(dāng)父節(jié)點被分裂時，必須更新那些關(guān)鍵字以及還有父節(jié)點的父親的值，這樣就招致額外的兩次磁盤寫（從而這次插入花費5次磁盤寫)。然而，雖然由于有大量的情況要考慮而使得程序確實不那么簡單，但是這些關(guān)鍵字還是以受控的方式變化。

正如這里的情形所示，當(dāng)一個非葉節(jié)點分裂時，它的父節(jié)點得到了一個兒子。如果父節(jié)點的兒子個數(shù)已經(jīng)達(dá)到規(guī)定的限度怎么辦呢？在這種情況下，繼續(xù)沿樹向上分裂節(jié)點直到找到一個不需要再分裂的父節(jié)點，或者到達(dá)樹根。

如果分裂樹根，那么我們就得到兩個樹根。顯然這是不可接受的，但我們可以建立一個新的根，這個根以分裂得到的兩個樹根作為它的兩個兒子。

這就是為什么準(zhǔn)許樹根可以最少有兩個兒子的特權(quán)的原因。這也是B樹增加高度的唯一方式。不用說，一路向上分裂直到根的情況是一種特別少見的異常事件，因為一棵具有4層的樹意味著在整個插入序列中已經(jīng)被分裂了3次（假設(shè)沒有刪除發(fā)生）。

事實上，任何非葉節(jié)點的分裂也是相當(dāng)少見的。還有其他一些方法處理兒子過多的情況。一種方法是在相鄰節(jié)點有空間時把一個兒子交給該鄰節(jié)點領(lǐng)養(yǎng)。例如，為了把29插入到圖4-63的B樹中，可以把32移到下一片樹葉而騰出一個空間。這種方法要求對父節(jié)點進(jìn)行修改，因為有些關(guān)鍵字受到了影響。然而，它趨向于使得節(jié)點更滿，從而在長時間運行中節(jié)省空間。

刪除remove

我們可以通過查找要刪除的項并在找到后刪除它來執(zhí)行刪除操作。

問題在于，如果被刪元所在的樹葉的數(shù)據(jù)項數(shù)已經(jīng)是最小值，那么刪除后它的項數(shù)就低于最小值了。我們可以通過在鄰節(jié)點本身沒有達(dá)到最小值時領(lǐng)養(yǎng)一個鄰項來矯正這種狀況。如果相鄰結(jié)點已經(jīng)達(dá)到最小值，那么可以與該相鄰節(jié)點聯(lián)合以形成一片滿葉?？墒牵@意味著其父節(jié)點失去一個兒子。如果失去兒子的結(jié)果又引起父節(jié)點的兒子數(shù)低于最小值，那么我們使用相同的策略繼續(xù)進(jìn)行。這個過程可以一直上行到根。根不可能只有一個兒子（要是允許根有一個兒子那可就愚蠢了）。如果這個領(lǐng)養(yǎng)過程的結(jié)果使得根只剩下一個兒子，那么刪除該根并讓它的這個兒子作為樹的新根。這是B樹降低高度的唯一的方式。

例如，假設(shè)我們想要從圖4-63的B樹中刪除99。由于那片樹葉只有兩項而它的鄰居已經(jīng)是最小值3項了，因此我們把這些項合并成有5項的一片新的樹葉。結(jié)果，它們的父節(jié)點只有兩個兒子了。這時該父節(jié)點可以從它的鄰節(jié)點領(lǐng)養(yǎng)，因為鄰節(jié)點有4個兒子。領(lǐng)養(yǎng)的結(jié)果使得雙方都有3個兒子，結(jié)果如圖4-64所示。

紅黑樹(red black tree)

歷史上AVL樹流行的另一變種是紅黑樹(red black tree)。對紅黑樹的操作在最壞情形下花費O(logN)時間，而且我們將看到，（對于插入操作的）一種審慎的非遞歸實現(xiàn)可以相對容易地完成（與AVL樹相比）。

紅黑樹是具有下列著色性質(zhì)的二叉查找樹：
1.每一個節(jié)點或者著成紅色，或者著成黑色。
2.根是黑色的。
3.如果一個節(jié)點是紅色的，那么它的子節(jié)點必須是黑色的。
4.從一個節(jié)點到一個null引用的每一條路徑必須包含相同數(shù)目的黑色節(jié)點。

著色法則的一個結(jié)論是，紅黑樹的高度最多是2log(N+1)。因此，查找操作保證是一種對數(shù)的操作。

自底向上的插入

前面已經(jīng)提到，如果新插入的項的父節(jié)點是黑色，那么插入完成。因此，將25插入到圖12-9的樹中是簡單的操作。

如果父節(jié)點是紅色的，那么有幾種情形（每種都有一個鏡像對稱）需要考慮。首先，假設(shè)這個父節(jié)點的兄弟是黑色的（我們采納約定：u11節(jié)點都是黑色的）。這對于插人3或8是適用的，但對插入99不適用。令X是新添加的樹葉，P是它的父節(jié)點，S是該父節(jié)點的兄弟（若存在)，G是祖父節(jié)點。在這種情形只有X和P是紅色的，G是黑色的，否則就會在插入前有兩個相連的紅色節(jié)點，違反了紅黑樹的法則。采用伸展樹的術(shù)語，X,P和G可以形成一個一字形鏈或之字形鏈（兩個方向中的任一個方向）。

圖12-10指出當(dāng)P是一個左兒子時（注意有一個對稱情形)我們應(yīng)該如何旋轉(zhuǎn)該樹。即使X是一片樹葉，我們還是畫出較一殷的情形，使得X在樹的中間。后面我們將用到這個較一般的旋轉(zhuǎn)。

自頂向下紅黑樹

上濾的實現(xiàn)需要用一個?；蛴靡恍└告湵４媛窂?。我們看到，如果使用一個自頂向下的過程，則伸展樹會更有效，事實上我們可以對紅黑樹應(yīng)用自頂向下的過程而保證S不會是紅色的。

這個過程在概念上是容易的。在向下的過程中當(dāng)看到一個節(jié)點X有兩個紅兒子的時候，可使X呈紅色而讓它的兩個兒子是黑的。（如果X是根，則在顏色翻轉(zhuǎn)后它將是紅色，但是為恢復(fù)性質(zhì)2可以直接著成黑色)

圖12-11顯示這種顏色翻轉(zhuǎn)的現(xiàn)象，只有當(dāng)X的父節(jié)點P也是紅的時候這種翻轉(zhuǎn)將破壞紅黑的法則。但是此時可以應(yīng)用圖12-10中適當(dāng)?shù)男D(zhuǎn)。如果X的父節(jié)點的兄弟是紅色會如何呢？這種可能已經(jīng)被從頂向下過程中的行動所排除，因此X的父節(jié)點的兄弟不可能是紅色！

特別地，如果在沿樹向下的過程中我們看到一個節(jié)點Y有兩個紅兒子，那么我們知道Y的孫子必然是黑的，由于Y的兒子也要變成黑的，甚至在可能發(fā)生的旋轉(zhuǎn)之后，因此我們將不會看到兩層上另外的紅節(jié)點。這樣，當(dāng)我們看到X,若X的父節(jié)點是紅的，則X的父節(jié)點的兄弟不可能也是紅色的。

例如，假設(shè)要將45插入到圖12-9中的樹上。在沿樹向下的過程中，我們看到50有兩個紅兒子。因此，我們執(zhí)行一次顏色翻轉(zhuǎn)，使50為紅的，40和55是黑的。現(xiàn)在50和60都是紅的。在60和70之間執(zhí)行單旋轉(zhuǎn)，使得60是30的右子樹的黑根，而70和50都是紅的。如果我們在路徑上看到另外的含有兩個紅兒子的節(jié)點，那么我們繼續(xù)執(zhí)行同樣的操作。當(dāng)我們到達(dá)樹葉時，把45作為紅節(jié)點插入，由于父節(jié)點是黑的，因此插入完成。最后得到如圖12-12所示的樹。

如圖12-12所示，所得到的紅黑樹常常平衡得很好。經(jīng)驗指出，平均紅黑樹大約和平均AVL樹一樣深，從而查找時間一般接近最優(yōu)。紅黑樹的優(yōu)點是執(zhí)行插入所需要的開銷相對較低，另外就是實踐中發(fā)生的旋轉(zhuǎn)相對較少。

自頂向下的刪除

紅黑樹中的刪除也可以自頂向下進(jìn)行。每一件工作都?xì)w結(jié)于能夠刪除樹葉。這是因為，要刪除一個帶有兩個兒子的節(jié)點，用右子樹上的最小節(jié)點代替它；該節(jié)點必然最多有一個兒子，然后將該節(jié)點刪除。只有一個右兒子的節(jié)點可以用相同的方式刪除，而只有一個左兒子的節(jié)點通過用其左子樹上最大節(jié)點替換而被刪除，然后再將該節(jié)點刪除。注意，對于紅黑樹，我們不要使用繞過帶有一個兒子的節(jié)點的情形的方法，因為這可能在樹的中部連接兩個紅色節(jié)點，增加紅黑條件實現(xiàn)的困難。

當(dāng)然，紅色樹葉的刪除很簡單。然而，如果一片樹葉是黑的，那么刪除操作會復(fù)雜得多，因為黑色節(jié)點的刪除將破壞條件4。解決方法是保證從上到下刪除期間樹葉是紅的。在整個討論中，令X為當(dāng)前節(jié)點，T是它的兄弟，而P是它們的父親。開始時我們把樹的根涂成紅色。當(dāng)沿樹向下遍歷時，我們設(shè)法保證X是紅色的。當(dāng)?shù)竭_(dá)一個新的節(jié)點時，我們要確信P是紅的（歸納地，我們試圖繼續(xù)保持這種不變性）并且X和T是黑的（因為不能有兩個相連的紅色節(jié)點)。這存在兩種主要的情形。首先，設(shè)X有兩個黑兒子。

此時有三種子情況，如圖12-17所示。如果T也有兩個黑兒子，那么可以翻轉(zhuǎn)X、T和P的顏色來保持這種不變性。否則，T的兒子之一是紅的。根據(jù)這個兒子節(jié)點是哪一個，我們可以應(yīng)用圖12-17所示的第二和第三種情形表示的旋轉(zhuǎn)。特別要注意，這種情形對于樹葉將是適用的，因為nul1Node被認(rèn)為是黑的。

其次，X的兒子之一是紅的。在這種情形下，我們落到下一層上，得到新的X、T和P。如果幸運，X落在紅兒子上，則我們可以繼續(xù)向前進(jìn)行。如果不是這樣，那么我們知道T將是紅的，而X和P將是黑的。我們可以旋轉(zhuǎn)T和P,使得X的新父親是紅的；當(dāng)然X及其祖父將是黑的。'此時我們可以回到第一種主情況。

標(biāo)準(zhǔn)庫中的集合Set與映射Map

List容器即ArrayList和LinkedList用于查找效率很低。因此，Collections API提供了兩個附加容器Set和Map,它們對諸如插入、刪除和查找等基本操作提供有效的實現(xiàn)。

關(guān)于Set接口

Set接口代表不允許重復(fù)元的Collection。由接口SortedSet給出的一種特殊類型的Set保證其中的各項處于有序的狀態(tài)。因為一個Set IS-A Collection,所以用于訪問繼承Collection的list的項的方法也對Set有效。

由Set所要求的一些獨特的操作是一些插入、刪除以及（有效地）執(zhí)行基本查找的能力。對于Set,add方法如果執(zhí)行成功則返回true,否則返回false,因為被添加的項已經(jīng)存在。保持各項以有序狀態(tài)的Set的實現(xiàn)是TreeSet。TreeSet類的基本操作花費對數(shù)最壞情形時間。

關(guān)于Map接口

Map是一個接口，代表由關(guān)鍵字以及它們的值組成的一些項的集合。關(guān)鍵字必須是唯一的，但是若干關(guān)鍵字可以映射到一些相同的值。因此，值不必是唯一的。在SortedMap接口中，映射中的關(guān)鍵字保持邏輯上有序狀態(tài)。SortedMap接口的一種實現(xiàn)是TreeMap類。Map的基本操作包括諸如isEmpty、clear、size等方法，而且最重要的是包含下列方法：

get返回Map中與key相關(guān)的值，或當(dāng)key不存在時返回null。如果在Map中不存在null值，那么由get返回的值可以用來確定key是否在Map中。然而，如果存在nul1值，那么必須使用containsKey。方法put把關(guān)鍵字/值對置入Map中，或者返回null,或者返回與key相聯(lián)系的老值。

通過一個Map進(jìn)行迭代要比Collection復(fù)雜，因為Map不提供迭代器，而是提供3種方法，將Map對象的視圖作為Collection對象返回。由于這些視圖本身就是Collection,因此它們可以被迭代。所提供的3種方法如下：

方法keySet和values返回簡單的集合（這些關(guān)鍵字不包含重復(fù)元，因此以一個Set對象的形式返回)。這里的entrySet方法是作為一些項而形成的Set對象被返回的（由于關(guān)鍵字是唯一的，因此不存在重復(fù)項)。每一項均由被嵌套的接口Map.Entry表示。對于類型Map.Entry的對象，其現(xiàn)有的方法包括訪問關(guān)鍵字、關(guān)鍵字的值，以及改變關(guān)鍵字的值：

TreeSet類和TreeMap類的實現(xiàn)

Java要求TreeSet和TreeMap支持基本的add、remove和contains操作以對數(shù)最壞情形時間完成。因此，基本的實現(xiàn)方法就是平衡二叉查找樹。一般說來，我們并不使用AVL樹，而是經(jīng)常使用一些自頂向下的紅黑樹。

實現(xiàn)TreeSet和TreeMap的一個重要問題是提供對迭代器類的支持。當(dāng)然，在內(nèi)部，迭代器保留到迭代中“當(dāng)前”節(jié)點的一個鏈接。困難部分是到下一個節(jié)點高效的推進(jìn)。存在幾種可能的解決方案，其中的一些方案敘述如下：

1.在構(gòu)造迭代器時，讓每個迭代器把包含諸TreeSet項的數(shù)組作為該迭代器的數(shù)據(jù)存儲。這有不足，因為我們還可以使用toArray,并不需要迭代器。

2.讓迭代器保留存儲通向當(dāng)前節(jié)點的路徑上的節(jié)點的一個棧。根據(jù)該信息，可以推出迭代器中的下一個節(jié)點，它或者是包含最小項的當(dāng)前節(jié)點右子樹上的節(jié)點，或者包含其左子樹當(dāng)前節(jié)點的最近的祖先。這使得迭代器多少有些大，并導(dǎo)致迭代器的代碼臃腫。

3.讓查找樹中的每個節(jié)點除存儲子節(jié)點外還要存儲它的父節(jié)點。此時迭代器不至于那么大，但是在每個節(jié)點上需要額外的內(nèi)存，并且迭代器的代碼仍然臃腫。

4.讓每個節(jié)點保留兩個附加的鏈：一個通向下一個更小的節(jié)點，另一個通向下一個更大的節(jié)點。這要占用空間，不過迭代器做起來非常簡單，并且保留這些鏈也很容易。

5.只對那些具有nu11左鏈或nul1右鏈的節(jié)點保留附加的鏈。通過使用附加的布爾變量使得這些例程判斷是一個左鏈正在被用作標(biāo)準(zhǔn)的二叉樹左鏈還是一個通向下一個更小節(jié)點的鏈，類似地，對右鏈也有類似的判斷。這種做法叫作線索樹(threaded tree),用于許多平衡二叉查找樹的實現(xiàn)中。

使用多個映射Map：一個詞典的案例

許多單詞都和另外一些單詞相似。例如，通過改變第1個字母，單詞wine可以變成dine、fine、line、mine、nine、pine或vine通過改變第3個字母，wine可以變成wide、wife、wipe或wire。通過改變第4個字母wine可以變成wind、wing、wink或wins。這樣我們就得到l5個不同的單詞，它們僅僅通過改變wine中的一個字母而得到。實際上，存在20多個不同的單詞，其中有些單詞更生僻。我們想要編寫一個程序以找出通過單個字母的替換可以變成至少15個其他單詞的單詞。

假設(shè)我們有一個詞典，由大約89000個不同長度的不同單詞組成。大部分單詞在6~11個字母之間。其中6字母單詞有8205個，7字母單詞有11989個，8字母單詞13672個，9字母單詞13014個，10字母單詞11297個，11字母單詞8617個（實際上，最可變化的單詞是3字母、4字母和5字母單詞，不過，更長的單詞檢查起來更耗費時間)。

方案一：使用一個Map對象

最直接了當(dāng)?shù)牟呗允鞘褂靡粋€Map對象，其中的關(guān)鍵字是單詞，而關(guān)鍵字的值是用1字母替換能夠從關(guān)鍵字變換得到的一列單詞。

該算法的問題在于速度慢，在我們的計算機(jī)上花費75秒的時間。一個明顯的改進(jìn)是避免比較不同長度的單詞。我們可以把單詞按照長度分組，然后對各個分組運行剛才提供的程序。為此，可以使用第2個映射！此時的關(guān)鍵字是個整數(shù)，代表單詞的長，而值則是該長度的所有單詞的集合。我們可以使用一個List存儲每個集合，然后應(yīng)用相同的做法。程序所示。第9行是第2個Map的聲明，第13行和第14行將分組置入該Map,然后用一個附加的循環(huán)對每組單詞迭代。與第1個算法比較，第2個算法只是在邊際上編程困難，其運行時間為16秒，大約快了5倍。

package com.tianju.book.jpa.mapLearn;

import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;

public class WordDemo {
    private static List<String> wordList = Arrays.asList(
            "wine", "dine", "fine", "line", "mine", "nine", "pine", "vine", "wide",
            "wife", "wipe", "wire", "wind", "wing", "wink", "wins");


    /**
     * 當(dāng)兩個單詞長度相等，并且只有1個字母不同時返回true
     */
    private static boolean isOneCharDiff(String word1,String word2){
        if (word2.length()!=word1.length()){
            return false; // 長度不同，返回false
        }
        int diff = 0;
        for (int i=0;i<word1.length();i++){
            if (word1.charAt(i)!=word2.charAt(i)){
                if (diff>1){
                    return false;
                }
                diff = diff +1;
            }
        }
        return diff == 1;
    }


    // {mine=[wine, dine, fine, line, nine, pine, vine], wins=[wine, wind, wing, wink],

    /**
     * 自己實現(xiàn)的方式，比大佬的要多一半的循環(huán)次數(shù)
     * getAdjWords方法的for循環(huán)次數(shù)：96
     * computeAdjacentWordsSlow方法的for循環(huán)次數(shù)：48
     * @param words
     * @return
     */
    public static Map<String,List<String>> getAdjWords(List<String> words){
        Map<String,List<String>> adjMap = new HashMap<>();
        int forTimes = 0;
        for (int i=0;i<words.size();i++){
            for (int j=0;j<words.size();j++){
//                System.out.println(words.get(i) + "--" + words.get(j));
                if (isOneCharDiff(words.get(i), words.get(j))){ // 只有一個單詞不同
                    List<String> stringList = adjMap.get(words.get(i));
                    if (stringList==null){
                        stringList = new ArrayList<>();
                        adjMap.put(words.get(i),stringList);
                    }
                    stringList.add(words.get(j));
                    forTimes++;
                }
            }
        }
        System.out.println("getAdjWords方法的for循環(huán)次數(shù)："+forTimes);
        return adjMap;
    }


    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses a quadratic algorithm (with appropriate Map).
    public static Map<String,List<String>> computeAdjacentWordsSlow( List<String> theWords )
    {
        Map<String,List<String>> adjWords = new HashMap<>( );

        String [ ] words = new String[ theWords.size( ) ];

        int forTimes = 0;
        theWords.toArray( words );
        for( int i = 0; i < words.length; i++ )
            for( int j = i + 1; j < words.length; j++ )
                if( isOneCharDiff( words[ i ], words[ j ] ) )
                {
                    update( adjWords, words[ i ], words[ j ] );
                    update( adjWords, words[ j ], words[ i ] );
                    forTimes++;
                }

        System.out.println("computeAdjacentWordsSlow方法的for循環(huán)次數(shù)："+forTimes);
        return adjWords;
    }

    private static <KeyType> void update( Map<KeyType,List<String>> m, KeyType key, String value )
    {
        List<String> lst = m.get( key );
        if( lst == null )
        {
            lst = new ArrayList<>( );
            m.put( key, lst );
        }
        lst.add( value );
    }



    public static void main(String[] args) {
        /**
         * 第一種方式，把單詞作為鍵，把只需要變換1個單詞就能得到新單詞的所有單詞的List作為該鍵的值
         */
        System.out.println(isOneCharDiff("dog", "dop"));
        Map<String, List<String>> adjWords = getAdjWords(wordList);
        System.out.println(adjWords);
        Map<String, List<String>> listMap = computeAdjacentWordsSlow(wordList);
        System.out.println(listMap);
    }
}

方案二：按照長度分組

一個明顯的改進(jìn)是避免比較不同長度的單詞。我們可以把單詞按照長度分組，然后對各個分組運行剛才提供的程序。為此，可以使用第2個映射！此時的關(guān)鍵字是個整數(shù)，代表單詞的長，而值則是該長度的所有單詞的集合。我們可以使用一個List存儲每個集合，然后應(yīng)用相同的做法。程序所示。第9行是第2個Map的聲明，第13行和第14行將分組置入該Map,然后用一個附加的循環(huán)對每組單詞迭代。與第1個算法比較，第2個算法只是在邊際上編程困難，其運行時間為16秒，大約快了5倍。

package com.tianju.book.jpa.mapLearn;

import java.util.*;

public class WordDemo2 {
    private static List<String> wordList = Arrays.asList(
            "wine", "dine", "fine", "line", "mine", "nine", "pine", "vine", "wide",
            "wife", "wipe", "wire", "wind", "wing", "wink", "wins");



    /**
     * 當(dāng)兩個單詞長度相等，并且只有1個字母不同時返回true
     */
    private static boolean isOneCharDiff(String word1,String word2){
        if (word2.length()!=word1.length()){
            return false; // 長度不同，返回false
        }
        int diff = 0;
        for (int i=0;i<word1.length();i++){
            if (word1.charAt(i)!=word2.charAt(i)){
                if (diff>1){
                    return false;
                }
                diff = diff +1;
            }
        }
        return diff == 1;
    }

    /**
     * 把單詞按照長度進(jìn)行分組
     */

    public static Map<String,List<String>> getAdjWords(List<String> wordList){
        Map<String,List<String>> adjMap = new HashMap<>();

        // 先按照單詞長度進(jìn)行分組
        Map<Integer,List<String>> wordsByLength = new HashMap<>( );
        for (String word:wordList) {
            List<String> lst = wordsByLength.get(word.length());
            if (lst==null){
                lst = new ArrayList<>();
                wordsByLength.put(word.length(), lst);
            }
            lst.add(word);
        }
        System.out.println(wordsByLength);

        // 獲得分組之后的單詞再進(jìn)行操作，對每組單詞進(jìn)行迭代，避免對比不同長度的單詞
        for (List<String> groupWords:wordsByLength.values()){
            int forTimes = 0;
            System.out.println(groupWords);
            List<String> words = groupWords;
            for (int i=0;i<words.size();i++){
                for (int j =i+1;j<words.size();j++){
                    if (isOneCharDiff(words.get(i), words.get(j))){
                        update(adjMap, words.get(i), words.get(j));
                        update(adjMap,words.get(j),words.get(i));
                        forTimes++;
                    }
                }
            }
            System.out.println("forTime: "+forTimes);
        }
        return adjMap;
    }

    private static <KeyType> void update( Map<KeyType,List<String>> m, KeyType key, String value )
    {
        List<String> lst = m.get( key );
        if( lst == null )
        {
            lst = new ArrayList<>( );
            m.put( key, lst );
        }
        lst.add( value );
    }


    public static void main(String[] args) {
        System.out.println(getAdjWords(wordList));


    }
}

方案三：按照多個字母分組

第3個算法更復(fù)雜，使用一些附加的映射！和前面一樣，將單詞按照長度分組，然后分別對每組運算。

為理解這個算法是如何工作的，假設(shè)我們對長度為4的單詞操作。這時，首先要找出像wine和nine這樣的單詞對，它們除第1個字母外完全相同。

對于長度為4的每一個單詞，一種做法是刪除第1個字母，留下一個3字母單詞代表。這樣就形成一個M即，其中的關(guān)鍵字為這種代表，而其值是所有包含同一代表的單詞的一個List。例如，在考慮4字母單詞組的第1個字母時，代表“ine”對應(yīng)“dine”“fine”“wine”“nine”“mine”“vine”“pine”“l(fā)ine”。代表“oot”對應(yīng)“boot”“foot”“hoot”“l(fā)oot”“soot”“zoot”。

每一個作為最后的Map的一個值的List對象都形成單詞的一個集團(tuán)，其中任何一個單詞均可以通過單字母替換變成另一個單詞，因此在這個最后的Map構(gòu)成之后，很容易遍歷它以及添加一些項到正在計算的原始Map中。然后，我們使用一個新的Map再處理4字母單詞組的第2個字母。此后是第3個字母，最后處理第4個字母。

代碼初步理解

package com.tianju.book.jpa.mapLearn;

import java.util.*;

public class WordDemo3 {
    private static List<String> wordList = Arrays.asList(
            "wine", "dine", "fine", "line", "mine", "nine", "pine", "vine", "wide",
            "wife", "wipe", "wire", "wind", "wing", "wink", "wins");


    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses an efficient algorithm that is O(N log N) with a TreeMap, or
    // O(N) if a HashMap is used.
    public static Map<String,List<String>> computeAdjacentWords( List<String> words )
    {
        Map<String,List<String>> adjWords = new TreeMap<>( );
        Map<Integer,List<String>> wordsByLength = new TreeMap<>( );

        // Group the words by their length
        for( String w : words )
            update( wordsByLength, w.length( ), w );

        // Work on each group separately
        for( Map.Entry<Integer,List<String>> entry : wordsByLength.entrySet( ) )
        {
            List<String> groupsWords = entry.getValue( );
            int groupNum = entry.getKey( );

            // Work on each position in each group
            for( int i = 0; i < groupNum; i++ )
            {
                // Remove one character in specified position, computing representative.
                // Words with same representative are adjacent, so first populate
                // a map
                Map<String,List<String>> repToWord = new HashMap<>( );
                for( String str : groupsWords )
                {
                    String rep = str.substring( 0, i ) + str.substring( i + 1 );
                    update( repToWord, rep, str );
                }
                // and then look for map values with more than one string
                for( List<String> wordClique : repToWord.values( ) )
                    if( wordClique.size( ) >= 2 )
                        for( String s1 : wordClique )
                            for( String s2 : wordClique )
                                if( s1 != s2 )  // must be same string; equals not needed
                                    update( adjWords, s1, s2 );
            }
        }
        return adjWords;
    }

    private static <KeyType> void update( Map<KeyType,List<String>> m, KeyType key, String value )
    {
        List<String> lst = m.get( key );
        if( lst == null )
        {
            lst = new ArrayList<>( );
            m.put( key, lst );
        }

        lst.add( value );
    }


    public static void main(String[] args) {
        Map<String, List<String>> map = computeAdjacentWords(wordList);
        System.out.println(map);
    }

}

該算法的一種實現(xiàn)，其運行時間改進(jìn)到4秒。雖然這些附加的Map使得算法更快，而且句子結(jié)構(gòu)也相對清晰，但是程序沒有利用到該Map的關(guān)鍵字保持有序排列的事實，

同樣，有可能一種支持Map的操作但不保證有序排列的數(shù)據(jù)結(jié)構(gòu)可能運行得更快，因為它要做的工作更少。第5章將探索這種可能性，并討論隱藏在另一種Map實現(xiàn)背后的想法，這種實現(xiàn)叫作HashMap。HashMap將實現(xiàn)的運行時間從1秒減少到0.8秒。

原書代碼

package com.tianju.book.jpa.mapLearn;

import java.io.*;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.HashMap;
import java.util.Queue;

/*
DISTRIBUTION OF DICTIONARY:
Read the words...88984
1       1
2       48
3       601
4       2409
5       4882
6       8205
7       11989
8       13672
9       13014
10      11297
11      8617
12      6003
13      3814
14      2173
15      1169
16      600
17      302
18      107
19      53
20      28
Elapsed time FAST: 2.8 vs 3.8
Elapsed time MEDIUM: 50.9 vs 50.5
Elapsed time SLOW: 95.9 vs 96.1 (H vs T)
**/

public class WordLadder
{
    public static List<String> readWords( BufferedReader in ) throws IOException
    {
        String oneLine;
        List<String> lst = new ArrayList<>( );

        while( ( oneLine = in.readLine( ) ) != null )
            lst.add( oneLine );

        return lst;
    }

    // Returns true is word1 and word2 are the same length
    // and differ in only one character.
    private static boolean oneCharOff( String word1, String word2 )
    {
        if( word1.length( ) != word2.length( ) )
            return false;

        int diffs = 0;

        for( int i = 0; i < word1.length( ); i++ )
            if( word1.charAt( i ) != word2.charAt( i ) )
                if( ++diffs > 1 )
                    return false;

        return diffs == 1;
    }

    private static <KeyType> void update( Map<KeyType,List<String>> m, KeyType key, String value )
    {
        List<String> lst = m.get( key );
        if( lst == null )
        {
            lst = new ArrayList<>( );
            m.put( key, lst );
        }

        lst.add( value );
    }

    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses a quadratic algorithm (with appropriate Map).
    public static Map<String,List<String>> computeAdjacentWordsSlow( List<String> theWords )
    {
        Map<String,List<String>> adjWords = new HashMap<>( );

        String [ ] words = new String[ theWords.size( ) ];

        theWords.toArray( words );
        for( int i = 0; i < words.length; i++ )
            for( int j = i + 1; j < words.length; j++ )
                if( oneCharOff( words[ i ], words[ j ] ) )
                {
                    update( adjWords, words[ i ], words[ j ] );
                    update( adjWords, words[ j ], words[ i ] );
                }

        return adjWords;
    }

    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses a quadratic algorithm (with appropriate Map), but speeds things up a little by
    // maintaining an additional map that groups words by their length.
    public static Map<String,List<String>> computeAdjacentWordsMedium( List<String> theWords )
    {
        Map<String,List<String>> adjWords = new HashMap<>( );
        Map<Integer,List<String>> wordsByLength = new HashMap<>( );

        // Group the words by their length
        for( String w : theWords )
            update( wordsByLength, w.length( ), w );

        // Work on each group separately
        for( List<String> groupsWords : wordsByLength.values( ) )
        {
            String [ ] words = new String[ groupsWords.size( ) ];

            groupsWords.toArray( words );
            for( int i = 0; i < words.length; i++ )
                for( int j = i + 1; j < words.length; j++ )
                    if( oneCharOff( words[ i ], words[ j ] ) )
                    {
                        update( adjWords, words[ i ], words[ j ] );
                        update( adjWords, words[ j ], words[ i ] );
                    }
        }

        return adjWords;
    }


    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses an efficient algorithm that is O(N log N) with a TreeMap, or
    // O(N) if a HashMap is used.
    public static Map<String,List<String>> computeAdjacentWords( List<String> words )
    {
        Map<String,List<String>> adjWords = new TreeMap<>( );
        Map<Integer,List<String>> wordsByLength = new TreeMap<>( );

        // Group the words by their length
        for( String w : words )
            update( wordsByLength, w.length( ), w );

        // Work on each group separately
        for( Map.Entry<Integer,List<String>> entry : wordsByLength.entrySet( ) )
        {
            List<String> groupsWords = entry.getValue( );
            int groupNum = entry.getKey( );

            // Work on each position in each group
            for( int i = 0; i < groupNum; i++ )
            {
                // Remove one character in specified position, computing representative.
                // Words with same representative are adjacent, so first populate
                // a map
                Map<String,List<String>> repToWord = new HashMap<>( );

                for( String str : groupsWords )
                {
                    String rep = str.substring( 0, i ) + str.substring( i + 1 );
                    update( repToWord, rep, str );
                }

                // and then look for map values with more than one string
                for( List<String> wordClique : repToWord.values( ) )
                    if( wordClique.size( ) >= 2 )
                        for( String s1 : wordClique )
                            for( String s2 : wordClique )
                                if( s1 != s2 )  // must be same string; equals not needed
                                    update( adjWords, s1, s2 );
            }
        }

        return adjWords;
    }

    // Find most changeable word: the word that differs in only one
    // character with the most words. Return a list of these words, in case of a tie.
    public static List<String> findMostChangeable( Map<String,List<String>> adjacentWords )
    {
        List<String> mostChangeableWords = new ArrayList<>( );
        int maxNumberOfAdjacentWords = 0;

        for( Map.Entry<String,List<String>> entry : adjacentWords.entrySet( ) )
        {
            List<String> changes = entry.getValue( );

            if( changes.size( ) > maxNumberOfAdjacentWords )
            {
                maxNumberOfAdjacentWords = changes.size( );
                mostChangeableWords.clear( );
            }
            if( changes.size( ) == maxNumberOfAdjacentWords )
                mostChangeableWords.add( entry.getKey( ) );
        }

        return mostChangeableWords;
    }

    public static void printMostChangeables( List<String> mostChangeable,
                                             Map<String,List<String>> adjacentWords )
    {
        for( String word : mostChangeable )
        {
            System.out.print( word + ":" );
            List<String> adjacents = adjacentWords.get( word );
            for( String str : adjacents )
                System.out.println( " " + str );
            System.out.println( " (" + adjacents.size( ) + " words)" );
        }
    }

    public static void printHighChangeables( Map<String,List<String>> adjacentWords,
                                             int minWords )
    {
        for( Map.Entry<String,List<String>> entry : adjacentWords.entrySet( ) )
        {
            List<String> words = entry.getValue( );

            if( words.size( ) >= minWords )
            {
                System.out.print( entry.getKey( ) + " )" + words.size( ) + "):" );
                for( String w : words )
                    System.out.print( " " + w );
                System.out.println( );
            }
        }
    }

    // After the shortest path calculation has run, computes the List that
    // contains the sequence of word changes to get from first to second.
    public static List<String> getChainFromPreviousMap( Map<String,String> prev,
                                                        String first, String second )
    {
        LinkedList<String> result = new LinkedList<>( );

        if( prev.get( second ) != null )
            for( String str = second; str != null; str = prev.get( str ) )
                result.addFirst( str );

        return result;
    }

    // Runs the shortest path calculation from the adjacency map, returning a List
    // that contains the sequence of words changes to get from first to second.
    public static List<String> findChain( Map<String,List<String>> adjacentWords, String first, String second )
    {
        Map<String,String> previousWord = new HashMap<>( );
        Queue<String> q = new LinkedList<>( );

        q.add( first );
        while( !q.isEmpty( ) )
        {
            String current = q.element( ); q.remove( );
            List<String> adj = adjacentWords.get( current );

            if( adj != null )
                for( String adjWord : adj )
                    if( previousWord.get( adjWord ) == null )
                    {
                        previousWord.put( adjWord, current );
                        q.add( adjWord );
                    }
        }

        previousWord.put( first, null );

        return getChainFromPreviousMap( previousWord, first, second );
    }

    // Runs the shortest path calculation from the original list of words, returning
    // a List that contains the sequence of word changes to get from first to
    // second. Since this calls computeAdjacentWords, it is recommended that the
    // user instead call computeAdjacentWords once and then call other findChar for
    // each word pair.
    public static List<String> findChain( List<String> words, String first, String second )
    {
        Map<String,List<String>> adjacentWords = computeAdjacentWords( words );
        return findChain( adjacentWords, first, second );
    }

    public static void run(String[] args) throws IOException {
        long start, end;

        FileReader fin = new FileReader( "D:\\Myprogram\\springboot-workspace\\spring-book-store\\spring-book-store\\src\\main\\java\\com\\tianju\\book\\jpa\\mapLearn\\dict.txt" );
        BufferedReader bin = new BufferedReader( fin );
        List<String> words = readWords( bin );
        System.out.println(words);
        Map<String,List<String>> adjacentWords;
        adjacentWords = computeAdjacentWordsSlow( words );
        System.out.println(adjacentWords);


    }

    public static void main( String [ ] args ) throws IOException
    {
        long start, end;
        FileReader fin = new FileReader( "D:\\Myprogram\\springboot-workspace\\spring-book-store\\spring-book-store\\src\\main\\java\\com\\tianju\\book\\jpa\\mapLearn\\dict.txt" );

//        FileReader fin = new FileReader( "dict.txt" );
        BufferedReader bin = new BufferedReader( fin );
        List<String> words = readWords( bin );
        System.out.println( "Read the words..." + words.size( ) );
        Map<String,List<String>> adjacentWords;

        start = System.currentTimeMillis( );
        adjacentWords = computeAdjacentWords( words );
        end = System.currentTimeMillis( );
        System.out.println( "Elapsed time FAST: " + (end-start) );

        start = System.currentTimeMillis( );
        adjacentWords = computeAdjacentWordsMedium( words );
        end = System.currentTimeMillis( );
        System.out.println( "Elapsed time MEDIUM: " + (end-start) );


        start = System.currentTimeMillis( );
        adjacentWords = computeAdjacentWordsSlow( words );
        end = System.currentTimeMillis( );
        System.out.println( "Elapsed time SLOW: " + (end-start) );


        // printHighChangeables( adjacentWords, 15 );

        System.out.println( "Adjacents computed..." );
        List<String> mostChangeable = findMostChangeable( adjacentWords );
        System.out.println( "Most changeable computed..." );
        printMostChangeables( mostChangeable, adjacentWords );

        BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );

        for( ; ; )
        {
            System.out.println( "Enter two words: " );
            String w1 = in.readLine( );
            String w2 = in.readLine( );

            List<String> path = findChain( adjacentWords, w1, w2 );
            System.out.print( path.size( ) + "..." );
            for( String word : path )
                System.out.print( " " + word );
            System.out.println( );
        }
    }
}

總結(jié)

1.B樹，階M，數(shù)據(jù)樹葉上，根的兒子數(shù)在2和M之間，除根外，非樹葉節(jié)點兒子為M/2和M之間；
2.B樹的插入引起分裂，B樹的刪除，引起合并和領(lǐng)養(yǎng)；
3.紅黑樹，根是黑的，紅色節(jié)點的兒子必須是黑的，所有路徑的黑色節(jié)點數(shù)相同；
4.紅黑樹的插入，顏色翻轉(zhuǎn)，單旋轉(zhuǎn)，插入節(jié)點定顏色；
5.java標(biāo)準(zhǔn)庫的set和map，使用紅黑樹；文章來源地址http://www.zghlxwxcb.cn/news/detail-682439.html

到了這里，關(guān)于Java學(xué)數(shù)據(jù)結(jié)構(gòu)（3）——樹Tree & B樹 & 紅黑樹 & Java標(biāo)準(zhǔn)庫中的集合Set與映射Map & 使用多個映射Map的案例的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！