The default trees have the following elements inserted
in order: [2, 1, 4, 5, 9, 3, 6, 7]
Try it out yourself! Watch how the Red-Black tree rearranges
itself to maintain a shorter height than the vanilla BST.
What's going on here?
A Binary Search Tree (BST) is a data structure that is
known for its quick and generally predictable behavior in
searching, sorting, insertion, and deletion. It differs
a Binary Tree in that the value of an element's left child
is lesser and the value of an element's right child is
If BST nodes are inserted in a specific order, the tree
will essentially become a linked list and lose its
quick lookup properties. Tree rotations allow us to maintain
a reasonable tree height while maintaing its BST properties.
Some BST's with special properties have been created to
use rotations to solve this problem. The most common are
- AVL trees require all nodes be balanced, where the
difference in heights of child nodes is no more than 1.
This results in guaranteed O(logN) lookup.
- Red-Black trees (implemented here) require
all nodes to be approximately balanced using specific
The less rigorous balance constraints result in slower
lookup than AVL trees but faster insertion and deletion operations.
- Splay trees rotate recently added or searched
elements to the root of the BST. This results in extremely
fast lookup for data that is frequently accessed.
Find more on my Github (readme)
Try running the Jasmine tests