Block 2: Trees and Advanced Data Structures Flashcards
what is an ADT?
Abstract Data Type
what is a data structure?
a concrete way of organising data in memory
what are 4 stack operations?
push(x), pop(), top(), isEmpty()
what is the order of a stack?
LIFO
what are 2 implementations of a stack?
linked list and dynamic array
what are 2 operations of a linked list?
push and pop
what is the theta value of a linked list?
Θ(1)
what is the average theta value of a dynamic list?
Θ(1)
what is the worst case of an operation on a dynamic list?
Θ(n)
What are the 4 queue operations?
Enqueue(x), dequeue(), Front(), isEmpty() or size()
What order does a queue work in?
FIFO
What are 2 applications of queues?
Buffering, Breadth-first Search
what operations do we expect small ADTs to have?
add(x), min(), max(), contains(x), delete(x)
what ADT did we cover in last year’s CS1860?
sets
What is a map ADT also known as?
dictionary / associative array
what is an unordered implementation of an ADT?
Hashtable
What is an ordered implementation of an ADT?
Balanced Binary Search Tree
What is the main concept of a binary tree?
the left subtree contains smaller values, and larger values are on the right
what operations do we look at for BSTs?
insert(x), lookup(x), min(), max(), successor(x), delete(x)
what time does any operation on a BST take maximum?
O(h) where h is the height of the tree
what is the best height for a tree with n elements?
O(log n)
what is the worst height for a tree with n elements?
n-1
how do you remove t from a BST if t is a leaf?
just remove it
how do you remove t from a BST if it isn’t a leaf but has no left child? What if has no right child?
replace t with t.rightchild. vice versa for no right child.
How do you delete a node t that has 2 children in a BST?
- find the largest node t2 in subtree t.leftChild
- delete t2 from subtree t.leftChild
- insert t2 in the place of t
what is the time complexity of deleting a node with 2 children from a BST?
O(h)
what is a rotation?
way to change structure of the tree, with few, local changes, without breaking the order property
what are 3 strategies for a self-balancing tree?
AVL trees, Red-Black trees, Splay trees
what is the AVL property?
for any node t, the height of the subtrees t.leftChild and t.rightChild differ by at most 1.
What is the equation for balance?
balance(t) = height(t.leftChild) - height(t.rightChild)
summarise the ADT sorting algorithm in 3 steps
- insert every item of the list into a data structure X
- start with item X.min()
- read out items in order using item = X.successor(item)
what is the definition of a set?
A set is a collection of distinct objects, considered an object in its own right
what are the set operations?
insert(x), delete(x), contains(x)
what are the 2 java implementations of sets?
TreeSet and HashSet
what 2 attributes do you need to add to each node to apply maps to a BST?
node.key and node.value
operations of a BST using a map?
containsKey(key), get(key), put(key, value), remove(key)
what are the inefficient methods in a BST using a map?
minValue and containsValue, as values are not ordered
do hash tables support ordering?
no
what is the average time complexity for hashMap operations?
O(1) / constant time
what are hash tables a perfect implementation of?
unordered sets and maps
what are the 2 values of a hash table?
size and capacity
what are slots in a hash table called?
hash buckets
what is the process for insertion into a hash table?
- compute hash(x)
- find hash bucket h%m
- if empty good, if not we need collision handling
what is the process for looking up a value in hash table?
- compute hash(x)
- find hash bucket h%m
- if it contains x or is empty, we know if x is in the hash table
what are the 2 principles for handling collisions?
chaining and open addressing
what is chaining?
placing colliding keys outside of the main table. used in java. each slot is the start of a linked list of table entries.
what is open addressing?
placing colliding keys inside the table, in a new slot.
what are the advantages of open addressing over chaining?
less memory usage, better data locality
what do cryptographic hash functions do?
convert file to a “fingerprint” bitstring
ideally, what is a hash function?
uninvertible and infeasible to find a similar pair
what are the desired properties of our hash functions?
> easy to compute
reasonably irregular
few collisions even with non-random data
consistent with equals
what does immutable mean?
unchangeable
what is the heap property?
every node in the tree contains a smaller value than both its children
what is the worst case time complexity of heapsort?
O(n log n)
what are the operations for a min-priority queue?
insert(x), minItem(), deleteMin()
what are the operations for a max-priority queue?
insert(x), maxItem(), deleteMax()
what is the running time of sifting up or down?
O(log n)
what ADT is used for priority queues?
heaps
