| Modifier and Type | Field and Description |
|---|---|
private java.util.Comparator<K> |
comparator
The Comparator used for comparing the keys
|
private LinkedAvlNode<K> |
first
node representing the start of the doubly linked list formed with the tree nodes
|
private LinkedAvlNode<K> |
last
node representing the end of the doubly linked list formed with the tree nodes
|
private LinkedAvlNode<K> |
root
the root of the tree
|
private int |
size
size of the tree
|
| Constructor and Description |
|---|
AvlTreeImpl(java.util.Comparator<K> comparator)
Creates a new instance of AVLTree.
|
| Modifier and Type | Method and Description |
|---|---|
private void |
balance(java.util.List<LinkedAvlNode<K>> treePath)
Balances the tree by visiting the nodes present in the List of nodes present in the
treePath parameter.
This really does the balancing if the height of the tree is greater than 2 and the balance factor is greater than +1 or less than -1. For an excellent info please read the Wikipedia article on AVL tree. |
private void |
detachNodes(LinkedAvlNode<K> node,
LinkedAvlNode<K> parentNode)
Detach a LinkedAvlNode from its parent
|
private LinkedAvlNode<K> |
fetchNonNullNode(K key,
LinkedAvlNode<K> startNode,
LinkedAvlNode<K> parent) |
LinkedAvlNode<K> |
find(K key)
Find a LinkedAvlNode with the given key value in the tree.
|
private LinkedAvlNode<K> |
find(K key,
LinkedAvlNode<K> startNode) |
private java.util.List<LinkedAvlNode<K>> |
find(K key,
LinkedAvlNode<K> startNode,
java.util.List<LinkedAvlNode<K>> path)
Find a LinkedAvlNode with the given key value in the tree starting from the startNode.
|
LinkedAvlNode<K> |
findGreater(K key)
Finds a LinkedAvlNode
|
LinkedAvlNode<K> |
findGreaterOrEqual(K key)
Finds a LinkedAvlNode
|
LinkedAvlNode<K> |
findLess(K key)
Finds a LinkedAvlNode
|
LinkedAvlNode<K> |
findLessOrEqual(K key)
Finds a LinkedAvlNode
|
private java.util.List<LinkedAvlNode<K>> |
findMax(LinkedAvlNode<K> startNode)
Find the LinkedAvlNode having the max key value in the tree starting from the startNode.
|
private java.util.List<LinkedAvlNode<K>> |
findMin(LinkedAvlNode<K> startNode)
Find the LinkedAvlNode having the min key value in the tree starting from the startNode.
|
private int |
getBalance(LinkedAvlNode<K> node)
Get balance-factor of the given LinkedAvlNode.
|
java.util.Comparator<K> |
getComparator() |
LinkedAvlNode<K> |
getFirst() |
java.util.List<K> |
getKeys() |
LinkedAvlNode<K> |
getLast() |
LinkedAvlNode<K> |
getRoot() |
int |
getSize()
returns the number of nodes present in this tree.
|
K |
insert(K key)
Inserts a LinkedAvlNode with the given key.
|
private void |
insertInList(LinkedAvlNode<K> node,
LinkedAvlNode<K> parentNode,
int pos) |
boolean |
isEmpty()
Tests if the tree is logically empty.
|
void |
printTree()
Prints the contents of AVL tree in pretty format
|
K |
remove(K key)
Removes the LinkedAvlNode present in the tree with the given key value
|
private void |
removeFromList(LinkedAvlNode<K> node) |
private void |
replaceNode(LinkedAvlNode<K> deleteNode,
LinkedAvlNode<K> replaceNode,
LinkedAvlNode<K> parentNode)
Replace a LinkedAvlNode to be removed with a new existing LinkedAvlNode
|
private void |
rotateSingleLeft(LinkedAvlNode<K> node,
LinkedAvlNode<K> parentNode)
Rotate the node left side once.
|
private void |
rotateSingleRight(LinkedAvlNode<K> node,
LinkedAvlNode<K> parentNode)
Rotate the node right side once.
|
(package private) void |
setFirst(LinkedAvlNode<K> first)
Set the first element of the tree
Note : this method is used by the deserialization method
|
(package private) void |
setLast(LinkedAvlNode<K> last)
Set the last element of the tree
Note : this method is used by the deserialization method
|
(package private) void |
setRoot(LinkedAvlNode<K> root)
Set the root of the tree.
|
(package private) void |
setSize(int size)
Set the size of the tree.
|
private void |
visit(LinkedAvlNode<K> node,
LinkedAvlNode<K> parentNode) |
private LinkedAvlNode<K> root
private java.util.Comparator<K> comparator
private LinkedAvlNode<K> first
private LinkedAvlNode<K> last
private int size
public AvlTreeImpl(java.util.Comparator<K> comparator)
comparator - the comparator to be used for comparing keyspublic java.util.Comparator<K> getComparator()
getComparator in interface AvlTree<K>public K insert(K key)
AvlTreeprivate void removeFromList(LinkedAvlNode<K> node)
private void insertInList(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos)
public K remove(K key)
AvlTreeprivate void balance(java.util.List<LinkedAvlNode<K>> treePath)
treePath - the traversed list of LinkedAvlNodes after performing an insert/delete operation.public boolean isEmpty()
AvlTreepublic int getSize()
AvlTreevoid setSize(int size)
size - the size of the treevoid setRoot(LinkedAvlNode<K> root)
root - the root of the treevoid setFirst(LinkedAvlNode<K> first)
first - the first element to be addedvoid setLast(LinkedAvlNode<K> last)
last - the last element to be addedpublic LinkedAvlNode<K> getRoot()
public java.util.List<K> getKeys()
public void printTree()
AvlTreepublic LinkedAvlNode<K> getFirst()
public LinkedAvlNode<K> getLast()
private void rotateSingleLeft(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
node - the LinkedAvlNode to be rotatedparentNode - parent LinkedAvlNode of nodeprivate void rotateSingleRight(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
node - the LinkedAvlNode to be rotatedparentNode - parent LinkedAvlNode of nodeprivate void detachNodes(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)
node - the LinkedAvlNode to be detachedparentNode - the parent LinkedAvlNode of the nodeprivate void replaceNode(LinkedAvlNode<K> deleteNode, LinkedAvlNode<K> replaceNode, LinkedAvlNode<K> parentNode)
deleteNode - the LinkedAvlNode to be deletedreplaceNode - the LinkedAvlNode to replace the deleteNodeparentNode - the parent LinkedAvlNode of deleteNodeprivate java.util.List<LinkedAvlNode<K>> find(K key, LinkedAvlNode<K> startNode, java.util.List<LinkedAvlNode<K>> path)
key - the key to findstartNode - starting node of a subtree/treepath - the list to be filled with traversed nodespublic LinkedAvlNode<K> findGreater(K key)
AvlTreefindGreater in interface AvlTree<K>key - the keypublic LinkedAvlNode<K> findGreaterOrEqual(K key)
AvlTreefindGreaterOrEqual in interface AvlTree<K>key - the keypublic LinkedAvlNode<K> findLess(K key)
AvlTreepublic LinkedAvlNode<K> findLessOrEqual(K key)
AvlTreefindLessOrEqual in interface AvlTree<K>key - the keyprivate LinkedAvlNode<K> fetchNonNullNode(K key, LinkedAvlNode<K> startNode, LinkedAvlNode<K> parent)
public LinkedAvlNode<K> find(K key)
AvlTreeprivate LinkedAvlNode<K> find(K key, LinkedAvlNode<K> startNode)
private java.util.List<LinkedAvlNode<K>> findMax(LinkedAvlNode<K> startNode)
startNode - starting node of a subtree/treeprivate java.util.List<LinkedAvlNode<K>> findMin(LinkedAvlNode<K> startNode)
startNode - starting node of a subtree/treeprivate int getBalance(LinkedAvlNode<K> node)
node - a LinkedAvlNodeprivate void visit(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)