gb_trees

gb_trees

Module

gb_trees

Module summary

General Balanced Trees

Description

An efficient implementation of Prof. Arne Andersson's General Balanced Trees. These have no storage overhead compared to unbalanced binary trees, and their performance is in general better than AVL trees.

This module considers two keys as different if and only if they do not compare equal (==).

Data structure

Data structure:

      
- {Size, Tree}, where `Tree' is composed of nodes of the form:
  - {Key, Value, Smaller, Bigger}, and the "empty tree" node:
  - nil.

There is no attempt to balance trees after deletions. Since deletions do not increase the height of a tree, this should be OK.

Original balance condition h(T) <= ceil(c * log(|T|)) has been changed to the similar (but not