Q

二叉树 - 删除

2012-06-27 57 views 1 likes

1

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

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

请帮助

2012-06-27 user809240

A

回答

2

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

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

2012-06-27 05:50:12 KennO

+0

我堆同意，因为它总是平衡（完成） – Ken

1

你需要一个Binary Search Tree

如上wiki页面说：

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

这意味着如果你可以把它总是平衡的T，你可以删除

2012-06-27 05:55:30 xvatar

3

得到O（logN）的需要为保证工作平衡二叉树。红黑树是平衡树结构的一个例子，实现并不太难。

Red Black Trees (wiki)

这里是一个nice lecture for that ..

2012-06-27 05:56:24 VSOverFlow

+0

我个人建议[AVL树（HTTP：//en.wikipedia。 org/wiki/AVL_tree），因为我认为它们实现起来要简单得多。 – JPvdMerwe

相关问题