amitbansal7 / data-structures-and-algorithms

Implementation of various Data Structures and algorithms - Linked List, Stacks, Queues, Binary Search Tree, AVL tree,Red Black Trees, Trie, Graph Algorithms, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Segment Trees etc.

DataStructures and Algorithms in C/C++

This code is written by Amit Bansal while learning Data structures and algorithms. References GFG, NPTEL, CLRS.

This repository contains:

Singly Linked List.

        Add Two Numbers Represented By Linked List.
        Bubble Sort in Linked List
        Merge Sort in Linked List
        Merge Sorted Linked List
        Reverse a singly Linked List with or without using stack

Doubly Linked List.

Circular Linked List.

        Sorted Insert

Stack using array and Linked List.

Queue using array and Linked List.

Priority Queue.

Sorting:

        Bubble Sort
        Heap Sort
        Insertion Sort
        Merge Sort
        Quick Sort
        Selection Sort

Binary Search Tree

        Insertion
        Deletion
        Preorder traversal
        Inorder traversal
        Postorder traversal
        Level order traversal
        Find Height of a Binary Search Tree
        Check if a Tree is Binary Search Tree or not(2 methods)
        Find Max and Min element in Binary Search Tree

AVL trees

        a.Insertion
        b.Deletion

Red Black Trees

        Insertion
        Deletion

Tries

        Insert
        Delete
        Search

Graphs

        Breadth First Search
        Depth Search Search
        Kosaraju's algorithm for strongly connected components
        Dijkstra's algorithm for single source shortest paths
        A* Search Algorithm
        Kruskal’s Minimum Spanning Tree Algorithm
        Topological Sorting
        Prims algorithm for minimum spanning tree using STL
        Floyd Warshall Algorithm for all pairs shortest paths
        Bellmanford algorithm for single source shortest path and negative edge cycle detection
        Detect a cycle using DFS
        Sortest Paths using Breadth First Search
        Check if an undirected Graph is eulerian.
        Find diameter of a tree using BFS
        Check if a graph is Bipartite using BFS
        Longest path in a directed acyclic graph

Flow Networks

        Ford-Fulkerson Algorithm for Maximum Flow

Greedy Algorithms

        Activity Selection Problem.
        Kruskal’s Minimum Spanning Tree Algorithm
        Dijkstra's algorithm for single source shortest paths
        Minimize Lateness problem
        Huffman Coding

Dynamic Programming

        Boolean Parenthesization Problem
        Edit Distance
        Knapsack problem with repetitions
        Knapsack Problem
        Longest Increasing Subsequence
        Maximum Value Contiguous Subsequence
        Optimal Strategy for a Game
        Optimal binary search trees
        RNA Secondary structure
        Rod Cutting
        Balanced Partition
        Box stacking
        Building Bridges
        Fibonnaci Numbers
        Longest increasing subsequence
        Maximum Value Contiguous Subsequence
        Subset Sum Problem
        Coin Changing Problem

Backtracking

        Alphacode: All possible codes that an integer string can generate
        String Permutation Algorithm
        Find Power Set of a set

Segment Tree

        Range Minimum Query
        Range Sum Query

data-structures-and-algorithms's Issues

The height of the node in AVL tree is wrong

I input the data 10, 4, 6. After the rebalance, the height of each of the three nodes should be ZERO. However, in your AVL tree code, the height isn't ZERO. You can check it.

4.Stack no free

push data is not free

RBT segfaults

Make an RBT Tree with elements from 1 to 21, including both. Now try to delete 12 the program will segfault for trying to illegally write to memory via the line

            x->parent = y;

from the main else block in RB_delete