瞭解TreeMaps

Question

這是一個關於樹圖的noobie問題。我已經閱讀了Java API和其他文檔，但我仍不清楚這是如何工作的。根據我的理解，Java中的樹（或任何語言）有點像家族樹;其中已說：

Layer 1        OldestGuy  
Layer 2  OldGuy1  Oldguy2   OldGuy3  OldGuy4   OldGuy5 
Layer 3 Guy1 Guy2 Guy3 Guy4 Guy5 Guy6........ etc 

其中層1具有1個值（即中央節點），並從那裏可以存在於每個後續層的值（或專家）的任意數量，並且一些「分支」的可以比其他人長（例如，它可以去OldestGuy - > OldGuy1 - > Guy1 & Guy2 ... Guyn，同時另一個分支只是OldestGuy - > OldGuy4）

有了這種印象，我試圖在特定分支的特定位置添加值到TreeMap中，同時進行特定連接，但我似乎得到的結果與HashMap的結果相同。

（這似乎是我想要做的，需要的東西比映像樹更多....作爲密鑰（或層（？）將是相同的幾個不同的值）

任何建議/說明會太棒了，因爲我覺得我好像在嚴重地用這個樹叫錯了樹

我見過使用谷歌.jar（如家譜）完成這個例子，但我只是試圖理解這個因爲TreeMap和Trees之間似乎存在很多衝突，以及如何將數據存儲在其中。

Answer 1

TreeMap只是Map的一個實現，恰好在幕後使用紅黑樹。樹的細節不會暴露給您，因此您不能將元素存儲在任意位置。

換句話說，TreeMap不是通用樹數據結構。如果這是你真正想要的，也許看看這個堆棧溢出問題：Java tree data-structure?。

Answer 2

Java TreeMap使用樹作爲內部數據結構以獲取O（log n）查找和插入，但不在其接口中公開其樹形結構。因此，例如，無法獲取樹節點及其所有後代，或者代表使用它的家族樹。

Answer 3

TreeMap是Map（通過樹實現），而不是樹（通過Map或其他實現）。

Answer 4

我覺得你混淆了兩個不同的東西。 A TreeMap實施爲紅黑樹。
根據Java文檔：

基於紅黑樹的NavigableMap實現。根據按鍵的自然排序，或者在地圖創建時提供的Comparator ，根據使用哪個構造函數，地圖排序爲 。

此實現爲 containsKey，get，put和remove操作提供了有保證的log（n）時間成本。算法是對Cormen，Leiserson和Rivest's Introduction 中算法的修改。

因此，在本質上，如果你想擁有你的鑰匙可預測的排序，你應該要麼離開樹形圖中使用的自然順序排序您的鑰匙或實現Comparator接口自己。再次，從的Javadoc：

注意，排序由一棵樹映射維護，就像任何有序映射， ，以及是否提供了明確的比較，必須 符合平等，如果此有序映射要正確實現 的Map接口。 （請參閱Comparable或Comparator以獲得與equals相等的精確的 定義）。這是因爲Map的 接口是根據等號操作定義的，但排序的 地圖使用其compareTo（或compare） 執行所有關鍵比較方法，因此通過此方法認爲相同的兩個鍵從排序映射的立足點開始相等。排序映射的行爲是 ，即使其排序與equals不一致，也是很好定義的;它只是 未能服從Map接口的一般合同。

現在，您是否想按照我提到的方式（即自然順序）或其他方式（即插入順序或其他方式）放置您的密鑰並不清楚。
例如，如果您更喜歡廣告訂單，LinkedHashMap對您的情況可能會更好。
如果有其他情況請說明：]。

Answer 5

public class TreeMap<K,V> 
extends AbstractMap<K,V> 
implements NavigableMap<K,V>, Cloneable, Serializable 

• 樹圖不使用散列存儲鍵。這是使用紅黑 樹（自平衡二叉搜索樹）。
• TreeMap按照其鍵的自然排序進行排序。樹圖將始終有所有元素排序。
• 樹形圖的工作基於樹形數據結構。
• 樹圖是不同步因此不是線程安全的。
• java中的樹圖不是允許空鍵，但允許多空值。

樹圖的工作基於樹數據結構。

• 每個節點都有3個引用：PARENT，LEFT和RIGHT。
• LEFT元素始終小於父元素。
• RIGHT元素總是等於或大於父元素。