dbmusings

data structures

Jul 06, 20242 min read

My notes on different data structures used to solve variety of problems in computer science.

Simple Graphs

No self loops, all edges are distinct.

simple graphs

For an undirected graph :
(|V|₂) represents the binomial coefficient n choose 2, which is the number of ways to choose 2 distinct elements from a set of n elements. This gives the maximum possible number of undirected edges in a simple graph with |V| vertices, where each edge connects two distinct vertices without any duplicates.

For a directed graph :
2(|V|₂) represents twice the binomial coefficient. This is because in a directed graph, for every pair of distinct vertices, there can be two possible edges (one in each direction). So the maximum number of directed edges is twice the maximum number of undirected edges.

More Readings :

Trees

Heap : Heap is a complete binary tree.

  • heappush() and heappop() take . heappush() starts from leaf upto to the root node, and heappop() in the opposite direction comparing the element with the current node, traversing the height of the tree which .
    So for push(siftup)/pop(siftdown) we first maintain the complete binary tree property then max/min heap property.

  • heapsort is since after each element you pop, elements need to be reordered to maintain the max/min heap property takes

  • Heapify takes wherein it does siftdown while generating the heap. Starts with leaf nodes and decides whether or not to swap depending on the child nodes instead of looking at parent nodes in heappush or siftup.

Interval Search Trees :

Radix Trees :

Balancing a BST

Drawing presentable trees

Appendix