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?
+2
A:
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)).
Elisha
2010-01-03 11:39:07
+3
A:
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.
Prasoon Saurav
2010-01-03 11:40:56
+2
A:
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
Bart Kiers
2010-01-03 11:44:25