Package com.tdunning.math.stats

Class IntAVLTree

java.lang.Object

com.tdunning.math.stats.IntAVLTree

All Implemented Interfaces:

java.io.Serializable

abstract class IntAVLTree
extends java.lang.Object
implements java.io.Serializable

An AVL-tree structure stored in parallel arrays. This class only stores the tree structure, so you need to extend it if you want to add data to the nodes, typically by using arrays and node identifiers as indices.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	IntAVLTree.IntStack	A stack of int values.
private static class	IntAVLTree.NodeAllocator

Field Summary

Fields

Modifier and Type	Field	Description
private byte[]	depth
private int[]	left
protected static int	NIL	We use 0 instead of -1 so that left(NIL) works without condition.
private IntAVLTree.NodeAllocator	nodeAllocator
private int[]	parent
private int[]	right
private int	root

Constructor Summary

Constructors

Constructor	Description
IntAVLTree()
IntAVLTree(int initialCapacity)

Method Summary

Modifier and Type	Method	Description
boolean	add()	Add current data to the tree and return true if a new node was added to the tree or false if the node was merged into an existing node.
private int	balanceFactor(int node)
int	capacity()	Return the current capacity, which is the number of nodes that this tree can hold.
(package private) void	checkBalance(int node)
protected abstract int	compare(int node)	Compare data against data which is stored in node.
protected abstract void	copy(int node)	Compare data into node.
int	depth(int node)	Return the depth nodes that are stored below node including itself.
private void	depth(int node, int depth)
int	find()	Find a node in this tree.
int	first(int node)	Return the least node under node.
protected void	fixAggregates(int node)
int	last(int node)	Return the largest node under node.
int	left(int node)	Return the left child of the provided node.
private void	left(int node, int left)
protected abstract void	merge(int node)	Merge data into node.
int	next(int node)	Return the least node that is strictly greater than node.
(package private) static int	oversize(int size)	Grow a size by 1/8.
int	parent(int node)	Return the parent of the provided node.
private void	parent(int node, int parent)
int	prev(int node)	Return the highest node that is strictly less than node.
private void	rebalance(int node)
private void	release(int node)
void	remove(int node)	Remove the specified node from the tree.
protected void	resize(int newCapacity)	Resize internal storage in order to be able to store data for nodes up to newCapacity (excluded).
int	right(int node)	Return the right child of the provided node.
private void	right(int node, int right)
int	root()	Return the current root of the tree.
private void	rotateLeft(int n)	Rotate left the subtree under n
private void	rotateRight(int n)	Rotate right the subtree under n
int	size()	Return the size of this tree.
private void	swap(int node1, int node2)
void	update(int node)	Update node with the current data.

Methods inherited from class java.lang.Object

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

Field Detail

NIL

protected static final int NIL

We use 0 instead of -1 so that left(NIL) works without condition.

See Also:

Constant Field Values

nodeAllocator

private final IntAVLTree.NodeAllocator nodeAllocator

root

private int root

parent

private int[] parent

left

private int[] left

right

private int[] right

depth

private byte[] depth

Constructor Detail

IntAVLTree

IntAVLTree(int initialCapacity)

IntAVLTree

IntAVLTree()

Method Detail

oversize

static int oversize(int size)

Grow a size by 1/8.

root

public int root()

Return the current root of the tree.

capacity

public int capacity()

Return the current capacity, which is the number of nodes that this tree can hold.

resize

protected void resize(int newCapacity)

Resize internal storage in order to be able to store data for nodes up to newCapacity (excluded).

size

public int size()

Return the size of this tree.

parent

public int parent(int node)

Return the parent of the provided node.

left

public int left(int node)

Return the left child of the provided node.

right

public int right(int node)

Return the right child of the provided node.

depth

public int depth(int node)

Return the depth nodes that are stored below node including itself.

first

public int first(int node)

Return the least node under node.

last

public int last(int node)

Return the largest node under node.

next

public final int next(int node)

Return the least node that is strictly greater than node.

prev

public final int prev(int node)

Return the highest node that is strictly less than node.

compare

protected abstract int compare(int node)

Compare data against data which is stored in node.

copy

protected abstract void copy(int node)

Compare data into node.

merge

protected abstract void merge(int node)

Merge data into node.

add

public boolean add()

Add current data to the tree and return true if a new node was added to the tree or false if the node was merged into an existing node.

find

public int find()

Find a node in this tree.

update

public void update(int node)

Update node with the current data.

remove

public void remove(int node)

Remove the specified node from the tree.

release

private void release(int node)

swap

private void swap(int node1,
                  int node2)

balanceFactor

private int balanceFactor(int node)

rebalance

private void rebalance(int node)

fixAggregates

protected void fixAggregates(int node)

rotateLeft

private void rotateLeft(int n)

Rotate left the subtree under n

rotateRight

private void rotateRight(int n)

Rotate right the subtree under n

parent

private void parent(int node,
                    int parent)

left

private void left(int node,
                  int left)

right

private void right(int node,
                   int right)

depth

private void depth(int node,
                   int depth)

checkBalance

void checkBalance(int node)