22XX302-DATA STRUCTURES - I
UNIT V & TREE
1. RED BLACK TREE
Red-Black Trees are another type of the Balanced Binary Search Trees with two
coloured nodes: Red and Black. It is a self-balancing binary search tree that makes
use of these colours to maintain the balance factor during the insertion and deletion
operations. Hence, during the Red-Black Tree operations, the memory uses 1 bit of
storage to accommodate the colour information of each node
In Red-Black trees, also known as RB trees, there are different conditions to follow
while assigning the colours to the nodes.
❖ The root node is always black in colour.
❖ No two adjacent nodes must be red in colour.
❖ Every path in the tree (from the root node to the leaf node) must have the
same amount of black coloured nodes.
Even though AVL trees are more balanced than RB trees, with the balancing
algorithm in AVL trees being stricter than that of RB trees, multiple and faster
insertion and deletion operations are made more efficient through RB trees.
UNIT V & TREE
1. RED BLACK TREE
Red-Black Trees are another type of the Balanced Binary Search Trees with two
coloured nodes: Red and Black. It is a self-balancing binary search tree that makes
use of these colours to maintain the balance factor during the insertion and deletion
operations. Hence, during the Red-Black Tree operations, the memory uses 1 bit of
storage to accommodate the colour information of each node
In Red-Black trees, also known as RB trees, there are different conditions to follow
while assigning the colours to the nodes.
❖ The root node is always black in colour.
❖ No two adjacent nodes must be red in colour.
❖ Every path in the tree (from the root node to the leaf node) must have the
same amount of black coloured nodes.
Even though AVL trees are more balanced than RB trees, with the balancing
algorithm in AVL trees being stricter than that of RB trees, multiple and faster
insertion and deletion operations are made more efficient through RB trees.
