Dictionaries

This page contains implementations of dictionary data structures.

Separate C source files and descriptions are provided for each dictionary implementation.

[Binary Search Tree, AVL Tree, 2-3 Tree, Red-Black Tree, Skip List, Hash Table, Digital Search Tree, Radix Search Trie]

These dictionaries can be used by algorithms in this repository.

Common Files

The header file dict_info.h defines a common structure type that each dictionary can provide. A program which uses this common structure type is then able to use different dictionaries interchangeably, as done by the supplied example program.

Example program: dict_test.c
Related: [Timing Library]
Experimental data: cpu time results

Binary Search Tree

C source files: bst.c bst.h
example program: bst_test.c
picture
description

AVL Tree

C source files: avl.c avl.h
example program: avl_test.c
picture
description

2-3 Tree

Standard 2-3 tree:

C source files: tree23.c tree23.h
example program: tree23_test.c
picture
description

Modified 2-3 tree, supporting delete_min() in O(1) worst case time:

C source files: tree23_ext.c tree23_ext.h
example program: tree23_ext_test.c
description

Digital Search Tree

C source files: dst.c dst.h
example program: dtree_test.c
pictures: (insert) (delete)
description

Radix Search Trie

C source files: rst.c rst.h
example program: rst_test.c
pictures: (insert) (delete)
description