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?
-
Just to be pedantic... the minimum number of nodes for a tree of height N has N nodes (ie: every node has one child), and isn't balanced. Perhaps you meant "the minimum height for its number of nodes"?Tordek– Tordek2010-01-03 11:55:32 +00:00Commented Jan 3, 2010 at 11:55
-
@Moody does it have to be a search tree?R. Martinho Fernandes– R. Martinho Fernandes2010-01-03 12:02:57 +00:00Commented Jan 3, 2010 at 12:02
-
@Tordek: The wording in the question is valid. The minimum number of nodes for a balanced binary tree of height 4 is 8, for height 5 is 16, for height 6 is 32,... for height n is 2^(n-1). I'm not sure if this is what Moody wants, though.R. Martinho Fernandes– R. Martinho Fernandes2010-01-03 12:08:34 +00:00Commented Jan 3, 2010 at 12:08
Add a comment
|
4 Answers
balanced binary tree
(data structure)
Definition: A binary tree where no leaf is more than a certain amount farther from the root than any other. After inserting or deleting a node, the tree may rebalanced with "rotations."
Generalization (I am a kind of ...) binary tree.
Specialization (... is a kind of me.) AVL tree, red-black tree, B-tree, balanced binary search tree.
Aggregate child (... is a part of or used in me.) left rotation, right rotation.
See also BB(α) tree, height-balanced tree.
-- http://www.itl.nist.gov/div897/sqg/dads/HTML/balancedbitr.html
Comments
AVL is a balanced tree with log(n) height (this is the lowest height possible for binary tree).
Another implementation of a similar data structure is Red Black Tree.
Both trees implement all operations in O(log(n)).
Comments
AVL Tree is something that you have been looking for.
From Wikipedia:
In computer science, an AVL tree is a self-balancing binary search tree, and it is the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
