CODEWITHSUNDEEP
algorithmdata-structures
Mars Lee
Mars Lee

Reputation: 1945

Do Red-Black tree and AVL tree have same balance condition?

For example:

An unbalanced tree:

  4
/   \
1    11
    /
   7
 /  \
5    9

After balance, it will become AVL tree:

    11
   /   \
  4    7
 /    / \
1    5   9

However, if the unbalanced tree is R-B tree like this:

(\\ means read pointers. \ means black pointers.)

  4
/   \\
1    11
    /
   7
 //  \\
 5    9

Is this a legal R-B tree? Or I should make it balance just like what I did to the tree?

Upvotes: 1

Views: 1296

Answers (1)

snakile
snakile

Reputation: 54521

The balance condition of AVL trees is different from the balance condition of Red-Black trees. An AVL tree is, in a sense, more balanced than a Red-Black tree.

In an AVL tree, for every node v, the difference between the height of v's right sub-tree and the height of v's left sub-tree must be at most 1. This is a very strict balance property compared to the one imposed by the Red-Black tree. In a Red-Black tree, no simple path from the root to a leaf is allowed to be more than twice as long as any other. This property results from the five color conditions a binary search tree must satisfy in order to be considered a valid Red-Black tree.

Your example Red-Black tree is indeed not balanced in the AVL sense because the difference between the height of the root's left sub-tree and the height of its right sub-tree is 2. Nevertheless, the tree is balanced in the Red-Black sense as it satisfies the five Red-Black color conditions.

The AVL balance condition implies that the height of an AVL tree is bounded by roughly 1.44log(n) while there's nothing preventing the height of a Red-Black tree from being greater: the Red-Black tree balance condition only implies a bound of 2log(n) on the height.

The fact that AVL trees tend to be shorter than Red-Black trees seems to suggest they must perform better. This is not necessarily the case: an AVL tree is indeed generally faster to search because it's more balanced than a Red-Black tree. But the reason an AVL tree is so well balanced is that keeping it balanced is computationally harder than keeping a Red-Black tree balanced. In particular, the AVL rotations make insertions and deletions in an AVL tree slower in comparison to these operations in the corresponding Red-Black tree.

Upvotes: 2

Related Questions