Balancing a ternary search tree

Question

How does one go about 'balancing' a ternary search tree? Most tst implementations don't address balancing, but suggest inserting in an optimal order (which I can't control.)

Answer 1

The article in Dr. Dobbs about Ternary Search Trees says: D.D. Sleator and R.E. Tarjan describe theoretical balancing algorithms for ternary search trees in "Self-Adjusting Binary Search Trees" (Journal of the ACM, July 1985). You can find online versions of this paper with your favorite search engine.

Answer 2

One simple optimization is to make it a red-black tree, which can avoid some worst-case scenarios. TSTs are really just binary trees where the value of a given node is another TST. So, the "middle" child of a node is not really part of the tree that is being balanced at each level, as it cannot move to a different parent anyway.

This ensures that each tier of the trie is traversed in log(R) time, although you could probably do even better by taking into account the size of the subtries at each node. That looks to be a lot more complicated though!

Answer 3

A generalization of the binary search tree is the B-Tree, which works for fanouts anywhere from 2 and up. That's not the only way to do it, but it's a common one.

Roughly the way it works is if an insert or delete would put the tree out of balance, it steals an element or a space from a neighboring node. If even that isn't enough to keep the tree in balance, its height by will be changed to make room.

Answer 4

read this article:

"Self-Adjusting of Ternary Search Tries Using Conditional Rotations and Randomized Heuristics" by "Ghada Hany Badr∗ and B. John Oommen †"

it will help you to understanding self-adjusting and balancing TSTs.