i need a optimal tree balancing algorithm.

for example:a)if add 30?Code:`12`

/ \

9 20

/ \ / \

6 10 16 25

\ /

17 22

b)if add 28?

c)if add 14?

d)if add 18?

Printable View

- 08-16-2006overkillbinary tree balance problem
i need a optimal tree balancing algorithm.

for example:Code:`12`

/ \

9 20

/ \ / \

6 10 16 25

\ /

17 22

b)if add 28?

c)if add 14?

d)if add 18? - 08-16-2006Prelude
Optimal is expensive. You're looking at a global rebalance of the tree after every modification. Do a google search for the DSW algorithm. If you're willing to live with "pretty darn close", the AVL balancing scheme is as good as it gets without really hurting performance.

- 08-16-2006pianorain
I'm sure modesty prevented the posting of this link. ;) Even if you don't use any of the code, the detailed explanations sure taught me a lot about different ways to balance a tree. I think my personal favorite is the red-black tree.

- 08-17-2006jafet
Man, that's, like, 100+ pages of pure confuzzledness :rolleyes: I'll be putting my brain cells on it when I have the time, but I don't think we all should expect the OP to.

- 08-17-2006SlyMaelstrom
It's so confuzzled, I'm not even sure Prelude knows what she wrote.

- 08-17-2006pianorainQuote:

Originally Posted by**jafet**