Non-Linear DS with Built-in Libraries

Non-Linear DS with Built-in Libraries

For some problems, linear storage is not the best way to store data. You might need some non-linear data structures.

Here are a list and some basics about them.

Balanced Binary Search Trees: C++ STL map/set: 

BST is one way to organize data in a tree structure. Here you can learn all the basics of a binary search tree: https://rishabhjainiitbhu.blogspot.com/2019/07/binary-search-tree-implementation-in-c.html. The BST is simply an application of divide and conquers strategy. Organizing the data like this allows for $O(log n)$ search and deletion.

STL set and STL maps are based on BSTs. Here is the link to learn about maps in C++. https://rishabhjainiitbhu.blogspot.com/2019/07/c-stl-maps.html

Heaps: C++ STL priority_queue

Heap also organizes the data in a tree. Heap is also a binary tree, except that it is a complete tree. Here is the link to learn all about trees: https://rishabhjainiitbhu.blogspot.com/2019/07/introduction-to-trees-c-data-structures.html.

In Heap: items on the left and right subtrees of x are smaller than(or equal) to x. This guarantees that the top(or the root) is always the maximum element.

There is no notion of search in a Heap. Heap allows for the fast extraction (deletion) of the maximum element.

priority_queues are implemented using heaps.

Here is the link to learn priority_queues: https://rishabhjainiitbhu.blogspot.com/2019/08/c-stl-priorityqueues.html

Hash Table: C++ STL unordered_map

Hash Table can usually be substituted with BSTs. Creating Hashing functions is no easy. Hash_tables are used to implement the unordered_map in c++ STl.