# binary search trees Flashcards

1
Q

A

nodes can be compared by some value
nodes on the left are less that node
nodes on the right are greater than node - can also define one side as equals

2
Q

A

faster search

3
Q

BST insert algorithm

A

if root = null –> new node becomes entire tree
value node add new node to RHS
recured until the node gets added as a new leaf node - nodes are only added as new leaf nodes

4
Q

BST find algorithm

A

start at root

• if search == root return root
• if searchroot recurse into RHS subtree
5
Q

delete algorithm

A
```find element to delete
- if element is a leaf  - just delete
- 1 child - replace node with its child
- 2 children
\+++ find x = min node in RHS subtree
\+++ remove x from RHS subtree
\+++ replace deleted element with x```
6
Q

how to handle duplicate keys

A

assume all keys are unique
- issue:
++is it identical items copies or different items with identical identifier keys

options =
++ duplicates in adjacent tree positions - modify all operations to deal with this
++ counter for dupes
++list of items attached to each node

7
Q

complexity analysis for operations (find insert delete)

A

best case - O(1)

worst case -O(n)

8
Q

why is the worst case not O(log n )

A

the tree could be linear in shape

9
Q

things to go over and add

A
• little o notations
• findK
• level order traversals explanations
10
Q

height

A

maximum edges from root to leaf

11
Q

size

A

number of nodes

12
Q

level

A

number of rows h+1

13
Q

full tree

A

no single child nodes

14
Q

complete tree-

A

has minimum height

all levels have every node except last and last is filled from left to right

15
Q

balanced tree

A

nodes are distributed according to some balancing factor

16
Q

what is the height of a tree with s nodes

A

MAX - H = size -

MIN h = LOG(s+1)-1

17
Q

how many nodes are in a tree with height h

A

min - h+1 (nodes are linear)

max - 2^(h+1)-1 (assume full and complete)