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
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?
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.
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.
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.
It's so confuzzled, I'm not even sure Prelude knows what she wrote.
Yeah, I had to put a lot of brain cells on it, reading and re-reading paragraphs over and over. I'm not saying that it's a bad read; the information is just very densely packed, and my mental decompression algorithm wasn't quite up to it in a few sections.Quote:
Originally Posted by jafet