Tree Balancing Problem

Hello!

I am trying to create a Tenary search tree that have 3 children: left, mid, right.
However, I have problem balancing it and I've tried different methods without success.


digraph {
nodesep=0.35
ordering=out
node[style="filled", fillcolor="grey"]
edge[color="blue", arrowhead="vee"]
{ node[shape=point style=invis] m5 m2 m8 m6 m4 m10 m11 m12 m13 m14 m15}
s -> m5 [weight=100 style=invis]
s -> h
s -> m2 [weight=100 style=invis]
h -> m8 [weight=100 style=invis]
h -> e
h -> m6 [weight=100 style=invis]
e -> m4 [weight=100 style=invis]
e -> l
e -> o
l -> m10 [weight=100 style=invis]
l -> ll
l -> m11 [weight=100 style=invis]
o -> m12 [weight=100 style=invis]
o -> g
o -> m13 [weight=100 style=invis]
g -> m14 [weight=100 style=invis]
g -> a
g -> m15 [weight=100 style=invis]
}

I want the left, mid and right to be in a straight line.
Tree should basically look like a binary search tree, where mid is equal.
In the picture 'l' should be mid of 'e' and 'o' right of 'e'.

http://i64.tinypic.com/2drzb48.png

Thank you.

Re: Tree Balancing Problem

Greetings.  If you remove style=invis, you can see the entire graph being rendered.  It appears you were attempting the tactic of cranking up the weight of the edge to the center child of each node, which seems reasonable. But the graph you submitted is different. For example you increased the weight of e->m4 (m4 is the leftmost child) instead of e->l (l is the center child). So e is centered over m4, not l.  Were you expecting something different?
Stephen North

 

I don't get it really. The

I don't get it really.
The graph should look like: <img>http://i68.tinypic.com/246nc5y.png</img>

'o' should be 'e' right child. So basically, e should have these: e->left(nil)  e->mid(l) e->right(o)

e -> m4 [weight=100 style=invis] (left, invisible)

e -> l (middle)

e -> o (right)

However this doesn't work and i dont know why it wont center it.

You are putting weights on

You are putting weights on the wrong edges. Heavier weights means the edge will be more vertical, so the edges with heavy weights should be the edge to the middle child. Try

digraph {
nodesep=0.35
ordering=out
node[style="filled", fillcolor="grey"]
edge[color="blue", arrowhead="vee"]
{ node[shape=point style=invis] m5 m2 m8 m6 m4 m10 m11 m12 m13 m14 m15}
s -> m5 [style=invis]
s -> h  [weight=100]
s -> m2 [style=invis]
h -> m8 [style=invis]
h -> e [weight=100]
h -> m6 [style=invis]
e -> m4 [style=invis]
e -> l [weight=100]
e -> o
l -> m10 [style=invis]
l -> ll [weight=100]
l -> m11 [style=invis]
o -> m12 [style=invis]
o -> g [weight=100]
o -> m13 [style=invis]
g -> m14 [style=invis]
g -> a [weight=100]
g -> m15 [style=invis]
}

 

Also, as a rule of thumb when setting style=invis for nodes and edges to tweak the layout, it's good to start without these set, so you can see how things interact. Once you have the layout the way you want it, you can then enable style=invis.

Thank you soo much! Gold Star

Thank you soo much! Gold Star for you my friend!

Recent comments