net.datastructures
Class BinarySearchTreeMap<K,V>

java.lang.Object
  net.datastructures.LinkedBinaryTree<Entry<K,V>>
      net.datastructures.BinarySearchTreeMap<K,V>

All Implemented Interfaces:

BinaryTree<Entry<K,V>>, Map<K,V>, Tree<Entry<K,V>>

Direct Known Subclasses:

AVLTreeMap, RBTreeMap

public class BinarySearchTreeMap<K,V>
extends LinkedBinaryTree<Entry<K,V>>
implements Map<K,V>

Realization of a map by means of a binary search tree.

Author:

Michael Goodrich, Eric Zamore

Nested Class Summary

protected static class

BinarySearchTreeMap.BSTEntry<K,V> Nested class for location-aware binary search tree entries

Field Summary

protected Position<Entry<K,V>>	actionPos
protected Comparator<K>	C
protected int	numEntries

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

BinarySearchTreeMap()
Creates a BinarySearchTreeMap with a default comparator.

BinarySearchTreeMap(Comparator<K> c)
Creates a BinarySearchTreeMap with the given comparator.

Method Summary

protected void	checkEntry(Entry<K,V> ent) Checks whether a given entry is valid.
protected void	checkKey(K key) Checks whether a given key is valid.
protected Entry<K,V>	entry(Position<Entry<K,V>> position) Extracts the entry at a given node of the tree.
Iterable<Entry<K,V>>	entrySet() Returns an iterable object containing all entries in the tree.
V	get(K key) Returns the value of the entry containing the given key.
protected Entry<K,V>	insertAtExternal(Position<Entry<K,V>> v, Entry<K,V> e) Auxiliary method for inserting an entry at an external node
boolean	isEmpty() Returns whether the tree is empty.
protected K	key(Position<Entry<K,V>> position) Extracts the key of the entry at a given node of the tree.
Iterable<K>	keySet() Returns an iterable object containing all keys in the tree.
V	put(K k, V x) If there is an entry with the specified key, replaces the value of this entry with the specified value and returns the old value.
V	remove(K k) If there is an entry with the specified key, removes this entry and returns its value.
protected void	removeExternal(Position<Entry<K,V>> v) Auxiliary method for removing an external node and its parent
protected V	replaceEntry(Position<Entry<K,V>> pos, Entry<K,V> ent) Replaces an entry with a new entry (and reset the entry's location)
protected Position<Entry<K,V>>	restructure(Position<Entry<K,V>> x) Performs a tri-node restructuring.
int	size() Returns the number of entries in the tree.
protected Position<Entry<K,V>>	treeSearch(K key, Position<Entry<K,V>> pos) Auxiliary method used by get, put, and remove.
protected V	value(Position<Entry<K,V>> position) Extracts the value of the entry at a given node of the tree.
Iterable<V>	values() Returns an iterable object containing all values in the tree.

Methods inherited from class net.datastructures.LinkedBinaryTree

addRoot, attach, checkPosition, children, createNode, expandExternal, hasLeft, hasRight, inorderPositions, insertLeft, insertRight, isExternal, isInternal, isRoot, iterator, left, parent, positions, preorderPositions, remove, removeAboveExternal, replace, right, root, sibling, swapElements

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

C

protected Comparator<K> C

actionPos

protected Position<Entry<K,V>> actionPos

numEntries

protected int numEntries

Constructor Detail

BinarySearchTreeMap

public BinarySearchTreeMap()

Creates a BinarySearchTreeMap with a default comparator.

BinarySearchTreeMap

public BinarySearchTreeMap(Comparator<K> c)

Creates a BinarySearchTreeMap with the given comparator.

Method Detail

key

protected K key(Position<Entry<K,V>> position)

Extracts the key of the entry at a given node of the tree.

value

protected V value(Position<Entry<K,V>> position)

Extracts the value of the entry at a given node of the tree.

entry

protected Entry<K,V> entry(Position<Entry<K,V>> position)

Extracts the entry at a given node of the tree.

replaceEntry

protected V replaceEntry(Position<Entry<K,V>> pos,
                         Entry<K,V> ent)

Replaces an entry with a new entry (and reset the entry's location)

checkKey

protected void checkKey(K key)
                 throws InvalidKeyException

Checks whether a given key is valid.

Throws:

InvalidKeyException

checkEntry

protected void checkEntry(Entry<K,V> ent)
                   throws InvalidEntryException

Checks whether a given entry is valid.

Throws:

InvalidEntryException

insertAtExternal

protected Entry<K,V> insertAtExternal(Position<Entry<K,V>> v,
                                      Entry<K,V> e)

Auxiliary method for inserting an entry at an external node

removeExternal

protected void removeExternal(Position<Entry<K,V>> v)

Auxiliary method for removing an external node and its parent

treeSearch

protected Position<Entry<K,V>> treeSearch(K key,
                                          Position<Entry<K,V>> pos)

Auxiliary method used by get, put, and remove.

size

public int size()

Returns the number of entries in the tree.

Specified by:

size in interface Map<K,V>

Specified by:

size in interface Tree<Entry<K,V>>

Overrides:

size in class LinkedBinaryTree<Entry<K,V>>

isEmpty

public boolean isEmpty()

Returns whether the tree is empty.

Specified by:

isEmpty in interface Map<K,V>

Specified by:

isEmpty in interface Tree<Entry<K,V>>

Overrides:

isEmpty in class LinkedBinaryTree<Entry<K,V>>

get

public V get(K key)
      throws InvalidKeyException

Returns the value of the entry containing the given key. Returns null if no such entry exists.

Specified by:

get in interface Map<K,V>

Throws:

InvalidKeyException

put

public V put(K k,
             V x)
      throws InvalidKeyException

If there is an entry with the specified key, replaces the value of this entry with the specified value and returns the old value. Else, adds a new entry with the specified key and value and returns null.

Specified by:

put in interface Map<K,V>

Throws:

InvalidKeyException

remove

public V remove(K k)
         throws InvalidKeyException

If there is an entry with the specified key, removes this entry and returns its value. Else, returns null.

Specified by:

remove in interface Map<K,V>

Throws:

InvalidKeyException

keySet

public Iterable<K> keySet()

Returns an iterable object containing all keys in the tree.

Specified by:

keySet in interface Map<K,V>

values

public Iterable<V> values()

Returns an iterable object containing all values in the tree.

Specified by:

values in interface Map<K,V>

entrySet

public Iterable<Entry<K,V>> entrySet()

Returns an iterable object containing all entries in the tree.

Specified by:

entrySet in interface Map<K,V>

restructure

protected Position<Entry<K,V>> restructure(Position<Entry<K,V>> x)

Performs a tri-node restructuring. Assumes the nodes are in one of following configurations:

          z=c       z=c        z=a         z=a
         /  \      /  \       /  \        /  \
       y=b  t4   y=a  t4    t1  y=c     t1  y=b
      /  \      /  \           /  \         /  \
    x=a  t3    t1 x=b        x=b  t4       t2 x=c
   /  \          /  \       /  \             /  \
  t1  t2        t2  t3     t2  t3           t3  t4
 

Returns:

the new root of the restructured subtree