/data_structs

Primary LanguagePythonMIT LicenseMIT

Build Status Coverage Status

#More Data Structures for Python 401

Binary Search Tree

Implement a binary search tree with insert(), search() size(), depth(), contains(), and balance() methods.

BST Traversals

Implement the following traversals:

  • In-order
  • Pre-order
  • Post-order
  • Breadth-first

https://en.wikipedia.org/wiki/Tree_traversal Each returns a generator that will yield nodes according to their conventions.

Hash Table

Implemented a hash table that has the option to use either a complex or naive hash.

Sorting Algorithms

Implemented the following sorting algorithms:

  • Bubble Sort - O(n^2), where n is the number of elements to be sorted
  • Insertion Sort - O(n^2), where n is the number of elements to be sorted
  • Mergesort - O(n * log(n)), where n is the number of elements to be sorted
  • Quicksort - O(n * log(n)), where n is the number of elements to be sorted
  • Radix Sort - O(n * k), where k is the number of digits in the largest number to be sorted

Tries

Contains an implementation of a trie, along with traversals and an autocomplete method.

  • Traversal - O(n), where n is the number of letters in the sub-trie branching from the input string
  • Autocomplete - O(n), where n is the number of letters in the sub-trie branching from the input string