next up previous contents index
Next: User Implementations Up: Implementations Previous: Implementations   Contents   Index

Subsections


List of data structures

This section lists the data structures for dictionaries, dictionary arrays, priority queues, and geometric data types currently contained in LEDA. For each of the data structures its name and type, the list of LEDA data types it can implement, and a literature reference are given. Before using a data structures xyz the corresponding header file <LEDA/impl/xyz.h> has to be included (cf. section Specifications for an example).

Dictionaries

ab_tree a-b tree dictionary, d_array, sortseq [11]
avl_tree AVL tree dictionary, d_array [5]
bb_tree BB[$ \alpha$] tree dictionary, d_array, sortseq [12]
ch_hashing hashing with chaining h_array [52]
dp_hashing dyn. perf. hashing h_array [21], [78]
pers_tree persistent tree p_dictionary [22]
rb_tree red-black tree dictionary, d_array, sortseq [38]
rs_tree rand. search tree dictionary, d_array, sortseq [2]
skiplist skip lists dictionary, d_array, sortseq []


Priority Queues

f_heap Fibonnacci heap priority_queue [32]
p_heap pairing heap priority_queue [75]
k_heap k-nary heap priority_queue [52]
m_heap monotonic heap priority_queue [52]
eb_tree Emde-Boas tree priority_queue [26], [78]

Geometry

range_tree range tree d2_dictionary, point_set [80], [51]
seg_tree segment tree seg_set [7], [24]
ps_tree priority search tree -- [54]
iv_tree interval tree interval_set [53], [24]
delaunay_tree delaunay tree point_set [19]


next up previous contents index
Next: User Implementations Up: Implementations Previous: Implementations   Contents   Index
LEDA research project
2000-02-09