二叉树获取最小元素的时间复杂度为O(1)

Question

我需要多次访问二叉树的最小元素。有哪些实现方式可以在 常数时间 内访问最小元素，而不是 O(log n)？

- Rudiger

---

您可能需要添加有关树的更改频率以及是否可以接受插入/删除操作较耗时（用于重建缓存信息）的信息。 - Thorbjørn Ravn Andersen

Answer 1

根据您的其他要求，最小堆可能是您正在寻找的内容。它可以在常数时间内检索最小元素。

然而，与简单的二叉搜索树相比，您不能像那样轻松地执行一些其他操作，例如确定值是否在树中。您可以查看伸展树，这是一种自平衡二叉树，可以提供对最近访问的元素的改进访问时间。

- R. Martinho Fernandes

---

它需要为其他目的保持元素的完整顺序；但我经常访问顶部元素。 - Rudiger

@Rudiger：除了树之外，只需维护最小堆即可处理任意插入/删除。这不是一个选项吗？ - Aryabhatta

@Moron：如果你可以承受额外的结构内存开销，那么这是一个不错的想法，可以在某些情况下发挥作用。 - R. Martinho Fernandes

堆不会本质上带来很多结构开销；对于内联数据的数组式实现，它的开销为零。只有当您想要将节点固定在内存中并链接到外部结构时，它才会增加。然后，您将被卡在一个3指针树加上可能有2个指针将其链接到实际记录，以便能够找到节点以更新/删除它们。 - Potatoswatter

@Potatoswatter 这就是我的意思，如果要保留额外的结构（无论是数组还是其他什么），您需要额外的引用集。数组必须在其中具有引用。我将引用视为结构，将值视为内容。 - R. Martinho Fernandes

Answer 2

在树中只需 O(log n) 次查找，然后将你要添加的新值与此缓存的最小元素进行比较。

更新：如果删除了最小元素，该方法如何处理。你只需要再花费 O(log n) 次时间来查找新的最小元素即可。

假设你的树中有 10000000000000 个整数，每个元素在内存中需要 4 字节。在这种情况下，你的整个树需要大约 40 TB 的硬盘空间。在这个巨大的树中搜索最小元素所需的时间 O(log n) 大约是 43 次操作。当然，这不是最简单的操作，但对于 20 年前的处理器来说，这几乎是微不足道的。

当然，这只适用于真实世界中的问题。如果你需要真正的 O(1) 算法（可能是学术目的），那么我不确定我的方法是否能在不使用额外内存的情况下提供这样的性能。

- Roman

---

如果从树中移除了最小元素，你需要找到新的最小值。这会影响这种方法吗？ - Rudiger

如果您控制树的实现：当从树中删除最小元素时，您将遇到新的最小元素，因此您可以在O(1)的额外时间内更新最小元素。(当然，实际上删除最小元素仍将花费O(log n)的时间。) - meriton

每次插入/删除时，只需更新缓存的最小值。假设使用RB或某种类似的平衡树实现，FindMin仍将是O(1)，插入/删除仍将是O(log n)。如果树允许您遍历它（如dfs），则无需干扰内部实现。 - Aryabhatta

问题在于，在许多实际场景中，第一个/最后一个元素可能会被删除的频率比其他元素高得多。 - Dilum Ranatunga

Answer 3

这可能听起来有些愚蠢，但如果您主要访问最小元素，并且不太改变树的结构，那么在添加/删除时（在任何树上），维护指向最小元素的指针可能是最佳解决方案。

- Ofir

---

请注意，这仅适用于您实现树的情况。如果您使用给定的树（具有给定接口），则可能无法维护指针（但值是...）。 - Anna

在BST中添加/删除节点的时间复杂度为O(log n)，因此在同一时间保持最小指针不变并不会改变算法复杂度。实际上，Linux内核的CFS调度程序对其任务的rbtree执行此操作：请参见/usr/src/linux/kernel/sched_fair.c中的cfs_rq.rb_leftmost。 - ephemient

Answer 4

遍历树的时间复杂度始终为O(log n)。你是自己编写树实现的吗？你可以在你的数据结构旁边简单地隐藏当前最低值元素的引用，并在添加/删除节点时更新它。(如果你没有编写树，则也可以通过将树实现包装在自己的包装对象中来完成相同的操作。)

- Ben Zotto

Answer 5

在TAOCP中有一种实现方法，利用非满节点中的“spare”指针来完成沿节点顺序的双向链表（我现在不记得详细情况了，但我想你必须为每个方向都有一个“has_child”标志才能使其工作）。

有了这个和一个起始指针，你可以在O(1)时间内获得起始元素。

这种解决方案并不比缓存最小值更快或更有效。

- dmckee --- ex-moderator kitten

---

@Martinho：就是那个链接。不错的链接。 - dmckee --- ex-moderator kitten

Answer 6

如果你所说的“最小元素”是指“具有最小值的元素”，那么你可以使用带有自定义比较器Comparator的TreeSet将项目按正确顺序排序以存储单个元素，然后只需调用SortedSet#first()或#last()以尽可能高效地获取最大/最小值。

请注意，与其他集合/列表相比，向TreeSet插入新项略慢，但如果您没有大量不断变化的元素，则不应该成为问题。

- Esko

---

我非常确定这个（红黑树）的时间复杂度是 O(log n)。 - Rudiger

Rudiger是正确的：TreeSet是使用TreeMap实现的（在文档中有说明），而TreeMap是一种红黑树：http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html - R. Martinho Fernandes

如果元素已经是“可比较”的，那么你甚至不需要使用“比较器”。 - trashgod

Answer 7

如果您可以使用一些内存，那么组合集合可能适合您。

例如，您要查找的内容听起来很像链表。您始终可以访问最小元素，但是插入或查找任意节点可能需要更长的时间，因为您必须进行O(n)的查找。

如果您将链表和树结合起来，可能会得到两全其美的效果。为了查找项目以进行获取/插入/删除操作，您将使用树来查找元素。元素的“持有者”节点必须具有从树到链表的跨越方式，以进行删除操作。此外，链表必须是双向链表。

因此，我认为获取最小项将是O(1)，任何任意查找/删除将是O(logN)--我认为即使插入也将是O(logN)，因为您可以在树中找到放置它的位置，查看前一个元素并从那里穿过到您的链表节点，然后添加“下一个”。

嗯，这开始看起来像是一个非常有用的数据结构，可能会浪费一些内存，但我认为除非您必须重新平衡树，否则任何操作都不会比O(logN)更糟糕。

- Bill K

Answer 8

如果您将二叉树升级/“upcomplex”为线索二叉树，则可以获得O（1）的第一个和最后一个元素。

您基本上需要保留对当前第一个和最后一个节点的引用。

在插入后立即检查，如果第一个节点的前一个非空，则更新第一个节点。最后一个节点同理。

每当您删除时，首先检查要删除的节点是否是第一个或最后一个。然后相应地更新存储的第一个和最后一个节点。

- Dilum Ranatunga