COP4415 - Final Exam

PPTs: BSTs to Hash Tables, Quiz 9

binary search trees

• abstract data type

• used for indexing data points

• data structure made of nodes and pointers

height

length of the longest path from the root to a leaf in a tree is known as the ______

0

a tree with only 1 node has the height of __

binary tree

each node can have at most 2 children

full binary tree

each node (other than leaves) has exactly 2 children

complete binary tree

every level (except maybe last) is completely filled and all nodes are as far left as possible

full, not complete

full or complete?

complete, not full

full or complete?

neither

full or complete?

both

full or complete?

depth first search

explores a path all the way to a leaf before backtracking and exploring another path

breadth first search

• explores levels in order

• every node in a level should be visited before going to next level

• starts at root, ends at leaves

binary tree traversals

1\.) preorder

2\.) inorder

3\.) postorder

preorder traversal

root is visited before its left and right subtrees

inorder traversal

root is visited between the subtrees

preorder traversal

What type of traversal is this?

void traverse(Node\* p) {

if(p != NULL) {

cout << p→data << endl;

traverse(p→left_child);

traverse(p→right_child);

}

}

inorder traversal

What type of traversal is this?

void traverse(Node\* p) {

if(p != NULL) {

traverse(p→left_child);

cout << p→data << endl;

traverse(p→right_child);

}

}

postorder traversal

What type of traversal is this?

void traverse(Node\* p) {

if(p != NULL) {

traverse(p→left_child);

traverse(p→right_child);

cout << p→data << endl;

}

}

4, 8, 1, 3, 9, 2, 5, 0, 6

What is the preorder traversal for this tree?

3, 1, 9, 8, 2, 4, 0, 6, 5

What is the inorder traversal for this tree?

3, 9, 1, 2, 8, 6, 0, 5, 4

What is the postorder traversal for this tree?

O(logn)

BST time complexity (for insert, search, delete) for a balanced tree

O(n)

BST time complexity (for insert, search, delete) for an unbalanced tree

balanced binary tree

height of left subtree and right subtree of any node differ by at most 1

self-balancing binary tree

height-balanced BSTs that automatically keeps height as small as possible when insertion/deletion is performed on tree

O(logn)

self-balancing BST time complexity

height

• total number of nodes in the longest path from the root to a leaf

• if no node, height is 0

• if 1 node, height is 1

height

• length of the longest path from the root to a leaf

• if no node, height is -1

• if 1 node, height is 0

AVL

• a self-balancing BST

• difference between the height of the left and right subtree cannot be more than 1 for all node (balanced)

O(logn)

AVL time complexity (for delete, search, insert)

AVL formal definition

1.) All empty trees are also AVL trees

2.) If T is a non-empty BST with TL and TR as its left and right subtrees, then T is an AVL tree iff:

• TL and TR are also AVL trees

• |hL - hR| <= 1

balance factor

• height of the left subtree minus the height of the right subtree

• hL - hR or hR - hL

left rotation

What do we do for this case:

1\.) Inserting a new node into the right subtree of a right child (RR)

right rotation

What do we do for this case:

2\.) Inserting a new node into the left subtree of a left child (LL) (symmetric case)

right rotation, then left rotation

What do we do for this case:

3\.) Inserting a new node into the left subtree of a right child (RL)

left rotation, then right rotation

What do we do for this case:

4\.) Inserting a new node into the right subtree of a left child (LR) (symmetric case)

right rotation

This is what type of rotation?

left rotation

This is what type of rotation?

heap

• an abstract data type

• must be a complete binary tree

max heap

• all values stored in the subtree of a given node are less than or equal to the value stored in the node

• root stores highest value of any given subtree

min heap

• all values stored in the subtree of a given node are greater than or equal to the value stored in that node

• root stores the smallest value of any given subtree

binary heaps

used to implement another abstract data type → priority queues

priority queue

• elements are inserted in order of arrival

• element with highest priority is processed/removed first

O(logn)

time complexity of percolate up/down

True

(T/F) In a priority queue, we always delete the element with the highest priority (the root)

O(logn)

time complexity of deleting nodes from binary heap

O(nlogn)

time complexity of building a heap from scratch

O(n)

heapify time complexity

O(nlogn)

heap sort time complexity

graph

* collection of nodes (vertices) and the connections between them (edges)

simple graph

G = (V, E) consists of a finite set denoted by V and a collection E of unordered pairs {u, v} of distinct elements from V

vertex

• each element of V

• AKA point, node

edge

• each element of E

• AKA link

order of graph

• number of vertices (cardinality of V)

