Dr. Dobbs上的文章三叉查找树提到:D.D. Sleator和R.E. Tarjan在《自调整二叉查找树》(ACM期刊,1985年7月)中描述了用于平衡三叉查找树的理论算法。你可以使用你喜欢的搜索引擎找到该论文的在线版本。
一种简单的优化方法是将其转换为红黑树,这可以避免一些最坏情况。TST实际上只是二叉树,其中给定节点的值是另一个TST。因此,节点的“中间”子节点实际上并不是每个层级正在平衡的树的一部分,因为它无论如何都不能移动到不同的父节点。这确保了Trie的每个层级在log(R)时间内被遍历,尽管您可能通过考虑每个节点的子Trie的大小来进一步提高效率。但那看起来会更加复杂!
二叉搜索树的一种推广是B-Tree,它适用于从2个到更多个扇出。这不是唯一的方法,但它是一种常见的方法。大致的工作方式是,如果插入或删除会使树失衡,它会从相邻节点中窃取一个元素或空间。即使如此仍无法保持平衡,它的高度也将被改变以腾出空间。