public class ArrayTree<K>
extends java.lang.Object
| Modifier and Type | Field and Description |
|---|---|
private K[] |
array
The array containing the data
|
private java.util.Comparator<K> |
comparator
The Comparator used for comparing the keys
|
private static int |
INCREMENT
The extend size to use when increasing the array size
|
private int |
size
The current number of elements in the array.
|
| Constructor and Description |
|---|
ArrayTree(java.util.Comparator<K> comparator)
Creates a new instance of AVLTree.
|
ArrayTree(java.util.Comparator<K> comparator,
K[] array)
Creates a new instance of AVLTree.
|
| Modifier and Type | Method and Description |
|---|---|
boolean |
contains(K key)
Tells if a key exist in the array.
|
K |
find(K key)
Find an element in the array.
|
K |
findGreater(K key)
Finds a key higher than the given key.
|
K |
findGreaterOrEqual(K key)
Finds a key higher than the given key.
|
K |
findLess(K key)
Finds a key which is lower than the given key.
|
K |
findLessOrEqual(K key)
Finds a key chich is lower than the given key.
|
K |
get(int position)
Get the element at a given position
|
int |
getAfterPosition(K key)
Find the element position in the array, or the position of the closest greater element in the array.
|
int |
getBeforePosition(K key)
Find the element position in the array, or the position of the closest greater element in the array.
|
java.util.Comparator<K> |
getComparator() |
K |
getFirst()
Get the first element in the tree.
|
java.util.List<K> |
getKeys() |
K |
getLast()
Get the last element in the tree.
|
int |
getPosition(K key)
Find the element position in the array.
|
K |
insert(K key)
Inserts a key.
|
boolean |
isEmpty()
Tests if the tree is empty.
|
void |
printTree()
Prints the contents of AVL tree in pretty format
|
private void |
reduceArray()
q<
Reduce the array size if neede
|
K |
remove(K key)
Removes a key present in the tree
|
int |
size()
returns the number of nodes present in this tree.
|
java.lang.String |
toString() |
private java.util.Comparator<K> comparator
private K[] array
private int size
private static final int INCREMENT
public ArrayTree(java.util.Comparator<K> comparator)
comparator - the comparator to be used for comparing keyspublic java.util.Comparator<K> getComparator()
public K insert(K key)
key - the item to be inserted, should not be nullprivate void reduceArray()
public K remove(K key)
key - the value to be removedpublic boolean isEmpty()
public int size()
public java.util.List<K> getKeys()
public void printTree()
public K get(int position) throws java.lang.ArrayIndexOutOfBoundsException
position - The position in the treejava.lang.ArrayIndexOutOfBoundsException - If the position is not within the array boundariespublic K getFirst()
public K getLast()
public K findGreater(K key)
key - the key to findpublic K findGreaterOrEqual(K key)
key - the keypublic K findLess(K key)
key - the keypublic K findLessOrEqual(K key)
key - the keypublic K find(K key)
key - the key to findpublic int getPosition(K key)
key - the key to findpublic int getAfterPosition(K key)
key - the key to findpublic int getBeforePosition(K key)
key - the key to findpublic boolean contains(K key)
key - The key to look forpublic java.lang.String toString()
toString in class java.lang.Object