AhmedKhaledAK/DSBasic

Basic data structures and algorithms implemented in Java. Graphs, B-Trees, Minimum Spanning Trees, Red-black Trees and more.

DSBasic

Currently in the repo:

• Red-black Trees: https://github.com/AhmedKhaledAK/DSBasic/tree/master/src/akopensource/rbtrees

  • Insertion
  • Deletion
  • Search
  • Get Minimum
  • Successor
  • Inorder traversal and level order traversal

• Graphs: https://github.com/AhmedKhaledAK/DSBasic/tree/master/src/akopensource/graphs

  • Adjacency List representation
  • Matrix representation
  • Breadth-first traversal
  • Calculating shortest-paths of unweighted graphs using BFS
  • Depth-first traversal
  • Getting predecessor of each vertex using BFS and DFS
  • Timestamps of vertices in DFS, classifications of edges, and topological sort
  • Transpose graphs and strongly connected components
  • Connected components using Disjoint Sets
  • Single-source shortest paths using Dijkstra's algorithm
  • Bellman Ford's algorithm

• Disjoint Sets: https://github.com/AhmedKhaledAK/DSBasic/tree/master/src/akopensource/disjointsets

  • Make-Set operation
  • Find-Set operation
  • Union operation
  • Union by rank
  • Path compression

• Minimum Spanning Trees: https://github.com/AhmedKhaledAK/DSBasic/tree/master/src/akopensource/graphs

  • Prim's algorithm
  • Kruskal's algorithm

• Sorting Algorithms: https://github.com/AhmedKhaledAK/DSBasic/tree/master/src/akopensource/sorting

  • Quicksort
  • Heapsort
  • Mergesort
  • Bubblesort
  • Insertion sort
  • Selection sort

• B-trees: https://github.com/AhmedKhaledAK/DSBasic/tree/master/src/akopensource/btrees

  • Insertion
  • Search
  • Predecessor
  • Successor
  • Deletion (case 1)

• Huffman codes: https://github.com/AhmedKhaledAK/DSBasic/tree/master/src/akopensource/huffman

• Miscellaneous:

  • Doubly LinkedList
  • Generating Random Arrays
  • Heap
  • Greatest Common Divisor algorithms
  • Tuples (triplets and pairs)