TreeMap

java.lang.Object
- net.datastructures.AbstractMap<K,V>
- - net.datastructures.AbstractSortedMap<K,V>
  - - net.datastructures.TreeMap<K,V>

All Implemented Interfaces:

Map<K,V>, SortedMap<K,V>

Direct Known Subclasses:

AVLTreeMap, RBTreeMap, SplayTreeMap
```
public class TreeMap<K,V>
extends AbstractSortedMap<K,V>
```
An implementation of a sorted map using a binary search tree.

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`protected static class`	`TreeMap.BalanceableBinaryTree<K,V>` A specialized version of the LinkedBinaryTree class with additional mutators to support binary search tree operations, and a specialized node class that includes an auxiliary instance variable for balancing data.

Nested classes/interfaces inherited from class net.datastructures.AbstractMap
AbstractMap.MapEntry<K,V>

Field Summary

Fields
Modifier and Type Field and Description

protected TreeMap.BalanceableBinaryTree<K,V> tree
Representation of the underlying tree structure.

Fields
Modifier and Type	Field and Description
`protected TreeMap.BalanceableBinaryTree<K,V>`	`tree` Representation of the underlying tree structure.

Constructor Summary

Constructors
Constructor and Description
`TreeMap()` Constructs an empty map using the natural ordering of keys.
`TreeMap(Comparator<K> comp)` Constructs an empty map using the given comparator to order keys.

Method Summary

Methods
Modifier and Type	Method and Description
`Entry<K,V>`	`ceilingEntry(K key)` Returns the entry with least key greater than or equal to given key (or null if no such key exists).
`protected void`	`dump()` Prints textual representation of tree structure (for debug purpose only).
`Iterable<Entry<K,V>>`	`entrySet()` Returns an iterable collection of all key-value entries of the map.
`Entry<K,V>`	`firstEntry()` Returns the entry having the least key (or null if map is empty).
`Entry<K,V>`	`floorEntry(K key)` Returns the entry with greatest key less than or equal to given key (or null if no such key exists).
`V`	`get(K key)` Returns the value associated with the specified key, or null if no such entry exists.
`Entry<K,V>`	`higherEntry(K key)` Returns the entry with least key strictly greater than given key (or null if no such key exists).
`protected boolean`	`isExternal(Position<Entry<K,V>> p)`
`protected boolean`	`isInternal(Position<Entry<K,V>> p)`
`protected boolean`	`isRoot(Position<Entry<K,V>> p)`
`Entry<K,V>`	`lastEntry()` Returns the entry having the greatest key (or null if map is empty).
`protected Position<Entry<K,V>>`	`left(Position<Entry<K,V>> p)`
`Entry<K,V>`	`lowerEntry(K key)` Returns the entry with greatest key strictly less than given key (or null if no such key exists).
`protected Position<Entry<K,V>>`	`parent(Position<Entry<K,V>> p)`
`V`	`put(K key, V value)` Associates the given value with the given key.
`protected void`	`rebalanceAccess(Position<Entry<K,V>> p)` Rebalances the tree after an access of specified position.
`protected void`	`rebalanceDelete(Position<Entry<K,V>> p)` Rebalances the tree after a child of specified position has been removed.
`protected void`	`rebalanceInsert(Position<Entry<K,V>> p)` Rebalances the tree after an insertion of specified position.
`V`	`remove(K key)` Removes the entry with the specified key, if present, and returns its associated value.
`protected Entry<K,V>`	`remove(Position<Entry<K,V>> p)`
`protected Position<Entry<K,V>>`	`restructure(Position<Entry<K,V>> x)`
`protected Position<Entry<K,V>>`	`right(Position<Entry<K,V>> p)`
`protected Position<Entry<K,V>>`	`root()`
`protected void`	`rotate(Position<Entry<K,V>> p)`
`protected void`	`set(Position<Entry<K,V>> p, Entry<K,V> e)`
`protected Position<Entry<K,V>>`	`sibling(Position<Entry<K,V>> p)`
`int`	`size()` Returns the number of entries in the map.
`Iterable<Entry<K,V>>`	`subMap(K fromKey, K toKey)` Returns an iterable containing all entries with keys in the range from `fromKey` inclusive to `toKey` exclusive.
`protected Position<Entry<K,V>>`	`treeMax(Position<Entry<K,V>> p)` Returns the position with the maximum key in the subtree rooted at p.
`protected Position<Entry<K,V>>`	`treeMin(Position<Entry<K,V>> p)` Returns position with the minimal key in the subtree rooted at Position p.

