为什么treemap需要O（log（n））时间在Get/put

问题描述：

在其中一篇帖子中，我看到TreeMap需要O(log(n))时间来获取/放置。有人可以请回答为什么它需要O(log(n))，即使它可以直接通过get/put使用密钥进行搜索吗？为什么treemap需要O（log（n））时间在Get/put

您认为需要多少次操作直接进行搜索？ – 2014-10-20 05:57:52

您应该检查本书中由Treemap类的Javadoc引用的算法，而不是以不适当的格式在此处询问。 – 2014-10-20 05:58:58

答

在TreeMap中，键/值条目存储在红黑树中，并且为了查找树中是否包含键，必须从根开始遍历它，直到某个路径达到所需的钥匙或到达叶子。

包含n个元素的树的高度为O(log n)，因此这是搜索密钥需要的时间。

但op问为什么O（log（n））？ – 2014-10-20 05:57:24

@KickButtowski我在原始版本中有一个错字。现在修复。 – Eran 2014-10-20 06:00:40

我认为说红色的黑树是一种**平衡树** – 2014-10-20 06:03:39