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]