How does inserting or deleting nodes affect a Red-Black tree?

Technology CommunityCategory: Binary TreeHow does inserting or deleting nodes affect a Red-Black tree?
VietMX Staff asked 5 months ago

To ensure that its color scheme and properties don’t get thrown off, red-black trees employ a key operation known as rotation.

Rotation is a binary operation, between a parent node and one of its children, that swaps nodes and modifys their pointers while preserving the inorder traversal of the tree (so that elements are still sorted).

There are two types of rotations: left rotation and right rotation.

  • Left rotation swaps the parent node with its right child, while
  • Right rotation swaps the parent node with its left child.

red-black-tree