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

ab_tree |
a-b tree | dictionary, d_array, sortseq |
[12] |

avl_tree |
AVL tree | dictionary, d_array | [5] |

bb_tree |
BB[] tree | dictionary, d_array, sortseq | [13] |

ch_hashing |
hashing with chaining | h_array |
[58] |

dp_hashing |
dyn. perf. hashing | h_array | [24], [88] |

pers_tree |
persistent tree | p_dictionary |
[25] |

rb_tree |
red-black tree | dictionary, d_array, sortseq | [42] |

rs_tree |
rand. search tree | dictionary, d_array, sortseq | [2] |

skiplist |
skip lists | dictionary, d_array, sortseq |
[77] |

Priority Queues

f_heap |
Fibonnacci heap | priority_queue |
[36] |

p_heap |
pairing heap | priority_queue | [84] |

k_heap |
k-nary heap | priority_queue | [58] |

m_heap |
monotonic heap | priority_queue | [58] |

eb_tree |
Emde-Boas tree | priority_queue | [29], [88] |

range_tree |
range tree | d2_dictionary, point_set |
[90], [57] |

seg_tree |
segment tree | seg_set |
[8], [27] |

ps_tree |
priority search tree | -- | [60] |

iv_tree |
interval tree | interval_set |
[59], [27] |

delaunay_tree |
delaunay tree | point_set |
[22] |