何時平衡BST的最佳時間？

我有一個BST和2個進入它的隊列。爲了在最短的時間內插入和刪除，我需要經常平衡我的樹。爲此，我使用DSW算法。何時平衡BST的最佳時間？

我已經完成了所有這些工作，並且這一切都很好。我的問題是我不知道什麼時候平衡樹的最佳時間。

我試過尋找這方面的文件和任何類型的信息，但我找不到任何。

我基本上需要知道什麼時候對樹進行平衡是最理想的，這樣不會太頻繁地花費太多時間，但是我的插入刪除時間通常不會很長。所以最終總運行時間儘可能短。

任何想法？

2013-10-17 Dee

這僅僅是一個偏離我的頭腦的建議：比較樹中的元素數量和最大深度？你知道對於'n'元素，最佳深度應該是'log2（n）+ 1'。如果實際的最大深度離最佳深度太遠，那麼您知道該樹不適當地平衡。 – bstempi

我喜歡這個主意，但距離太遠有多遠？ – Dee

我想這取決於你想要樹有多高效。如果你做了「太遠」2或3，你會有一個非常有效的樹，但你會更頻繁地重新平衡。如果你將它定義爲更大的東西，那麼花費更少的時間來平衡你的樹，而犧牲樹訪問時間。我想如果你的樹是重讀的，保持數字低。如果它重寫，請保持較高。 – bstempi

這一切都取決於你的用例。採取更多的測量你的樹在你的情況下的行爲。

您也可以嘗試測量樹的不平衡程度，並在達到某個閾值時對其進行平衡。

2013-10-17 13:01:25 pierd

你可以添加一些細節或者如何在僞代碼中完成這個的例子嗎？這個答案接近於沒有這個細節的評論。 –

回答