平衡三叉搜索树

Question

10

如何“平衡”三叉搜索树？大多数三叉搜索树的实现没有考虑平衡，但建议按照最佳顺序插入节点（我无法控制）。

- uroc

搜索树有多大？ - Will A

几千个单词，长度在4到20个字符之间。不确定这算大还是小，但对我来说很大。 - uroc

听起来当树达到某个点并用“最优顺序”构建的树替换它是你最好的选择 - 如果你能抽出时间，应该只需要几毫秒。 - Will A

我在想，重新平衡是否只需将节点更改为其lo子节点及其所有lo子节点、本身和hi子节点及其所有hi子节点的中间元素。 - uroc

4个回答

4

一种简单的优化方法是将其转换为红黑树，这可以避免一些最坏情况。TST实际上只是二叉树，其中给定节点的值是另一个TST。因此，节点的“中间”子节点实际上并不是每个层级正在平衡的树的一部分，因为它无论如何都不能移动到不同的父节点。

这确保了Trie的每个层级在log(R)时间内被遍历，尽管您可能通过考虑每个节点的子Trie的大小来进一步提高效率。但那看起来会更加复杂！

- Jim Howes

0

二叉搜索树的一种推广是B-Tree，它适用于从2个到更多个扇出。这不是唯一的方法，但它是一种常见的方法。

大致的工作方式是，如果插入或删除会使树失衡，它会从相邻节点中窃取一个元素或空间。即使如此仍无法保持平衡，它的高度也将被改变以腾出空间。

- SingleNegationElimination

这篇文章讨论了三叉搜索树。 - hmuelner

1

我对1-2 B树和三叉树之间的区别一点也不清楚。你能解释一下吗？ - SingleNegationElimination

2

一个B-Tree（通常）包含节点中的完整键。在三叉搜索树中，关键字由路径到节点定义。 - hmuelner

0

阅读本文：

“使用条件旋转和随机启发式方法自适应三叉搜索树的平衡调整” 作者： “Ghada Hany Badr∗和B. John Oommen†”

它将帮助您了解自适应和平衡TSTs。

- Mostafa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hmuelner · Accepted Answer

Dr. Dobbs上的文章三叉查找树提到：D.D. Sleator和R.E. Tarjan在《自调整二叉查找树》（ACM期刊，1985年7月）中描述了用于平衡三叉查找树的理论算法。你可以使用你喜欢的搜索引擎找到该论文的在线版本。