Package generic.stl
Class RedBlackTree<K,V>
- java.lang.Object
-
- generic.stl.RedBlackTree<K,V>
-
public class RedBlackTree<K,V> extends java.lang.Object
A RedBlack Tree implementation with K type keys and place to store V type values.
-
-
Field Summary
Fields Modifier and Type Field Description static java.lang.String
EOL
-
Constructor Summary
Constructors Constructor Description RedBlackTree(RedBlackTree<K,V> tree)
Creates a copy of an existing RedBlackTreeRedBlackTree(java.util.Comparator<K> comparator, boolean allowDuplicateKeys)
Creates a new RedBlackTree
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
containsKey(K key)
Returns true if the key is in the set.void
deleteEntry(RedBlackNode<K,V> p)
Delete node p, and then rebalance the tree.RedBlackNode<K,V>
findFirstNode(K key)
RedBlackNode<K,V>
findLastNode(K key)
RedBlackNode<K,V>
getFirst()
Returns the first entry in this set.RedBlackNode<K,V>
getLast()
Returns the last entry in this set.boolean
isEmpty()
Test if the set is empty.RedBlackNode<K,V>
lowerBound(K key)
Finds the node with the lowest key that is >= to the given key.Pair<RedBlackNode<K,V>,java.lang.Boolean>
put(K key, V value)
Adds the given key,value to the map.V
remove(K key)
Removes the given key (first if duplicates are allowed) from the set.void
removeAll()
Removes all entrys from the set.int
size()
Returns the number keys in this set.java.lang.String
toString()
RedBlackNode<K,V>
upperBound(K key)
Finds the node with the lowest key that is > the given key.
-
-
-
Constructor Detail
-
RedBlackTree
public RedBlackTree(java.util.Comparator<K> comparator, boolean allowDuplicateKeys)
Creates a new RedBlackTree- Parameters:
comparator
- the comparator for this treeallowDuplicateKeys
- true to allow duplicate keys
-
RedBlackTree
public RedBlackTree(RedBlackTree<K,V> tree)
Creates a copy of an existing RedBlackTree- Parameters:
tree
- the existing tree to copy
-
-
Method Detail
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
size
public int size()
Returns the number keys in this set.
-
containsKey
public boolean containsKey(K key)
Returns true if the key is in the set.- Parameters:
key
- the key whose presence is to be tested.
-
getFirst
public RedBlackNode<K,V> getFirst()
Returns the first entry in this set.
-
getLast
public RedBlackNode<K,V> getLast()
Returns the last entry in this set.
-
lowerBound
public RedBlackNode<K,V> lowerBound(K key)
Finds the node with the lowest key that is >= to the given key. Returns null if all nodes in the tree have keys less than the given key.- Parameters:
key
- the key to search for.- Returns:
- the node with the lowest key that is >= to the given key or null if no such key exists.
-
upperBound
public RedBlackNode<K,V> upperBound(K key)
Finds the node with the lowest key that is > the given key. Returns null if all nodes in the tree have keys less than or equal to the given key.- Parameters:
key
- the key to search for.- Returns:
- the node with the lowest key that is > to the given key or null if no such key exists.
-
put
public Pair<RedBlackNode<K,V>,java.lang.Boolean> put(K key, V value)
Adds the given key,value to the map. If the map does not allow duplicate keys and a key already exists, the old value will be replaced by the new value and the old value will be returned.- Parameters:
key
- the key to add to the set.value
- the key's value.- Returns:
- the old value associated with the key, or null if the key was not previously in the map.
-
findFirstNode
public RedBlackNode<K,V> findFirstNode(K key)
-
findLastNode
public RedBlackNode<K,V> findLastNode(K key)
-
remove
public V remove(K key)
Removes the given key (first if duplicates are allowed) from the set.- Parameters:
key
- the key to remove from the set.- Returns:
- the value associated with the key removed or null if the key not found.
-
removeAll
public void removeAll()
Removes all entrys from the set.
-
isEmpty
public boolean isEmpty()
Test if the set is empty.- Returns:
- true if the set is empty.
-
deleteEntry
public void deleteEntry(RedBlackNode<K,V> p)
Delete node p, and then rebalance the tree.
-
-