Question

why are RB and AVL trees considered balanced binary search trees? give concrete examples for each tree type

Answer 1

Balanced Binary Search Tree : A binary tree is search balanced tree if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

AVL performs better when you look up more often than insertion/deletion. Red-black is better when you are inserting/deleting more often than searching. But the theoretical asymptotic complexity for both of them are the same. They Both performs the operation in O( logN ) time That is why both RB and AVL trees are considered as balanced binary search tree.

Example for AVL Tree :

Steps involved in Insertion in AVL tree.

After inserting Node 45, the AVL trtee becomes imbalanced

Starting at the inserted node (45), traverse up the tree and find the first imbalanced node:

• We Find node 78 ( This is the first node with | height( left tree ) - height( right tree ) | > 1 )

The AVL tree will become balanced again after we performed the tri-node restructing operation :

Example for Red-Black tree :

Steps involved in insertion in a Red-Black tree.

This is a Red - Black Tree

After inserting 9 in the Tree, it becomes :

After Recolouring

Right Rotate with Recolouring

To insert a node x, we first insert the node as if in an ordinary Binary Search Tree and colour it red. If the parent of the inserted node is black, then we are done since none of the Red-Black properties will be violated. If the parent is red, then the red constraint is violated. In such a case, we bubble the violation up the tree by repeatedly applying the recolouring transformation until it no longer applies. This either eliminates the violation or produces a situation in which one of the transformations, each of which leaves no violation.