Self-balancing Trees

August 22nd, 2009

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).

[by Allan Odgaard]

3 Responses to “Self-balancing Trees”

  1. Nikolai Says:
    August 22nd, 2009 at 21:52

    Julienne's page is completely unreadable in Safari.

  2. Allan Odgaard Says:
    August 23rd, 2009 at 07:30

    Works fine for me, both Mobile Safari and Safari 4.0.3 under Leopard.

  3. Peter Lund Says:
    August 9th, 2012 at 16:45

    Hej Allan!

    take a look at left-leaning red-black trees.

Leave a Reply