public class RedBlackTree<T> extends Object implements Iterable<T>
The difference between this implementation and TreeMap
is that we
assume that keys are ints. This should provide for a constant factor speed-up. We also assume
that we may copy this implementation to specialize for particular data element types.
This class implements most methods required for a Map
. However, since we
use ints as keys, we can't implement the interface, as ints are not Objects, and so for example
RedBlackTree.containsKey(int key)
does not specialize Map.containsKey(Object key)
.
Note that this implementation is not thread-safe. A thread-safe version could easily be provided, but would come with additional overhead.
Constructor and Description |
---|
RedBlackTree()
Default constructor, does nothing.
|
Modifier and Type | Method and Description |
---|---|
void |
clear()
Remove all elements from the tree.
|
boolean |
containsKey(int key)
Checks if the key is contained in the tree.
|
boolean |
containsValue(T o)
Check if the value object is contained in the tree.
|
T |
get(int key)
Get the object for a key.
|
BinaryTree |
getBinaryTree() |
T |
getFirst() |
boolean |
isEmpty()
Check if the map is empty.
|
Iterator<T> |
iterator() |
int[] |
keySet()
Return the set of keys as a sorted array.
|
static void |
main(String[] args) |
void |
printKeys()
Debugging aid.
|
boolean |
put(int key,
T el)
Insert an object with a given key into the tree.
|
T |
remove(int key)
Delete the node with the given key from the tree, if it exists.
|
int |
size() |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
forEach, spliterator
public final int size()
public final void clear()
public final boolean containsKey(int key)
key
- The key.true
, if key is defined; false
, else.public final boolean containsValue(T o)
o
- The value we want to check.true
, if value is there; false
, else.public final boolean put(int key, T el)
key
- The key under which the Object is to be inserted.el
- The Object to be inserted.true
, if the key was not in the tree; false
, if an
element with that key was already in the tree. The old element is overwritten with the
new one.public final T remove(int key)
key
- The key to be deleted.public final T get(int key)
null
.
Since null
can also be a regular value, use containsKey()
to check if a
key is defined or not.key
- The key.null
if key is not defined.public final boolean isEmpty()
true
if map is empty; false
, else.public final int[] keySet()
public final T getFirst()
null
if the tree is
empty.public BinaryTree getBinaryTree()
public void printKeys()
public static void main(String[] args)
Copyright © 2006–2023 The Apache Software Foundation. All rights reserved.