/red-black-tree

Implementation of a self-balancing binary search tree.

Primary LanguageC++

red_black_tree

This is an implementation of a red black tree which is a self-balancing binary search tree.

After each insert/delete operation, There are specific rules that must be respected to enforce the balance. If they have been violated, they must be restored by recoloring and rotations.

Red-Black tree Properties

  • Each node is either black or red.

  • The root is always black.

  • A red node must not have red children.

  • All paths from a node to the leaves contain the same number of black nodes.