Binary Search Trees Flashcards
1
Q
What is a Heap?
A
A binary tree where each node U has a priority
2
Q
In a Heap which node is the root?
A
The node with the minimum priority
3
Q
What is a treap?
A
A binary tree where each node has a value and a priority
4
Q
How are priority values assigned in a treap?
A
They are unique and assigned at random
5
Q
Similar to a heap which node is the root?
A
The node with the smallest priority
6
Q
What is the runtime of find, add and remove?
A
O(logn)
7
Q
What is the expected length of a search path for a treap?
A
At most, 1.38log2n+2
