# 1. Red-Black Trees
# BinaryTree performs it's operations in O(h) time. Thus, the operations are fast if the height of the search tree is small.
# If its height is large, operations slow down.
# Red-black trees are one of many search-trees that are balanced in order to guarantee that basic operations take O(log n).
# A red-black tree is a BST with one extra bit of storage per node: its color, which can be either RED or BLACK.
# -see chapter 13 of Cormen et al.

# 2. AVL trees
# An AVL tree is a BST that is height balanced: for each node X, the heights of the left and right subtrees of X differ by at most 1.
# To implement an AVL tree, we maintain an extra attribute in each node: X.h is the height of node X
# -see chapter 13-3 of Cormen et al.

# 3. Treap
# Randomly built binary search trees tend to be balanced. Thus, we can randomly permute the inputs if all of them are known in advance.
# What if we do not have all the items at once?
# A Treap is a BST that is self-randomised so as to achive node ordering.
# For each node X, we assign X.priority, which is a random number chosen independently for each node.
# -see chapter 13-4 of Cormen et al.

# 4. B-tree
# They are balanced search trees designed to work well on disks.
# B-trees are similar to red-black trees, but they are better at minimizing disk I/O operations.
# Many database systems use B-trees to store information
# -see chapter 18 of Cormen et al.