二叉树在O(1)中得到最小元素

Question

我多次访问二叉树的最小元素.什么实现允许我在恒定时间内访问最小元素,而不是O(log n)？

Answer 1

根据您的其他要求,最小堆可能是您正在寻找的.它为您提供了最小元素的恒定时间检索.

但是,您不能像使用简单的二叉搜索树一样轻松地执行其他操作,例如确定值是否在树中.您可以查看splay树,这是一种自平衡二叉树,可以为最近访问过的元素提供更好的访问时间.

Answer 2

在O(log n)中找到一次,然后将要添加的新值与此缓存的最小元素进行比较.

UPD:如果你删除最小元素,这怎么可行.你只需再花一点O(log n)并找到新的.

让我们假设你的树中有10 000 000 000个整数.每个元素在内存中需要4个字节.在这种情况下,您的所有树都需要大约40 TB的硬盘空间.在这个巨大的树中搜索最小元素所花费的时间O(log n)大约是43次操作.当然,这不是最简单的操作,但无论如何,即使对于20年前的处理器来说也几乎没有.

当然,如果这是一个现实问题,这是实际的.如果出于某些目的(可能是大学)你需要真正的O(1)算法,那么我不确定我的方法可以在不使用额外内存的情况下为您提供这样的性能.