balanced tree equation?
October 04, 2002 07:25 PM
is it true that a balanced tree should have ((2 ^ N + 1) / 2)- 1 nodes where N = height of the tree ?
[edited by - vaneger on October 4, 2002 8:34:33 PM]
1,658
October 04, 2002 07:44 PM
Assuming a binary tree, each level has twice as many nodes as the previous level.
Thus the tree has Σk=1..n 2k nodes.
That is 2n+1-1 nodes.
This can be proved by induction.
Edit: Embarassing error: forgot the +1 in n+1
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
[edited by - Fruny on October 4, 2002 9:03:22 PM]
Thus the tree has Σk=1..n 2k nodes.
That is 2n+1-1 nodes.
This can be proved by induction.
Edit: Embarassing error: forgot the +1 in n+1
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
[edited by - Fruny on October 4, 2002 9:03:22 PM]
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
October 04, 2002 08:01 PM
ya thats pretty much what i just said for isntance a tree with 7 nodes ahould have a height of 3 ( (( 2 * 2 * 2 ) / 2) - 1)) )
October 04, 2002 08:14 PM
(2 ^ n ) - 1 = ((2 ^ n + 1 ) / 2 - 1)
i had the whole + 1 /2 part cus i started one number lower (0 instead of 1) so i modified my algorithm instead of my counter no big deal results in same numbers
i had the whole + 1 /2 part cus i started one number lower (0 instead of 1) so i modified my algorithm instead of my counter no big deal results in same numbers
1,658
October 04, 2002 08:26 PM
0 level = 0 node = 21 -1 = 1-1 = 01 level = 1 node = 22 -1 = 2-1 = 12 levels = 3 nodes = 23 -1 = 4-1 = 3...n levels = k nodes = 2n+1 -1n+1 levels = k+2n+1 = 2n+1+2n+1-1 = 2n+2-1 = 2(n+1)+1-1QED. Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
[edited by - Fruny on October 4, 2002 9:26:58 PM]
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
