CSI 2110 Lecture 8: Maps, Binary Search Trees
Document Summary
Stores and retrieves values based on a uniquely identifying search key. Insert takes o(1) but first we need to search for a key duplicate which takes o(n) Each internal node stores an element of a map. Keys stored at nodes in the left subtree are less. Keys stores at nodes in the right subtree are greater. In-order traversal always traverses keys in increasing order. Next node depends on the outcome of the comparison of k with the key of the current node. If we reach a leaf, key is not found, return dummy node. Worst case of best possible tree: o(log n) Assume key is in tree and let v be the node storing k. If node v has a leaf child w, remove v and w from the tree with the operation. If node v has a leaf child w, remove v and w from the tree with the operation removeaboveexternal(w)