Methods inherited from class net.datastructures.AbstractSortedMap
checkKey, compare, compare, compare, compare

Methods inherited from class net.datastructures.AbstractMap
isEmpty, keySet, values

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface net.datastructures.Map
isEmpty, keySet, values

- Field Detail
  - tree
```
protected TreeMap.BalanceableBinaryTree<K,V> tree
```
    Representation of the underlying tree structure.
- Constructor Detail
  - TreeMap
```
public TreeMap()
```
    Constructs an empty map using the natural ordering of keys.
  - TreeMap
```
public TreeMap(Comparator<K> comp)
```
    Constructs an empty map using the given comparator to order keys.
    
    Parameters:
    comp - comparator defining the order of keys in the map
- Method Detail
  - size
```
public int size()
```
    Returns the number of entries in the map.
    
    Returns:
    number of entries in the map
  - root
```
protected Position<Entry<K,V>> root()
```
  - parent
```
protected Position<Entry<K,V>> parent(Position<Entry<K,V>> p)
```
  - left
```
protected Position<Entry<K,V>> left(Position<Entry<K,V>> p)
```
  - right
```
protected Position<Entry<K,V>> right(Position<Entry<K,V>> p)
```
  - sibling
```
protected Position<Entry<K,V>> sibling(Position<Entry<K,V>> p)
```
  - isRoot
```
protected boolean isRoot(Position<Entry<K,V>> p)
```
  - isExternal
```
protected boolean isExternal(Position<Entry<K,V>> p)
```
  - isInternal
```
protected boolean isInternal(Position<Entry<K,V>> p)
```
  - set
```
protected void set(Position<Entry<K,V>> p,
       Entry<K,V> e)
```
  - remove
```
protected Entry<K,V> remove(Position<Entry<K,V>> p)
```
  - rotate
```
protected void rotate(Position<Entry<K,V>> p)
```
  - restructure
```
protected Position<Entry<K,V>> restructure(Position<Entry<K,V>> x)
```
  - treeMin
```
protected Position<Entry<K,V>> treeMin(Position<Entry<K,V>> p)
```
    Returns position with the minimal key in the subtree rooted at Position p.
    
    Parameters:
    p - a Position of the tree serving as root of a subtree
    
    Returns:
    Position with minimal key in subtree
  - treeMax
```
protected Position<Entry<K,V>> treeMax(Position<Entry<K,V>> p)
```
    Returns the position with the maximum key in the subtree rooted at p.
    
    Parameters:
    p - a Position of the tree serving as root of a subtree
    
    Returns:
    Position with maximum key in subtree
  - get
```
public V get(K key)
      throws IllegalArgumentException
```
    Returns the value associated with the specified key, or null if no such entry exists.
    
    Parameters:
    key - the key whose associated value is to be returned
    
    Returns:
    the associated value, or null if no such entry exists
    
    Throws:
    
    IllegalArgumentException
  - put
```
public V put(K key,
    V value)
      throws IllegalArgumentException
```
    Associates the given value with the given key. If an entry with the key was already in the map, this replaced the previous value with the new one and returns the old value. Otherwise, a new entry is added and null is returned.
    
    Parameters:
    key - key with which the specified value is to be associated
    value - value to be associated with the specified key
    
    Returns:
    the previous value associated with the key (or null, if no such entry)
    
    Throws:
    
    IllegalArgumentException
  - remove
```
public V remove(K key)
         throws IllegalArgumentException
```
    Removes the entry with the specified key, if present, and returns its associated value. Otherwise does nothing and returns null.
    
    Parameters:
    key - the key whose entry is to be removed from the map
    
    Returns:
    the previous value associated with the removed key, or null if no such entry exists
    
    Throws:
    
    IllegalArgumentException
  - firstEntry
