Learning JavaScript Data Structures and Algorithms - Third Edition

Red-Black tree

Like the AVL tree, the Red-Black tree is also a self-balancing binary search tree. We learned that inserting or removing a node from the AVL tree might cause rotations, so if we need a self-balancing tree that involves many frequent insertions or deletions, then the Red-Black tree is preferred. If the insertions and deletions are less frequent (we are interest in frequent search operations), then the AVL tree is preferred over the Red-Black tree.

In the Red-Black tree, every node follows the rules which are listed as follows:

1. As the name of the tree suggests, each node is either red or black.
2. The root of the tree is black.
3. All of the leaves are black (nodes represented with the NULL reference).
4. If a node is red, then both ...