Map ADT: Abstraction

A map is a collection of <key, value> pairs. The keys must be unique and immutable (not modifiable).

• Other names include "dictionaries," "associative arrays," or "symbol tables." in other contexts.
  • Some references distinguish between map adn dictionaries by defining the latter as a map in which duplication keys are allowed.
• Core operations involve "insertion," "removal," and "udpate." as well as the lookup of a value associated with a particular key.

Arrays can be seen as Maps where the keys are array indices. Map is a fast "key lookup" data structure that offers a flexible means of indexing into its elements.

• In a way, a set can also be a map without values, and only pairs

Map Interface

• Two generic variables, K (the key) and V (the value).
  • Keys must be unique, not null, and immutable; values have no constraints.
• IllegalArgumentException should be used instead of specific exception classes in order to show another style of interface design.
• put updates the value associated with a key and throws an exception if K is not mapped.
• insert inserts a new key/value pair and throws an exception if K is already mapped.
• The interface extends Iterable<K> which means the iterator will iterate over the keys.

Array-based implementation

ArrayMap uses Java's ArrayList internally.

• Inefficient: operations take O(n) time.
• iterator() method makes a copy of all keys, so it takes O(n) extra time and space to initiate teh iteration.

Two ways to store keyvalue pairs:

1. Create a new structure

private static class Entry<K,V> {
	K key;
	V value;
	
	Entry (K k, V v) {
		this.key = k;
		this.value = v;
	}
}

2. Use two arrays in parallel

private K[] keys;
private V[] vaues;

3. Efficient implementations are done as a hash table or search tree.

OrderedMap ADT Interface

For a binary search tree implementation , the "keys" are used to organize the entries in a tree structure; therefore, they must be comparable. We must define as:

public interface OrderedMap<K extends Comparable<K>, V> {
	extends Map<K, V>
}

• Its iterator is expected to go over the keys in order.

BinarySearchTreeMap

Efficiency

Eac of the operations starts at the root and follows a path down to potentially the leaf at the deepest level. Therefore, time complexity of each operation is O(h), where h is the height of the tree.

• Worst case: all nodes in the BST is arranged as a sngle path, therefore the core operations take O(n) time.
• Best case: the BST is a full binary tree with a height of O(lgn). Coer operations take O(lgn) time.

Balanced BST

We restrict the height of a BST to O(lgn) to avoid the worst case.

Balancing means the tree structure is adjusted as necessary to maintain a better blance and resulting height.

• Balance property: for any node, the height of the node's let and right subtrees are either equal or differ by at most 1.
• A BST that maintains the balanceproperty is a "balanced BST" or BBST.

To establish the balance property, we define balance factor. Each node's balnace factor is the height of the left subtree minus the height of the right subtree.

bf(node) = height(node.left) - height(node.right)

height(n) = {-1 when n = null, 0 when n = leaf, and 1+max(height of children) when n=/=leaf}

A BST is balanced when, for any node, the balance actor is 1, 0, or -1.

Height is O(lgN)

In a BBST, it is guaranteed that a tree's height is O(lgN). This is observed for a perfect BST, where each internal node has two children and all the leaves are at the same level. The height of a BST is when it has the minimum number of node concerning its height. N(h) is the minimum number of nodes gven height.

• The worst case h E O(n) is when N(h = h+1)

The upper bound of N(h) for BBST bounds the height of all BBST.

Example: Consider a BBST of height h>=3.

• min number of node n = N(h)
• composed of a root and two subtrees.
• if the big tree were height h, then the subtrees must be height h-1.
  • if it had the minimum number of nodes, the other subtree would have a height of h-2.
• N(h) = 1 + N(h-1) + N(h-2)
  • N(h) > N(h-1) and N(h-1) > N(h-2)
  • Therefore, N(h) > N(h-1) + N(h-2) > 2 * N(h-2)
• We find a pattern because we can expand N(h) > 2*N(h-2) to N(h-2) > 4*N(h-4)
• Ultimately, $N>...>4 \times N(h-4) > 8 \times N(h-8)$ which is the pattern $N(h) > 2^i \times N(h-2i)$.
  • The largest i we can pu in there is $i = h/2 -1$

Therefore, the minimum number of nodes n = N(h) in a BBST of height h is at least 2^(h/2). $n > 2^{h/2}$ so h E O(lgn).