binary search trees

Question 1

What is a data structure?

Answer 1

• Collection of data items manipulated by an algorithm or program
  
  • Data item is an instance of a data type
  • In java, data types include:
    ○ Primitive (int/char)
    ○ Built-in (string)
    ○ Compound (class)

Question 2

What is an operation?

Answer 2

• Data structures are interfaced though operations
  ○ Basic set: add, search, delete, iterate
  ○ Ordered set: min, max, rank
  ○ Stack: pop/push
  ○ Queue: first/last

Question 3

what are some operations that you can do to data?

Answer 3

add, search, remove, min/max

Question 4

What is the add, search, remove, min/max of an array?

Answer 4

Big O
N N N N

Question 5

What is the add, search, remove, min/max of a sorted array?

Answer 5

N
log N
N
1 (constant)

Question 6

What is the add, search, remove, min/max of a linked list?

Answer 6

1
N
N
N

Question 7

What is the add, search, remove, min/max of a sorted linked list?

Answer 7

N
N
N
1

Question 8

What is a BST?

Answer 8

Binary Search Tree
Like sorted arrays, but also fast (logarithmic add delete)
Rooted binary tree satisfies search tree properties

Question 9

What are the search tree properties?

Answer 9

• has single distinguished root node
• has an orientation downwards/outwards
• nodes ponted by a node X in outward direction from root are the children of X
• node pointed by X towards root are the parents
• each node has AT MOST 2 children (binary)

Question 10

What is the height of a BST?

Answer 10

(aka depth)
a rooted tree is the length of the longest path from root to leaf
( count down the edges between nodes for each “level” of a bst)

Question 11

What is the height of an empty BST?

Answer 11

0

Question 12

What is a complete RBT?

Answer 12

all levels of the tree except the last one (they are uniform)

Question 13

What is the minimal height of a RBT?

Answer 13

the height of a complete (non-empty) BST

Question 14

How are items sorted in a BST?

Answer 14

• for each node X in tree:
  all data in left subtree are SMALLER values than data item X
  all data in right subtree are GREATER values than data item X

Question 15

How to search for items in a BST?

Answer 15

1. Traverse key recursively starting at root
2. Base case:
   
   • If current node is NULL, return false
   • If k = key at current node, return true
3. Recursive case:
   
   • If k < key at current node, traverse left
     
     • If k > key at current node, traverse right

Question 16

How to add to bst?

Answer 16

• compare each traversal to the item to be added
• if less then, go left
• if more than, go right
• add to bst in lowest position

Question 17

What is the efficiency of the balanced bst?

Answer 17

add = O(log N)
search = O(log N)
min/max = O(log N)
remove = O(log N)

Question 18

How to delete from a bst?

Answer 18

1. locate node you want to delete using search algorithm
2. if node has no children (leaf) then: delete the node directly from tree
   if node has 1 child:
   - splice out node to remove
   - replace with child node
   if node has 2 children:
   - replace n with its predecessor to preserve search tree property
   -original is deleted from tree and new node points to other remaining child.