Red-Black Trees

Introduction

A Red Black Tree is a special kind of tree that has the ability to ensure a balanced tree height to make sure traversal of the tree is done in an efficient, effective manner.

Properties of Red Black Trees

1. Every node is either red or black.
2. The number of black nodes is the same along every path from a fixed node.
3. Red nodes cannot have a red node as a child.
4. The root node is always set to black.

Actions on a Red Black Tree

Insertion

Measures taken to the tree to maintain balance by changing the color of the nodes and rotating nodes.

Deletion

Measures taken to the tree to make properties hold after removing a node if a property is broken

Lookup

Same as a normal binary search tree, expect in a red black-tree's case, the tree will never act as a linked list, with the height always being balanced.

Diagram of a Red Black Tree

More information on the topic

For more details, visit Red Black Tree Introduction