Q

二叉樹 - 刪除

2012-06-27 59 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

相關問題