• denoted by |V|

size of graph

• cardinality of E

• denoted by |E|

path

sequence of edges denoted by v1, v2, …., v_n-1, v_n

cycle

If v1 = v_n, then the path is a _______.

adjacent

2 vertices are _____ or neighbors if there’s an edge between them

degree

number of edges incident with a vertex v is the _____ of the vertex

graph representations

1\.) adjacency list

2\.) adjacency matrix

adjacency list

• each vertex adjacent to a given vertex is listed

• space: O(|V| + |E|)

• takes O(|V|) time to check if vertex u is adjacent to vertex v

adjacency matrix

• |V| x |V| binary matrix

• A(u,v) = 1 if (u,v) is an edge, else it equals 0

• space: O( |V|^2 )

• O(1) time to check if vertex u is adjacent to vertex v

• (|V|) time to list all neighbors

BFS theorem

A vertex v is discovered in Round k iff the shortest distance of v from source S is k

O(|V| + |E|)

total time for BFS algorithm

O(|V| + |E|)

total space for BFS algorithm

BFS algorithm

* implemented using common queue:
* when vertex is discovered, put it at end of queue
* next vertex to visit is the one at front of queue
* finished when no more vertices in queue

DFS algorithm

An alternative algorithm to find all vertices reachable from a particular source vertex S

O(|V| + |E|)

total time for DFS

tree

connected graph with no cycles

n-1

a tree with n vertices has ____ edges

spanning tree

• a tree that spans undirected and connected graph G and is a subgraph of G

• includes every vertex of G and every edge in the tree belongs to G

cost of spanning tree

sum of the weights of all edges in the tree

minimum spanning tree

spanning tree where the cost is minimum among all the spanning trees

spanning forest

if graph isn’t connected, there is a spanning tree for each connected component of the graph

greedy algorithm

• simple, intuitive algorithm used in optimization problems

• tries to find overall optimal way to solve entire problem

kruskal’s algorithm

• builds spanning tree by adding edges one by one into growing spanning tree

• follows greedy approach → finds an edge with least weight and adds it to tree

O(|V| log|V|)

kruskal’s algorithm time complexity

prim’s algorithm

• keeps track of vertices already included in MST

• picks vertices with minimum key value to add to MST and updates key value of all adjacent vertices

O(E logV)

prim’s algorithm time complexity

selection sort

• Given an array of n numbers, sort the array in n steps

• Steps

  • Scan the entire array and find smallest element

  • Swap smallest element with element at index i

  • Increment i

  • Repeat until i = n

O(n^2)

selection sort time complexity

merge sort

• Using divide and conquer, break down the array and sort each part

• Then, merge the pieces back together

O(nlogn)

merge sort time complexity

table

abstract data type that stores and retrieves

record

each individual row in the table

hash table

implemented using an array to store records in unsorted order

unsorted array

runtime complexity:

• adding a record: O(1)

• deleting a record: O(n)

• searching for a record: O(n)

sorted array

runtime complexity:

• adding a record: O(n)

• deleting a record: O(n)

• searching for a record: O(logn) → binary search

binary tree

runtime complexity:

• adding a record: O(logn)

• deleting a record: O(logn)

• searching for a record: O(logn)

direct access table

runtime complexity:

• adding a record: O(1)

• deleting a record: O(1)

• searching for a record: O(1)

direct access table

• special type of array

• each record has own exclusive cell → large array

• pro: O(1) time complexity for everythin

• con: space complexity is huge

hash table

array of table items, where index is calculated by a hash function

hash function

• a mathematical calculation that maps the search key to an index in a hash table

• time complexity for calculating: O(1)

hashing

• a way to access a table/array in constant time

• uses a hash function and collision resolution scheme

collision

• when a hash function maps 2+ search keys into the same location in a hash table

• h(key1) = h(key2)

hash functions for integers

1\.) Selecting digits

2\.) Folding

3\.) Modulo arithmetic

selecting digits

• only select a few digits instead of whole integer

• ex: h(4324494421) = 432

• pro: fast and easy to calculate

• con: does not distribute randomly

folding

• adds digits of the integer together

• ex: h(123456789) = 1+2+3+4+5+6+7+8+9 = 45

• can add in different ways for hash tables of diff sizes:

  • ex: h(123456789) = 123+456+789 = 1368

modulo arithmetic

• uses prime number for table size to reduce collisions

• h(x) = x mod (tableSize)

• ex: h(123456789) = 123456789 mod 31 = 2

perfect hash function

ideal situation where hash function maps each search key into a diff location in the hash table (no collisions)