[ Home Page ] [ Eiffel Archive ] [ Eiffel Classes and Clusters ]

Arc de Triomphe clipart (2486 bytes)

RBT: A Red-Black Tree Library


Written by Mike Durian.

Extracted from midi-eiffel by Geoff Eldridge

red_black_tree_0_2.zip (11,000 bytes) source code

ftp://ftp.boogie.com/pub/midi latest version location (Mikes place)


RBT: A Red-Black Tree Library

Balanced trees are a well-known solution to the problem of maintaining an ordered list of items so as to be able to quickly perform the operations insert, delete, and access. These operations can be executed in O(log n) time on a list of n elements if the list is represented by a balanced tree. Several types of balanced tree structures have been studied in the literature, including AVL-trees, B-trees, and red-black trees. With both red-black and B-trees, the more complicated list operations split and concatenate, can also be performed in logarithmic time.

A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black.

Red-black trees: Trees which remain balanced - and thus guarantee O(logn) search times - in a dynamic environment. Or more importantly, since any tree can be re-balanced - but at considerable cost - can be re-balanced in O(logn) time.

The SmallEiffel web site is:

http://SmallEiffel.loria.fr/
mike
durian@boogie.com

Geoff Eldridge geoff@elj.com December 31, 1999


[ Home Page ] [ Eiffel Archive ] [ Eiffel Classes and Clusters ]