Data Structures

Binary Search Tree

The Binary Search Tree represents an ordered symbol table of generic key-value 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 key-value pair with the largest key.

Worst Case Complexity: O(N)

Balanced Tree Complexity: O(lg N)

delete_min()[source]

Remove the key-value 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 key-value 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)

select_key(rank)[source]

Return the key with rank equal to ‘rank’

Worst Case Complexity: O(N)

Balanced Tree Complexity: O(lg N)

size()[source]

Return the number of nodes in the BST

Worst Case Complexity: O(1)

Balanced Tree Complexity: O(1)

class algorithms.data_structures.binary_search_tree.Node(key=None, val=None, size_of_subtree=1)[source]

Bases: object

Implementation of a Node in a Binary Search Tree.

Directed Graph

The Digraph class represents a directed graph of vertices which can be any hashable value. Parallel edges and self-loops are permitted.

Pseudo Code: http://algs4.cs.princeton.edu/42directed/Digraph.java.html

class algorithms.data_structures.digraph.Digraph[source]
add_edge(src, dest)[source]

Adds an undirected edge ‘src’-‘dest’ to the graph.

Worst Case Complexity O(1)

adj(src)[source]

Returns the vertices adjacent to vertex ‘src’.

Worst Case Complexity: O(1)

edge_count()[source]

Returns the number of edges in the graph.

Worst Case Complexity: O(1)

outdegree(src)[source]

Returns the degree of the vertex ‘src’

Worst Case Complexity: O(1)

reverse()[source]

Returns the reverse of this digraph

Worst Case Complexity: O(V+E)

vertex_count()[source]

Returns the number of vertices in the graph.

Worst Case Complexity: O(1)

vertices()[source]

Returns an iterable of all the vertices in the graph.

Worst Case Complexity: O(V)

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 First-In-First-Out (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

class algorithms.data_structures.queue.Queue[source]
add(value)[source]

Add element as the last item in the Queue.

Worst Case Complexity: O(1)

is_empty()[source]

Returns a boolean indicating if the Queue is empty.

Worst Case Complexity: O(1)

remove()[source]

Remove element from the front of the Queue and return it’s value.

Worst Case Complexity: O(1)

size()[source]

Return size of the Queue.

Worst Case Complexity: O(1)

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

class algorithms.data_structures.singly_linked_list.Node(data=None, next=None)[source]
get_data()[source]
get_next()[source]
set_data(data)[source]
set_next(next)[source]
class algorithms.data_structures.singly_linked_list.SinglyLinkedList[source]
add(value)[source]

Add element to list

Time Complexity: O(N)

remove(value)[source]

Remove element from list

Time Complexity: O(N)

search(value)[source]

Search for value in list

Time Complexity: O(N)

size()[source]

Return size of 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

class algorithms.data_structures.stack.Stack[source]
add(value)[source]

Add element at last

Time Complexity: O(1)

is_empty()[source]

1 value returned on empty 0 value returned on not empty

Time Complexity: O(1)

remove()[source]

Remove element from last return value

Time Complexity: O(1)

size()[source]

Return size of stack

Time Complexity: O(1)

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

class algorithms.data_structures.undirected_graph.Undirected_Graph[source]
add_edge(src, dest)[source]

Adds an undirected edge ‘src’-‘dest’ to the graph.

Time Complexity: O(1)

adj(src)[source]

Returns the vertices adjacent to vertex ‘src’.

Time Complexity: O(1)

degree(src)[source]

Returns the degree of the vertex ‘src’

Time Complexity: O(1)

edge_count()[source]

Returns the number of edges in the graph.

Time Complexity: O(1)

vertex_count()[source]

Returns the number of vertices in the graph.

Time Complexity: O(1)

vertices()[source]

Returns an iterable of all the vertices in the graph.

Time Complexity: O(V)

Union Find:

A disjoint-set data structure, also called union-find 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 linked-list)

Psuedo Code: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

class algorithms.data_structures.union_find.UnionFind(N)[source]
find(x)[source]
is_connected(x, y)[source]
make_set(x)[source]
union(x, y)[source]

Union Find by Rank

A disjoint-set data structure, also called union-find 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/Disjoint-set_data_structure

class algorithms.data_structures.union_find_by_rank.UnionFindByRank(N)[source]
find(x)[source]
is_connected(x, y)[source]
make_set(x)[source]
union(x, y)[source]

Union Find with path compression

A disjoint-set data structure, also called union-find 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 fast-growing Ackermann function.

Psuedo Code: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

class algorithms.data_structures.union_find_with_path_compression.UnionFindWithPathCompression(N)[source]
find(x)[source]
is_connected(x, y)[source]
make_set(x)[source]
parent(x)[source]
union(x, y)[source]