Search triple tree balancing

Question

How can I “balance” the triple search tree? Most tst implementations are not related to balancing, but suggest inserting in the optimal order (which I cannot control.)

Answer 1

Dr. Dobbs's article on Triple Search Trees says: DD Sleator and RE Tarjan describes theoretical balancing algorithms for triple search trees in "Self-Regulating Binary Search Trees" (Journal of ACM, July 1985). You can find online versions of this article in your favorite search engine.

Answer 2

read this article:

"Self-tuning triple search attempts using conditional spins and randomized heuristics" by "Ghada Hany Badr * and B. John Oommen †"

this will help you understand the self-adjusting and balancing TSTs.

Answer 3

A generalization of the binary search tree is the B-Tree , which works for branches from 2 to above. This is not the only way to do this, but it is a common one.

Roughly how this works, if inserting or deleting results in the loss of a tree, it will steal an element or space from a neighboring node. Even if this is not enough to keep the tree in balance, its height will be changed to make room.