Red-Black Trees

Red-Black Tree Insert

To perform operation insert(k, o), we execute the insertion algorithm for binary search trees and color red the newly inserted node z unless it is the root.

1. We preserve the root, external and depth properties.
2. If the parent v of z is black, we also preserve the internal property and we are done.
3. Else (v is red ) we have a double red (i.e., a violation of the internal property), which requires a reorganization of the tree.

Following are some of the areas in Red-Black Trees in which we provide help:

Definition: a binary tree, satisfying

Red-Black Tree Reorganization

Red-Black Tree Insert