1

我基本上需要一种保证 O(log n) 删除的方法。这可以用二叉树完成，还是总是最坏的情况 O(n)？

如果我每次都平衡树怎么办？

请帮忙

4

3 回答 3

3

您需要一个平衡的二叉树才能保证工作。红黑树是平衡树结构的一个例子，实现起来并不难。

红黑树（维基）

这是一个很好的讲座..

于 2012-06-27T05:56:24.460 回答
2

如果您正在寻找平衡二叉树，您可以使用“堆”

http://en.wikipedia.org/wiki/Heap_(data_structure )

于 2012-06-27T05:50:12.553 回答
1

你需要一个二叉搜索树

正如上面的wiki页面所说：

因此在最坏的情况下，它需要的时间与树的高度成正比

这意味着如果您可以使其始终保持平衡，则可以获得 O(logN) 进行删除

于 2012-06-27T05:55:30.083 回答