OCaml Data Structures and Algorithms

A comprehensive library of data structures and algorithms implemented in OCaml.

This library is designed for educational purposes to demonstrate how common data structures and algorithms can be implemented in a functional programming language.

Data Structures

Tree-based Data Structures

• Binary Search Tree
• AVL Tree (Self-balancing)
• Red-Black Tree (Self-balancing)
• Splay Tree (Self-adjusting)
• Treap (Randomized BST)
• B-Tree (Multi-way search tree)
• Trie (Prefix tree)
• Segment Tree (Range queries)
• Fenwick Tree / Binary Indexed Tree (Prefix sums)
• Suffix Tree (Pattern matching)
• Union-Find / Disjoint Set (Connectivity)

Sorting Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort
• Counting Sort
• Radix Sort

Building

# Setup OPAM environment
eval $(opam env)

# Build the project
make build

# Run tests
make test

# Start OCaml REPL with library loaded
make utop

Usage

# Using sorting algorithms
open Ods

(* Using basic sorting *)
let sorted_list = Sorting.Bubble.sort [5; 2; 1; 4; 3];;
let sorted_array = Sorting.Quick.sort_array [|5; 2; 1; 4; 3|];;

(* Using automatic algorithm selection *)
let optimal_sort = Sorting.sort_list [5; 2; 1; 4; 3];;

# Using tree data structures
open Ods

(* Create and use an AVL tree *)
let avl = Trees.AVL.build [5; 3; 8; 1; 4; 7; 10];;
let has_value = Trees.AVL.member 5 avl;;
let values = Trees.AVL.inorder avl;;

Project Structure

/src
  /sorting        - Sorting algorithm implementations
  /trees          - Tree data structure implementations
  ods.ml          - Main library module
/test             - Test suite

License

MIT License