CMSC420 Exam 5

How does splay first insertion work?

Splay(x), get either IOP or IOS as root, insert x before/after root by moving it down based on IOP or IOS

How does splay first deletion work?

Splay(x) to bring it to the root, if it has two subtrees splay in either of them to get IOS/IOP as root of that tree, promite it to replace x

How does splay second delete work?

Delete regularly and splay the parent

What is time complexity of operations?

Amortized per operation it’s logn, worst case n

What does m mean in an EKD tree?

Max number of points in a leaf node

What direction do you go when inserting if the coordinate matches the splitting node?

Go right

How generally does splitting work?

Choose a coordinate to split by, cycle sort by that coordinate, floor((m + 1)/ 2) go left, the rest go right (the right gets one more if it’s uneven)

How does cycle split work?

If at the root split by the first coordinate, if it a non-root split by the coordinate after the coordinate which the parent split by

How does spread split work?

Calculate spread of each coordinate, split by the max spread. if there’s a tie go with the left most coordinate

What is the splitting value?

The median of the splitting coordinate

How does deleting from a EKD tree work?

Search for point, delete it, if the node becomes empty, remove it’s parent splitting node and promote the other child

When you delete, how do you update the bounding box?

Recalculate the bounding box at the leaf, then recursively go to the root taking the rectangle union between the two children

How does the range query work?

If we’re at a leaf, check which points are in the range, other wise check if left node BB overlaps with rectangle, if they do go there, then check right

How can you tell if two rectangles overlap?

If A.max >= B.min and B.max >= A.min for both y and x coordinate

how does k-nearest-neighbors work?

If we’re at a leaf, fill it with the K closest points, otherwise look at the cloest child bounding box, if list is not full go that way, otheriwse if the list is full, only go to the bounding box if it’s less than or equal to the current distance of the furthest point in the list

How to calculate distance to a bounding box?

What does the $ represent in EKD trees?

Terminating character, sits right above a value which is a leaf

Which nodes can only have one child in an EKD tree?

Root and parents of leaves

How to convert set of strings into a trie

Group by first letter, in each group take the longest prefix, cut off those prefixes, make them branches, and recurse

Are tries unique?

Yes