爲什麼treemap需要O（log（n））時間在Get/put

在其中一篇帖子中，我看到TreeMap需要O(log(n))時間來獲取/放置。有人可以請回答爲什麼它需要O(log(n))，即使它可以直接通過get/put使用密鑰進行搜索嗎？爲什麼treemap需要O（log（n））時間在Get/put

2014-10-20 mac

您認爲需要多少次操作直接進行搜索？ – 2014-10-20 05:57:52

您應該檢查本書中由Treemap類的Javadoc引用的算法，而不是以不適當的格式在此處詢問。 – 2014-10-20 05:58:58

在TreeMap中，鍵/值條目存儲在紅黑樹中，並且爲了查找樹中是否包含鍵，必須從根開始遍歷它，直到某個路徑達到所需的鑰匙或到達葉子。

包含n個元素的樹的高度爲O(log n)，因此這是搜索密鑰需要的時間。

2014-10-20 05:56:41 Eran

但op問爲什麼O（log（n））？ – 2014-10-20 05:57:24

@KickButtowski我在原始版本中有一個錯字。現在修復。 – Eran 2014-10-20 06:00:40

我認爲說紅色的黑樹是一種**平衡樹** – 2014-10-20 06:03:39

回答