org.apache.hadoop.hbase.util

Class AvlUtil.AvlTree

java.lang.Object

org.apache.hadoop.hbase.util.AvlUtil.AvlTree

Enclosing class:

AvlUtil

@InterfaceAudience.Private
public static class AvlUtil.AvlTree
extends Object

Helper class that allows to create and manipulate an AVL Tree

Constructor Summary

Constructors

Constructor and Description
AvlTree()

Method Summary

Modifier and Type	Method and Description
private static <TNode extends AvlUtil.AvlNode> TNode	balance(TNode p)
private static <TNode extends AvlUtil.AvlNode> int	balanceFactor(TNode node)
private static <TNode extends AvlUtil.AvlNode> void	fixHeight(TNode node)
static <TNode extends AvlUtil.AvlNode> TNode	get(TNode root, Object key, AvlUtil.AvlKeyComparator<TNode> keyComparator) Return the node that matches the specified key or null in case of node not found.
static <TNode extends AvlUtil.AvlNode> TNode	getFirst(TNode root) Return the first node of the tree.
static <TNode extends AvlUtil.AvlNode> TNode	getLast(TNode root) Return the last node of the tree.
private static <TNode extends AvlUtil.AvlNode> int	height(TNode node)
static <TNode extends AvlUtil.AvlNode> TNode	insert(TNode root, Object key, AvlUtil.AvlKeyComparator<TNode> keyComparator, AvlUtil.AvlInsertOrReplace<TNode> insertOrReplace) Insert a node into the tree.
static <TNode extends AvlUtil.AvlNode> TNode	insert(TNode root, TNode node) Insert a node into the tree.
static <TNode extends AvlUtil.AvlNode> TNode	remove(TNode root, Object key, AvlUtil.AvlKeyComparator<TNode> keyComparator) Removes the node matching the specified key from the tree
static <TNode extends AvlUtil.AvlNode> TNode	remove(TNode root, Object key, AvlUtil.AvlKeyComparator<TNode> keyComparator, AtomicBoolean removed) Removes the node matching the specified key from the tree
private static <TNode extends AvlUtil.AvlNode> TNode	removeMin(TNode p)
private static <TNode extends AvlUtil.AvlNode> TNode	rotateLeft(TNode q)
private static <TNode extends AvlUtil.AvlNode> TNode	rotateRight(TNode p)
static <TNode extends AvlUtil.AvlNode> void	visit(TNode root, AvlUtil.AvlNodeVisitor<TNode> visitor) Visit each node of the tree

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AvlTree

public AvlTree()

Method Detail

get

public static <TNode extends AvlUtil.AvlNode> TNode get(TNode root,
                                                        Object key,
                                                        AvlUtil.AvlKeyComparator<TNode> keyComparator)

Return the node that matches the specified key or null in case of node not found.

Parameters:

root - the current root of the tree

key - the key for the node we are trying to find

keyComparator - the comparator to use to match node and key

Returns:

the node that matches the specified key or null in case of node not found.

getFirst

public static <TNode extends AvlUtil.AvlNode> TNode getFirst(TNode root)

Return the first node of the tree.

Parameters:

root - the current root of the tree

Returns:

the first (min) node of the tree

getLast

public static <TNode extends AvlUtil.AvlNode> TNode getLast(TNode root)

Return the last node of the tree.

Parameters:

root - the current root of the tree

Returns:

the last (max) node of the tree

insert

public static <TNode extends AvlUtil.AvlNode> TNode insert(TNode root,
                                                           TNode node)

Insert a node into the tree. It uses the AvlNode.compareTo() for ordering. NOTE: The node must not be already in the tree.

Parameters:

root - the current root of the tree

node - the node to insert

Returns:

the new root of the tree

insert

public static <TNode extends AvlUtil.AvlNode> TNode insert(TNode root,
                                                           Object key,
                                                           AvlUtil.AvlKeyComparator<TNode> keyComparator,
                                                           AvlUtil.AvlInsertOrReplace<TNode> insertOrReplace)

Insert a node into the tree. This is useful when you want to create a new node or replace the content depending if the node already exists or not. Using AvlInsertOrReplace class you can return the node to add/replace.

Parameters:

root - the current root of the tree

key - the key for the node we are trying to insert

keyComparator - the comparator to use to match node and key

insertOrReplace - the class to use to insert or replace the node

Returns:

the new root of the tree

removeMin

private static <TNode extends AvlUtil.AvlNode> TNode removeMin(TNode p)

remove

public static <TNode extends AvlUtil.AvlNode> TNode remove(TNode root,
                                                           Object key,
                                                           AvlUtil.AvlKeyComparator<TNode> keyComparator)

Removes the node matching the specified key from the tree

Parameters:

root - the current root of the tree

key - the key for the node we are trying to find

keyComparator - the comparator to use to match node and key

Returns:

the new root of the tree

remove

public static <TNode extends AvlUtil.AvlNode> TNode remove(TNode root,
                                                           Object key,
                                                           AvlUtil.AvlKeyComparator<TNode> keyComparator,
                                                           AtomicBoolean removed)

Removes the node matching the specified key from the tree

Parameters:

root - the current root of the tree

key - the key for the node we are trying to find

keyComparator - the comparator to use to match node and key

removed - will be set to true if the node was found and removed, otherwise false

Returns:

the new root of the tree

visit

public static <TNode extends AvlUtil.AvlNode> void visit(TNode root,
                                                         AvlUtil.AvlNodeVisitor<TNode> visitor)

Visit each node of the tree

Parameters:

root - the current root of the tree

visitor - the AvlNodeVisitor instance

balance

private static <TNode extends AvlUtil.AvlNode> TNode balance(TNode p)

rotateRight

private static <TNode extends AvlUtil.AvlNode> TNode rotateRight(TNode p)

rotateLeft

private static <TNode extends AvlUtil.AvlNode> TNode rotateLeft(TNode q)

fixHeight

private static <TNode extends AvlUtil.AvlNode> void fixHeight(TNode node)

height

private static <TNode extends AvlUtil.AvlNode> int height(TNode node)

balanceFactor

private static <TNode extends AvlUtil.AvlNode> int balanceFactor(TNode node)