CMSC420 Exam 4

How does demote and merge work?

Pick one of the minimum full siblings, demote the parent of those 2 and form a new node

What is time complexity of all operations in B-tree?

O(log k)

When does a node become a scapegoat?

When size(x.child)/size(x) > alpha

Is a scape goat tree one with no scapegoats?

False, scapegoat trees have scapegoats

Which median do you pick when rebuilding a tree?

The upper median

What is the rebuilding time?

O(k)

When during insertion is there a depth violation and we have to check upwards for a scapegoat?

If d > log(1/alpha)(n) where n = number of nodes in the tree

What is the height of a scapegoat tree in terms of big O

O(log(n))

How expensive is an insertsion and deletion in scapegoat tree without accounting for rebuilding?

O(log(k))

How does deletion amortized cost work?

Insert 3 everytime you delete, O(1) amortized per operation cost

How does insertion amortized cost work?

Insert 3 tokens into the path onto the inserted node, including the inserted node, or deleted node/replacement

What does splay(x) do?

Bring x, or the parent of what would’ve been x to the top

What is a zig?

Rotating to root

What is a zig-zig?

Two left/right rotations at parent of x?

What is a zig-zag?

Rotating x one up at it’s parent, then rotating x up to the grand parent