Red-Black Tree Operations

Learn to add and remove an element in red-black trees.

We'll cover the following

Addition

To implement add(x) in a RedBlackTree, we perform a standard BinarySearchTree insertion to add a new leaf, u, with u.x = x and set u.colour = red. Note that this does not change the black height of any node, so it does not violate the black-height property. It may, however, violate the left-leaning property (if u is the right child of its parent), and it may violate the no-red-edge property (if u’s parent is red). To restore these properties, we call the method add_fixup(u).

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy