Red-black tree

Last updated Jan 28, 2023

• Algorithms
• Data structures

Red-black tree is a type of self-balancing binary search tree, a data structure used to implement ordered sets and maps. It is called red-black tree because each node in the tree is either red or black. The basic idea behind the red-black tree is to maintain a balance between the left and right subtrees of each node, so that, the tree remains roughly balanced, even as elements are added or removed. The following are the main properties of Red-Black Tree:

• Every node has a color, either red or black.
• The root of the tree is always black.
• There are no two adjacent red nodes (A red node cannot have a red parent or red child)
• Every path from a node (including leaf) to a null node has a same number of black nodes.

The height of a red-black tree is guaranteed to be O(log n), where n is the number of elements in the tree. This makes the basic operations of insertion, deletion and search all run in O(log n) time

AVL Tree is strictly self-balanced tree, it makes searching operation always cost O(log n) time. When Red-black tree, in the worst case it could be O(n) (left skewed or right skewed tree).

Tutorial

https://www.youtube.com/watch?v=qA02XWRTBdw

Apply the following rules when inserting elements to a Red-black tree

• If the tree is empty, create a new node as root node with back color.
• If the node is not empty, then create a new node as leaf node with red color
  • check the color of new node’s parent
    • If it’s black color, then stop.
    • If it’s red, then check the color of parent’s sibling
      • If it’s black or null, then do suitable rotation and recolor.
      • If it’s red then, recolor (both parent and parent sibling) and also check if parent’s parent of new node is NOT the root node, then recolor it and recheck.

• https://www.youtube.com/watch?v=3RQtq7PDHog