In this lab session we will explore a couple of techniques for implementing a balanced binary tree.
- Balance on demand - This is one of the easiest and under certain operating conditions the most efficient way of balancing a binary search tree. Decompose an unbalanced tree into a vector, sort the vector, and recompose the tree starting from the mid-point of segments of the vector.
- Splay tree - This is a self balancing binary search tree implementation, which naturally lends itself to either a MRU or MFU type of use case.