```
public Entry<K,V> firstEntry()
```
    Returns the entry having the least key (or null if map is empty).
    
    Returns:
    entry with least key (or null if map is empty)
  - lastEntry
```
public Entry<K,V> lastEntry()
```
    Returns the entry having the greatest key (or null if map is empty).
    
    Returns:
    entry with greatest key (or null if map is empty)
  - ceilingEntry
```
public Entry<K,V> ceilingEntry(K key)
                        throws IllegalArgumentException
```
    Returns the entry with least key greater than or equal to given key (or null if no such key exists).
    
    Returns:
    entry with least key greater than or equal to given (or null if no such entry)
    
    Throws:
    
    IllegalArgumentException - if the key is not compatible with the map
  - floorEntry
```
public Entry<K,V> floorEntry(K key)
                      throws IllegalArgumentException
```
    Returns the entry with greatest key less than or equal to given key (or null if no such key exists).
    
    Returns:
    entry with greatest key less than or equal to given (or null if no such entry)
    
    Throws:
    
    IllegalArgumentException - if the key is not compatible with the map
  - lowerEntry
```
public Entry<K,V> lowerEntry(K key)
                      throws IllegalArgumentException
```
    Returns the entry with greatest key strictly less than given key (or null if no such key exists).
    
    Returns:
    entry with greatest key strictly less than given (or null if no such entry)
    
    Throws:
    
    IllegalArgumentException - if the key is not compatible with the map
  - higherEntry
```
public Entry<K,V> higherEntry(K key)
                       throws IllegalArgumentException
```
    Returns the entry with least key strictly greater than given key (or null if no such key exists).
    
    Returns:
    entry with least key strictly greater than given (or null if no such entry)
    
    Throws:
    
    IllegalArgumentException - if the key is not compatible with the map
  - entrySet
```
public Iterable<Entry<K,V>> entrySet()
```
    Returns an iterable collection of all key-value entries of the map.
    
    Returns:
    iterable collection of the map's entries
  - subMap
```
public Iterable<Entry<K,V>> subMap(K fromKey,
                          K toKey)
                            throws IllegalArgumentException
```
    Returns an iterable containing all entries with keys in the range from fromKey inclusive to toKey exclusive.
    
    Returns:
    iterable with keys in desired range
    
    Throws:
    
    IllegalArgumentException - if fromKey or toKey is not compatible with the map
  - rebalanceInsert
```
protected void rebalanceInsert(Position<Entry<K,V>> p)
```
    Rebalances the tree after an insertion of specified position. This version of the method does not do anything, but it can be overridden by subclasses.
    
    Parameters:
    p - the position which was recently inserted
  - rebalanceDelete
```
protected void rebalanceDelete(Position<Entry<K,V>> p)
```
    Rebalances the tree after a child of specified position has been removed. This version of the method does not do anything, but it can be overridden by subclasses.
    
    Parameters:
    p - the position of the sibling of the removed leaf
  - rebalanceAccess
```
protected void rebalanceAccess(Position<Entry<K,V>> p)
```
    Rebalances the tree after an access of specified position. This version of the method does not do anything, but it can be overridden by a subclasses.
    
    Parameters:
    p - the Position which was recently accessed (possibly a leaf)
  - dump
```
protected void dump()
```
    Prints textual representation of tree structure (for debug purpose only).

Class TreeMap<K,V>

Nested Class Summary

Nested classes/interfaces inherited from class net.datastructures.AbstractMap

Field Summary

Constructor Summary

Method Summary

Methods inherited from class net.datastructures.AbstractSortedMap

Methods inherited from class net.datastructures.AbstractMap

Methods inherited from class java.lang.Object

Methods inherited from interface net.datastructures.Map

Field Detail

tree

Constructor Detail

TreeMap

TreeMap

Method Detail

size

root

parent

left

right

sibling

isRoot

isExternal

isInternal

set

remove

rotate

restructure

treeMin

treeMax

get

put

remove

firstEntry

lastEntry

ceilingEntry

floorEntry

lowerEntry

higherEntry

entrySet

subMap

rebalanceInsert

rebalanceDelete

rebalanceAccess

dump