Search IconIcon to open search

Red-black tree

Last updated Jan 28, 2023

# What is red-black tree?

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:

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

# Compare to AVL tree

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).

# Insertion



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

# Resources