What is the name of the binary tree (or the family of the binary trees), that is balanced, and has the minimum number of nodes possible for its height?
Well this is special kind of tree not the AVL tree.
A:
Red-black tree?
Any one from http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree#Implementations?
KennyTM
2010-01-14 07:14:59
it should better be a comment..
Neeraj
2010-01-14 07:31:00
+1
A:
if the binary tree is balanced then, it height is a function of its nodes (n). height = log2n. so a balanced tree don't have a range of heights.
Alon
2010-01-14 07:28:49
And what about RB-tree then? It's balanced but may have quite different heights of its leaf nodes (basically 2x difference at maximum) - http://en.wikipedia.org/wiki/Red-black_tree .
IgorK
2010-01-14 08:14:11
a RB-tree is allowed to be nearly balanced , that is way there is a range of it heights (is also in the Wikipedia entry : "the tree is roughly balanced"
Alon
2010-01-21 20:00:05
+1
A:
The minimum number of nodes a completely balanced binary tree can have for height d is 2^(d-1)+1. As far as i know this type doesn't have a name.
The maximal number of nodes is 2^d. This is called a complete tree. All layers are completely full and each node has either 2 or zero childern(implied).
JPvdMerwe
2010-01-14 07:48:48
A:
balanced tree does not have a ranged of height that's why I called it is a special tree but I have confused that weight balanced tree included in the balanced binary tree?
Syed Mehmood Ali
2010-01-14 08:03:45
Please either leave a comment or edit your question to provide the extra information, thanks!
KennyTM
2010-01-14 08:14:48
A:
consider the minimum number of nodes possible for its height and I have mentioned this in my question and also it is a guaranteed balanced tree
Syed Mehmood Ali
2010-01-14 08:09:49