binary-search-tree - 什么时候是平衡 BST 的最佳时间？

Question

我有一个 BST 和 2 个队列。为了在尽可能短的时间内插入和删除，我需要经常平衡我的树。为此，我使用 DSW 算法。

我已经实现了这一切，一切都很好。我的问题是我不知道平衡树的最佳时间是什么时候。

我已经尝试寻找关于此的论文和任何类型的信息，但我找不到任何信息。

我基本上需要知道什么时候平衡树是最佳的，这样它不会经常花费太多时间，但它通常足以让我的插入和删除时间不会花费很长时间。所以最终总运行时间尽可能短。

有任何想法吗？

Answer 1

这完全取决于您的用例。进行更多测量您的树在您的情况下的行为方式。

您也可以尝试测量树的不平衡程度，并在达到某个阈值时对其进行平衡。