gb_trees

gb_trees

Module

gb_trees

Module summary

General balanced trees.

Description

This module provides Prof. Arne Andersson's General Balanced Trees. These have no storage overhead compared to unbalanced binary trees, and their performance is better than AVL trees.

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

Data Structure

{Size, Tree}

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. As deletions do not increase the height of a tree, this should be OK.

The original balance condition h(T) <= ceil(c * log(|T|)) has been changed to the sim