Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Definition of a Balanced Tree

Tags:

tree

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?

like image 697
Mark Soric Avatar asked Nov 04 '11 20:11

Mark Soric


People also ask

What is the meaning of balanced tree?

(data structure) Definition: A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of "much farther" and different amounts of work to keep them balanced.

How can you tell if a tree is balanced?

To check if a Binary tree is balanced we need to check three conditions : The absolute difference between heights of left and right subtrees at any node should be less than 1. For each node, its left subtree should be a balanced binary tree. For each node, its right subtree should be a balanced binary tree.

When a tree is called a balanced tree?

A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

What is balanced tree and unbalanced tree?

A balanced binary tree is one in which no leaf nodes are 'too far' from the root. For example, one definition of balanced could require that all leaf nodes have a depth that differ by at most 1. An unbalanced binary tree is one that is not balanced.


2 Answers

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

  1. The left and right subtrees' heights differ by at most one, AND
  2. The left subtree is balanced, AND
  3. 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.

like image 158
comocomocomocomo Avatar answered Sep 27 '22 22:09

comocomocomocomo


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) <-- Unbalanced because 1-(-1)=2 >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)        <-- Unbalanced: 2-0 =2 > 1            /   \         E(h=1)  F (h=0)         /     \       H (h=0)   G (h=0)       
like image 20
CherylG Avatar answered Sep 27 '22 22:09

CherylG