Data Structures¶
Binary Search Tree¶
The Binary Search Tree represents an ordered symbol table of generic keyvalue pairs. Keys must be comparable. Does not permit duplicate keys. When assocating a value with a key already present in the BST, the previous value is replaced by the new one. This implementation is for an unbalanced BST.
Pseudo Code: http://algs4.cs.princeton.edu/32bst

class
algorithms.data_structures.binary_search_tree.
BinarySearchTree
[source]¶ Bases:
object
Implementation of a Binary Search Tree.

ceiling_key
(key)[source]¶ Returns the smallest key that is greater than or equal to the given value ‘key’
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

contains
(key)[source]¶ Returns True if the BST contains ‘key’, False otherwise
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

delete
(key)[source]¶ Remove the node with key equal to ‘key’
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

delete_max
()[source]¶ Remove the keyvalue pair with the largest key.
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

delete_min
()[source]¶ Remove the keyvalue pair with the smallest key.
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

floor_key
(key)[source]¶ Returns the biggest key that is less than or equal to the given value ‘key’
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

get
(key)[source]¶ Return the value paired with ‘key’
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

is_empty
()[source]¶ Returns True if the BST is empty, False otherwise
Worst Case Complexity: O(1)
Balanced Tree Complexity: O(1)

keys
()[source]¶ Return all of the keys in the BST in aschending order
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(N)

max_key
()[source]¶ Return the maximum key in the BST
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

min_key
()[source]¶ Return the minimum key in the BST
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

put
(key, val)[source]¶ Add a new keyvalue pair.
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

rank
(key)[source]¶ Return the number of keys less than a given ‘key’.
Worst Case Complexity: O(N)
Balanced Tree Complexity: O(lg N)

Directed Graph¶
The Digraph class represents a directed graph of vertices which can be any hashable value. Parallel edges and selfloops are permitted.
Pseudo Code: http://algs4.cs.princeton.edu/42directed/Digraph.java.html
Queue¶
A Queue is a linear data structure, or more abstractly a sequential collection. The entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a FirstInFirstOut (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed.
Pseudo Code: https://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29
Singly Linked List¶
A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.
Pseudo Code: https://en.wikipedia.org/wiki/Linked_list
Stack¶
A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added.
Pseudo Code: https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29
Undirected Graph¶
The Undirected_Graph class represents an undirected graph of vertices which can be any hashable value.
Pseudo Code: http://algs4.cs.princeton.edu/41undirected/Graph.java.html
Union Find:¶
A disjointset data structure, also called unionfind data structure implements two functions:
union(A, B)  merge A’s set with B’s set
find(A)  finds what set A belongs to
Naive approach:
Find follows parent nodes until it reaches the root. Union combines two trees into one by attaching the root of one to the root of the other
Time Complexity : O(N) (a highly unbalanced tree might be created, nothing better a linkedlist)
Psuedo Code: http://en.wikipedia.org/wiki/Disjointset_data_structure
Union Find by Rank¶
A disjointset data structure, also called unionfind data structure implements two functions:
union(A, B)  merge A’s set with B’s set
find(A)  finds what set A belongs to
Union by rank approach: attach the smaller tree to the root of the larger tree
Time Complexity : O(logn)
Psuedo Code: http://en.wikipedia.org/wiki/Disjointset_data_structure
Union Find with path compression¶
A disjointset data structure, also called unionfind data structure implements two functions:
union(A, B)  merge A’s set with B’s set
find(A)  finds what set A belongs to
Union with path compression approach:
Each node visited on the way to a root node may as well be attached directly to the root node. attach the smaller tree to the root of the larger tree
Time Complexity : O(a(n)), where a(n) is the inverse of the function n=f(x)=A(x,x) and A is the extremely fastgrowing Ackermann function.
Psuedo Code: http://en.wikipedia.org/wiki/Disjointset_data_structure