Self-balancing Trees

In a previous blog post I describe a data structure which require the use of a self-balancing binary search tree.

Few need to implement their own self-balancing trees, but since two previous comments referred to AVL and red/black trees respectively, I should give a shout-out to Arne Andersson and his paper titled Binary Search Trees Made Simple (PDF).

The paper introduces AA trees which are simple to implement but understanding the logic for when to skew/rotate is not clear from the paper. Julienne Walker filled that hole with a great tutorial about AA trees and how they (like red/black trees) stem from B-trees of order 3 (PDF).