10

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.)

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
uroc
  • 3,993
  • 3
  • 21
  • 18
  • How large a search tree? – Will A Dec 01 '10 at 03:57
  • A couple thousand words ranging from 4 to 20 characters. Not sure if that is big or small, but its big for me. – uroc Dec 01 '10 at 04:03
  • Sounds like throwing away the tree when it gets to a certain point and replacing it with a tree built with 'the optimal order' is your best bet - should take milliseconds, if you can spare the time. – Will A Dec 01 '10 at 04:30
  • I'm wondering if rebalancing is a simple as changing a node to be the middle element of its lo child and all its lo children, itself, and the hi child and all its hi children. – uroc Dec 01 '10 at 04:38

4 Answers4

5

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.

hmuelner
  • 8,093
  • 1
  • 28
  • 39
  • 2
    Note (after skimming the paper): The suggested method (splaying) rebalances the tree even during read-only operations, and thus may not be well-suited for multithreaded access. – DevSolar May 29 '18 at 09:55
4

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!

Jim Howes
  • 51
  • 2
0

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.

Mostafa
  • 670
  • 1
  • 10
  • 20
0

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.

SingleNegationElimination
  • 151,563
  • 33
  • 264
  • 304