# 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