BST 6 Efficiency of BST Operations Flashcards
1
Q
If the BST contains n nodes, how many nodes will we visit AT WORST?
A
2
Q
In a BSt, how many of the items do we eliminate at each step?
A
3
Q
What does a worst case tree look like and what data structure does it resemble
A
4
Q
Define what the level of a node is
A
5
Q
What does a good tree look like and what properties does it have?
A
6
Q
What is a full/complete tree? What properties does it have? What is the formula?
A
7
Q
What is the shortest a tree could be, if it has n nodes? What is the height?
A
8
Q
What is the height of a worst case tree (linked-list)
A
9
Q
What is the operation efficiency of a best case and worst case tree? How long would each take with 1,000,000 keys?
A
- Full/Complete tree = O(log n)
- With 1,000,000 keys would take around 20 steps
- Wrost/Snake tree = O(n)
- With 1,000,000 keys would take 1,000,000
