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
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 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 innode
.protected abstract void
copy(int node)
Compare data intonode
.int
depth(int node)
Return the depth nodes that are stored belownode
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 undernode
.protected void
fixAggregates(int node)
int
last(int node)
Return the largest node undernode
.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 intonode
.int
next(int node)
Return the least node that is strictly greater thannode
.(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 thannode
.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 tonewCapacity
(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 undern
private void
rotateRight(int n)
Rotate right the subtree undern
int
size()
Return the size of this tree.private void
swap(int node1, int node2)
void
update(int node)
Updatenode
with the current data.
-
-
-
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
-
-
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 tonewCapacity
(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 belownode
including itself.
-
first
public int first(int node)
Return the least node undernode
.
-
last
public int last(int node)
Return the largest node undernode
.
-
next
public final int next(int node)
Return the least node that is strictly greater thannode
.
-
prev
public final int prev(int node)
Return the highest node that is strictly less thannode
.
-
compare
protected abstract int compare(int node)
Compare data against data which is stored innode
.
-
copy
protected abstract void copy(int node)
Compare data intonode
.
-
merge
protected abstract void merge(int node)
Merge data intonode
.
-
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)
Updatenode
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 undern
-
rotateRight
private void rotateRight(int n)
Rotate right the subtree undern
-
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)
-
-