Definition of a Balanced Tree

Question

I am just wondering if someone might be able to clarify the definition of a balanced tree for me  I have that  a tree is balanced if each sub-tree is balanced and the height of the two sub-trees differ by at most one    I apologize if this is a dumb question  but does this definition apply to every node all the way down to the leaves of a tree or only to the left and right sub-trees immediately off the root  I guess another way to frame this would be  is it possible for internal nodes of a tree to be unbalanced and the whole tree to remain balanced

User · Answer

The constraint is generally applied recursively to every subtree. That is, the tree is only balanced if:

The left and right subtrees' heights differ by at most one, AND
The left subtree is balanced, AND
The right subtree is balanced

According to this, the next tree is balanced:

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G

The next one is not balanced because the subtrees of C differ by 2 in their height:

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G

That said, the specific constraint of the first point depends on the type of tree. The one listed above is the typical for AVL trees.

Red-black trees, for instance, impose a softer constraint.

User · Answer

the aim of balanced tree is to reach the leaf in a minimum of traversal  min height    The degree of the tree is the number of branches minus 1  A Balanced tree may be not Binary

User · Answer

The height of a node in a tree is the length of the longest path from that node downward to a leaf  counting both the start and end vertices of the path  A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1   A tree is height-balanced if all of its nodes are height-balanced

User · Answer

There are several ways to define  Balanced   The main goal is to keep the depths of all nodes to be O log n     It appears to me that the balance condition you were talking about is for AVL tree  Here is the formal definition of AVL tree s balance condition      For any node in AVL  the height of its left subtree differs by at most 1 from the height of its right subtree     Next question  what is  height        The  height  of a node in a binary tree is the length of the longest path from that node to a leaf    There is one weird but common case      People define the height of an empty tree to be  -1     For example  root s left child is null                 A   Height   2                      height  -1        B  Height   1   lt -- Unbalanced because 1- -1  2  gt 1                                            C  Height   0    Two more examples to determine   Yes  A Balanced Tree Example           A  h 3                B h 1      C  h 2                           D  h 0   E h 0   F  h 1                                 G  h 0    No  Not A Balanced Tree Example           A  h 3                B h 0      C  h 2          lt -- Unbalanced  2-0  2  gt  1                          E h 1   F  h 0                        H  h 0    G  h 0

User · Answer

Balanced tree is a tree whose height is of order of log number of elements in the tree    height   O log n   O  as in asymptotic notation i e  height should have same or lower asymptotic growth rate than log n  n  number of elements in the tree   The definition given  a tree is balanced of each sub-tree is balanced and the height of the two sub-trees differ by at most one  is followed by AVL trees   Since  AVL trees are balanced but not all balanced trees are AVL trees  balanced trees don t hold this definition and internal nodes can be unbalanced in them  However  AVL trees require all internal nodes to be balanced

User · Answer

There s no difference between these two things  Think about it   Let s take a simpler definition   A positive number is even if it is zero or that number minus two is even   Does this say 8 is even if 6 is even  Or does this say 8 is even if 6  4  2  and 0 are even   There s no difference  If it says 8 is even if 6 is even  it also says 6 is even if 4 is even  And thus it also says 4 is even if 2 is even  And thus it says 2 is even if 0 is even  So if it says 8 is even if 6 is even  it  indirectly  says 8 is even if 6  4  2  and 0 are even   It s the same thing here  Any indirect sub-tree can be found by a chain of direct sub-trees  So even if it only applies directly to direct sub-trees  it still applies indirectly to all sub-trees  and thus all nodes

[tree] Definition of a Balanced Tree

Examples related to tree