List of Advanced Data Structures


This article has the list of 100+ Advanced Data Structures that you must understand to prepare to solve advanced problems and compete in competitions like ICPC, Google Code Jam, Facebook Hacker Cup and many more.

Following is the list of 100+ Advanced Data Structures:

Following are some of the ideas behind the Advanced Data Structures:

Segment Tree

Segment Tree is a Data Structure that is used to answer range queries (like Range Minimum Query) efficiently. There are different variants of Segment Tree each of which has used in different applications.

Interval Tree

Interval Tree is a modification of Binary Search Tree (BST) which is used to solve geometric problems such as find a point or line which is overlapping or enclosed in the rectangle.

Fenwick Tree/ Binary Indexed Tree

Fenwick Tree is similar to Segment Tree and is used to solve range queries. It is based on a different idea and is simpler and has less memory load than Segment Tree. It can be used with an invertible operation only. The variants of Fenwick Tree are:

Cartesian Tree

A Cartesian tree is a binary rooted tree data structure that can answer range queries can be answered by finding least common ancestors in the tree. An inorder traversal of the tree would give the original sequence used to form the tree. It is used as binary search tree for an ordered sequence.

A treap is a height balanced binary tree with heap properties. It is used to store a sequence in a tree, which allows for various applications like searching. It takes O(log N) time complexity for search, insert and delete operations and takes O(N) space complexity

X and Y fast trie

There are 2 variants:

X-fast trie is a data structure used to store integers from a bounded domain. It is a trie of hash tables and supports successor and predecessor operations in log log U time

Y-fast trie is a data structure used to store integers from a bounded domain. It has two data structures X fast trie and balanced binary search tree with the change being we operate on representative values r in X-fast tries, and the leaf nodes point to balanced binary search trees instead of values.

Aditya Chatterjee

Aditya Chatterjee

Aditya Chatterjee is an Independent Algorithmic Researcher, Software Developer and Technical Author. He is the founding member of OPENGENUS, an organization with focus on changing Internet consumption

Read More

Vote for Aditya Chatterjee for Top Writers 2021:

Tags