平衡三元搜索树

Question

一个人如何“平衡”三元搜索树？大多数TST实现都无法解决平衡，而是建议以最佳顺序插入（我无法控制）。

Answer 1

Dobbs博士的文章 三元搜索树 说：DD Sleator和Re Tarjan描述了“自我调整的二进制搜索树”中三元搜索树的理论平衡算法（ACM杂志，1985年7月）。您可以使用您喜欢的搜索引擎找到本文的在线版本。

Answer 2

一种简单的优化是使其成为红色树，可以避免一些最坏情况。 TST实际上只是二进制树，其中给定节点的值是另一个TST。因此，节点的“中间”孩子实际上并不是每个级别都在平衡的树的一部分，因为无论如何它都无法移至其他父母。

这确保了Trie的每个层在日志时间（R）时间中都可以穿越，尽管您可以考虑到每个节点处的子调子的大小，从而可以做得更好。不过，这看起来更加复杂！

Answer 3

二进制搜索树的概括是 B树, ，适用于2个及以上任何地方的粉丝。这不是唯一的方法，但这是一个普遍的方法。

大致工作的工作方式是，插入或删除是否会使树失去平衡，它会从相邻节点中窃取元素或空间。如果这还不足以使树保持平衡，那么它的高度将被更改以腾出空间。

Answer 4

阅读本文：

“ Ghada Hany Badr ∗和B. John Oommen†”，“使用条件旋转和随机启发式方法对三元搜索进行自我调整。

它将帮助您理解自我调整和平衡TST。