Trusted answers to developer questions

What is a red-black tree?

Free System Design Interview Course

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2024 with this popular free course.

The red-black tree is another member of the binary search tree family. Like the AVL tree, a red-black tree has self-balancing properties.

The structure of a red-black tree follows certain rules to ensure that the tree is always balanced.

Properties of a red-black tree

  • Each tree node is colored either red or black.

  • The root node of the tree is always black.

  • Every path from the root to any of the leaf nodes must have the same number of black nodes.

  • No two red nodes can be adjacent, i.e., a red node cannot be the parent or the child of another red node.

Examples

A correct red-black tree.
A correct red-black tree.

The tree above ensures that every path from the root to a leaf node has the same amount of black nodes. In this case,​ there is one (excluding the root node).

There are adjacent black nodes, ​but no adjacent red nodes.

A incorrect red-black tree.
A incorrect red-black tree.

The tree above does not follow the red-black convention as two red nodes are adjacent to each other. Another problem is that one of the paths to a leaf node has zero black nodes, whereas the other two contain a black node.

Time Complexity

Operation Average Case Worst Case
Search O(log n) O(log n)
Insertion O(log n) O(log n)
Deletion O(log n) O(log n)

Insertion and deletion in a red-black tree works better than the worst case, O(n) , of a BST.

RELATED TAGS

data structure
tree
balanced
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?