在TreeMap中，樹是什麼意思？

我是新來的java，特別是java集合。 Java數據結構TreeMap沒有任何方法（如getChildren，getParent）表明它擁有分層結構。單詞樹在類名中的意義是什麼？在TreeMap中，樹是什麼意思？

來源

2015-12-19 Manojkumar Khotele

您是否閱讀過此Java類上的官方JavaDoc：http://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html？ – MWiesner

贊成票。 http://stackoverflow.com/questions/33251375/java-why-treemap-is-called-tree-map –

「樹」部分給出了類的實現細節。按照documentation，TreeMap是

一個Red-Black tree基於NavigableMap實現。

名稱OrderedMap或SortedMap可能會更好，但「樹」是不夠好，傳達類的工作它的用戶的方式。

來源

2015-12-19 14:09:13 dasblinkenlight

A TreeMap本質上是一棵Red-black樹，它是一個平衡搜索樹。此樹的主要目的是確保O(lg(n))查找並且不建模層次結構。

如果你看一下TreeMap的代碼，你會發現它有TreeMap.Entry，它定義如下。

static final class Entry<K,V> implements Map.Entry<K,V> { 
    K key; 
    V value; 
    Entry<K,V> left; 
    Entry<K,V> right; 
    Entry<K,V> parent; 
    boolean color = BLACK; 
    .. 
}

但OOP告訴我們，實現細節不應暴露

來源

2015-12-19 14:13:25

的數據結構是主要的地圖，沒有一棵樹。但是地圖是用樹來實現的。 TreeMap提供了一種有效的方式來按鍵排序存儲鍵/值對，並允許快速檢索。由於它是用戶的地圖，因此不需要獲取樹中任何節點的父節點或其子節點，因此沒有getParent或getChildren函數可用。

來源

2015-12-19 14:13:50

換句話說，TreeMap意味着它是一個Map實現，其中數據以樹狀結構存儲。這導致這樣的事實，即元素按鍵排序（TreeMap實現SortedMap）。

這是good visualisation of red-black tree。

Java中的其他類型的地圖是HashMap和LinkedHashmap。你可以找到差異here。

來源

2015-12-19 14:14:12 Gaket

您提供的用於紅黑樹可視化的鏈接：http://www.cs.usfca.edu /~galles/visualization/RedBlack.html不起作用 – nuwanjaya

我剛纔檢查過它，它適用於我的Safari和Chrome。您應該在左上角的文本框中輸入一些數字，在「插入」按鈕附近，然後按「插入」開始。 – Gaket

是的，它工作！感謝更新：） – nuwanjaya

在TreeMap中，樹是什麼意思？

回答

相關問題