Important to remember CISC220 Midterm 2

What differs a tree vs binary search tree?

a tree each node has 1 parent and 0 or more children in a BST each node has 1 parent and 0-2 children

What are nodes with no children called?

leaf

How do you remove a node with two children

look for a replacement node either in the left subtree right max or right subtree left min

How do you calculate the number of nodes in a BST?

2^levels-1 and 2^levels (not including 2^levels)

How do you figure out how many levels are in a BST?

log_2 (n)

If there are between 2^(levels-1) and 2^(levels) nodes, it will take at most _______________ steps to find any node.

level number

How can you tell if a BST is balanced?

at any node, the height of the left subtree and the height of the right subtree differ by ONE

AVL left rotation

unbalanced node = -2 and right child balance = -1

(x→leftChild→rightChild)

AVL right rotation

Unbalanced node = 2 and left child balance = 1

(x→rightChild→leftChild)

AVL Left right rotation

unbalance node = -2 and right child = 1

AVL Right left rotation

unbalanced node = 2 left child balance = -1

What is the time complexity for the best case for BST (balanced)?

O(log n)

What is the time complexity for the worst case for BST (unbalanced)?

O(n)

What is the time complexity for maintaining, finding, inserting, removing in an AVL tree?

O(log n)

What is the order for Pre-Order

root left right

What is the order for in order

left root right

What is the order for post order

children before parent

What is Pre-Order used for?

copying a tree

What is post-order used for

deleting a tree

What is In-Order used for?

Getting the order of a tree (BST)

What is QuickSort average run time? (Best case: unsorted algo)

O(n log n)

What is QuickSort average run time? (Worst Case: sorted algo)

O(n²)

What are some ways to make a sorted list of QuickSort closer to O(n log n)

• Scramble array before quicksort

• Use middle element of subarray as pivot

• use a random element of the array as pivot

• median of three elements as the pivot

• All of the above

All of the above

What is the logic for quicksort?

All values to the left are less than the pivot all values to the right are greater than pivot

What is merge sort algorithm?

Combine two sorted sequences into one larger sorted

What is best case time for merge sort?

O(n log n)

What is worst case time for merge sort?

O(n log n)

What is time complexity for merging in merge sort

O(n)

Identify which sorting algorithm this is

Merge Sort

Identify which sorting algorithm this is

Quick Sort

What are the characteristics of a set?

No Duplicates, no order, all data is the same type

Hash functions take a _________ and calculates a number that can be used as an _________ in the map

a. pizza; food

b. key; index

c index; key

key; index

What are three things we need to worry about when Hashing?

Hashing function, array size, collisions

What are the qualities of a good hashing function?

• maps all keys indices within the array

• distributes keys evenly throughout array

• avoids collisions

• computes quickly and consistently

Why is it important to have the array size prime for a hash function?

Spread remainder more evenly throughout the array

What should hash function be careful of in terms of hashing strings?

large num of shorter words and prefixes that words have in common

What is Chaining?

Make the hash array be an array of linked lists

What is linear probing?

Keep going to next index until empty space

what is quadratic probing?

jump using i^i (1×1, 2×2, 3×3….)

What is double hashing?

Use a second hash function is theres a collision at the first collision function

What are problems with linear clustering?

Clustering around one area in the array and then takes too long to search and wastes space:(

How to remove from a hashmap with chaining?

Just remove from linked list!

Huge arrays with little data = ???

fewer collisions but wasted space

Smaller arrays with large amounts of data = ???

More collisions but less wasted space

What does Load facotr indicate??

how full the array is

What is the formula for a load factor

number of indices filled / total number of slots

What to do if load gets less than under 25%

Make new array HALF old array size, up to nearest prime and rehash all values (less wasted space)

What to do if load is over 70%

allocate new array double old array size, take pairs rehash (less collisions)

Time complexity: Finding in an unbalanced binary search tree

O(n)

Time complexity: Inserting into a balanced binary search tree

O( log n)

Time complexity: Sorting an ordered list using mergesort

O(n log n)

Time complexity: Sorting a completely random list using quicksort

O(n log n)

Time complexity: Sorting an ordered list (with the first number as the pivot) using quicksort

O(n²)

Time complexity: Finding optimally in a hashmap

O(n)

Time complexity: Finding in a balanced binary search tree

O(log n)

true or false: a binary tree differs from a tree in that each node can have more than one successor

false

true or false: a complete tree is one in which each level is full, except the lead level, which if full from left to right

true

true or false: a binary search tree differs from a tree in that each node, the left childs data is less than the nodes data and the right childs data is greater than the nodes data

true

true of false: a balanced binary seach tree is balanced. balanced means that for each node, the height of the left child and the height of the right child differ by no more than one. 

true

what is a general tree?

a node can have any number of children

What is a full binary tree?

A full binary tree is a binary tree in which all of the nodes have either 0 or 2 offspring