Red Black Tree

This page introduces a data structure we discussed during class----the red black tree

Introduction

A Red Black Tree is a self-balanceing binary search tree.

It uses red and black node colors to keep the tree balanced, which helps search, insert and delete operations more efficient than a simple binary search tree.

Properties

• Each node are red or black
• Root node is black
• No red nodes have red children
• All path from the root to a null child have the same number of black nodes

Insertion

There are mainly 3 steps to insert data in to R-B trees

1. Insert a new value using BST insertion algorithm
2. Color the new node red
3. Check R-B tree properties and restore if necessary

For repairing a red root, if the root of the tree is red, we can switch it to black without violating any other property.

For repairing red node with red child, we need to pick a repair operation:

Deletion

There are mainly 2 steps to delete data in a R-B tree

1. Delete value using BST deletion algorithm
2. Check R-B tree propeties and restore if necessary

For repairing, if the deleted node is black and replacement is red, turn replacement black

For black node without red replacement, we also need to pick the operation:

For time complexity and other detailed information, here's a place to visit:

Thank you for visiting this site!