O(logN) lookup, Ө(N!) fun.
Red/Black Tree
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 always greater.

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 listed below.

  1. 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.
  2. Red-Black trees (implemented here) require all nodes to be approximately balanced using specific properties. The less rigorous balance constraints result in slower lookup than AVL trees but faster insertion and deletion operations.
  3. 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!