DataStructures

AVL Tree

avl_tree.cpp contains an AVL tree implementation with recursive insert, delete, look-up and indexing operations. The code is a solution to https://www.spoj.com/problems/ORDERSET.

Insertion $O(\log(n))$

Deletion $O(\log(n))$

Lookup $O(\log(n))$

Indexing $O(\log(n))$

Binary Search Tree

tree.cpp contains an unbalanced BST implementation with recursive insert, delete and look-up operations. The code is a solution to https://www.urionlinejudge.com.br/judge/en/problems/view/1201.

Insertion $O(n)$

Deletion $O(n)$

Lookup $O(n)$

Disjoint Set Union

dsu.cpp contains a DSU implementation with efficient union and find operations. The code is a solution to https://www.spoj.com/problems/ADABRANC.

Union $O(\alpha(n))$

Find $O(\alpha(n))$

Fenwick Tree

fenwick_tree.cpp contains a binary indexed tree implementation with efficient element update and range operations. The code is a solution to https://cses.fi/problemset/task/1651.

Add $O(\log(n))$

Prefix $O(\log(n))$

Segment Tree

segment_tree.cpp contains an array-based segment tree implementation with iterative range and update operations. The code is a solution to https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/A.

Range $O(\log(n))$

Update $O(\log(n))$

Skip List

skip_list.cpp contains the implementation of a skip list with (in expectation) logarithmic insert, delete, look-up and indexing operations. The code is a solution to https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/smallest-subarray-2-d6530e0b/.

This is a randomized data structure. The below time complexities hold only in expectation.

Insertion $O(\log(n))$

Deletion $O(\log(n))$

Lookup $O(\log(n))$

Indexing $O(\log(n))$

Trie

trie.cpp contains an array-based trie implementation with insert and look-up operations. The code is a solution to https://www.spoj.com/problems/ADAINDEX.

Insertion $O(|s|)$

Lookup $O(|s|)$