Red-black tree

A self-balancing binary search tree that allows for quick execution of basic operations: adding, deleting, and finding nodes. The balance is achieved by introducing an additional node attribute - "color". This attribute can take one of two possible values - "black" or "red". Leaf nodes in a red-black tree don't contain data, so they don't require memory allocation - it's sufficient to simply store a null pointer to the child in the parent node.

A very fast, useful, and practical data structure. For example, the std::map container in C++ is implemented using a red-black tree.

You may have read that during serious algorithmic interviews at FAANG companies, candidates are "forced to rotate red-black trees on the whiteboard". This "rotation" is actually the balancing process - after inserting or deleting an element, the tree needs to be rebalanced. You can familiarize yourself with the approximate amount of code required here or here.