Data structures and algorithms
Implementations of some data structures and algorithms
Table of contents
Hashtable
Hashtable template class implementation with Separate chaining collision resolving method
- hash function
- rehashing in case of load ratio limit reached
- insert
- remove by key
- find by key
Substring search
Rabin-Karp string-searching algorithm implementation Given a some number of patterns stored in a hashtable we need to count a number of each pattern occerrences in a string
Red-Black Tree
Left leaning red-black tree implementation
- node inserting
- hight calculation
- black-hight calculation
- tree traversal
- prefix
- infix
- postfix
- breadth-first search (BFS) with Queue implementation
Graph
Simple Bellman–Ford algorithm to compute the shortest path from a single vertex to all of the other vertices in a weighted digraph Also there is a BFS search implementation for graph
Encoding
- Building a prefix-search tree by Shannon–Fano and Huffman methods
- LZ77 and LZ78 algorithm implementations