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?
binary tree balance problem
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?
Last edited by Salem; 08-16-2006 at 10:45 AM. Reason: Tried to code tag the tree, but it didn't help
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.
My best code is written with the delete key.
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.
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
Man, that's, like, 100+ pages of pure confuzzlednessI'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.
Code:#include <stdio.h> void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){ puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9 /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i] ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][ t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}
It's so confuzzled, I'm not even sure Prelude knows what she wrote.
Sent from my iPadŽ
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.Originally Posted by jafet
Man, that's, like, 100+ pages of pure confuzzledness
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
