如何“平衡”三元搜索树？大多数 tst 实现不解决平衡问题，但建议以最佳顺序插入（我无法控制。）
问问题
4105 次
4 回答
5
Dobbs 博士关于三元搜索树的文章说：DD Sleator 和 RE Tarjan 在“自调整二叉搜索树”（ACM 杂志，1985 年 7 月）中描述了三元搜索树的理论平衡算法。您可以使用您最喜欢的搜索引擎找到本文的在线版本。
于 2010-12-01T12:26:17.777 回答
4
一个简单的优化是让它成为一棵红黑树，这样可以避免一些最坏的情况。TST 实际上只是二叉树，其中给定节点的值是另一个 TST。因此，节点的“中间”子节点实际上并不是在每个级别都处于平衡状态的树的一部分，因为它无论如何都不能移动到不同的父节点。
这可以确保在 log(R) 时间内遍历 trie 的每一层，尽管考虑到每个节点的子尝试的大小，您可能会做得更好。不过，这看起来要复杂得多！
于 2018-07-04T16:33:59.417 回答
0
二叉搜索树的一个概括是B-Tree，它适用于从 2 开始的任何地方的扇出。这不是唯一的方法，但它是一种常见的方法。
它的大致工作方式是，如果插入或删除会使树失去平衡，它会从相邻节点窃取元素或空间。如果这还不足以保持树的平衡，它的高度将被改变以腾出空间。
于 2010-12-01T04:29:40.450 回答
0
阅读这篇文章：
“使用条件旋转和随机启发式的三元搜索尝试的自我调整”，作者“Ghada Hany Badr∗ 和 B. John Oommen †”
它将帮助您了解自我调整和平衡 TST。
于 2012-09-12T04:27:04.630 回答