Interview Questions And Answers 
-
What is a balanced tree?
3,722 Views |
(9 votes, avg: 3)
Loading ...
Answers »
Our Sponsors
Our Sponsors
What is a balanced tree?
3,722 Views | (9 votes, avg: 3)
Loading ...
A binary tree is balanced if the depth of two subtrees of every node never differ by more than one
if the height of the left subtree of a node and the right subtre of a node differ by atmost one. can also be called AVL trees
A
/
First of all, a balanced tree need NOT necessarily be a binary tree. For example, a 2-3 tree is one of the most balanced forms of tree structures. However, mostly the balanced trees are implemented as binary trees.
Secondly, a balanced tree is a tree, in which the height of each subtree is dependent on the rest of the subtrees (NOT necessarily the same or differing just by one). For example in a Red-black tree, the height of one subtree can at the most be double that of the other.
http://www.purists.org/georg/avltree/
great examples of AVL trees and non-AVL trees
In my mind the easiest way to think about it is: if each node weights the same, a balanced tree is a tree where if any branch were to be plucked and held in the sky by a string holding the root, the tree will not skew to a side (assuming there is no torque).
Leave an Answer/Comment