cs126 binary search trees

What is an ordered map?

A map where keys satisfy the properties of a total order.

What is a binary search tree?

• A proper binary tree that stores keys / key-value pairs as its internal nodes

• Each node in a left subtree of a node is smaller than it

• Each node in a right subtree of a node is larger than it

• External nodes do not store items

Name the (3) fundamental methods of a binary search tree.

• get(k)

• put(k,v)

• remove(k)

What does the binary search tree operation get(k) do?

Returns the value v associated with key k, or return null.

What does the binary search tree operation put(k,v) do?

Replaces the value associated with k, or inserts a new entry if there is none.

What does the binary search tree operation remove(k) do?

Remove and returns entry with key k, or return null.

What is the worst-case time cost associated with searching for an item in a BST?

O(logn)

What is the worst-case time cost associated with removing / inserting an item in a BST?

O(n) for both

How is a search performed on a BST?

• Inspect a node

• If the node is the item then its found

• If the node is a leaf, the item is not in the tree

• If the key at the node  is greater than the item, inspect the right subtree

• Otherwise inspect the left subtree

How is an insertion performed on a BST?

• Perform a search for the key

• When a leaf is reached, insert the key at the node, and expand the node into an internal node

How is a deletion performed on a BST if the node has no children?

Delete the node.

How is a deletion performed on a BST if the node has one child?

Make the child of the node, the child of the parent, then delete the node.

How is a deletion performed on a BST if the node has two children?

Replace the value by the max (rightmost) value of the left subtree and delete() the max node of the left subtree.

Describe the performance of BST.

• If a tree has n items and a height of h

  • Space used is O(n)

  • get(), put(), remove() all take O(h) time

• In the worst case, h is O(n)

• In the best case, h is O(logn)