Class IntAVLTree

java.lang.Object
com.tdunning.math.stats.IntAVLTree
All Implemented Interfaces:
Serializable

abstract class IntAVLTree extends Object implements 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 
    A stack of int values.
    private static class 
     
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private byte[]
     
    private int[]
     
    protected static final int
    We use 0 instead of -1 so that left(NIL) works without condition.
     
    private int[]
     
    private int[]
     
    private int
     
  • Constructor Summary

    Constructors
    Constructor
    Description
     
    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
    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 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.
    final 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)
     
    final 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
    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
    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 Details

    • NIL

      protected static final int NIL
      We use 0 instead of -1 so that left(NIL) works without condition.
      See Also:
    • nodeAllocator

      private final IntAVLTree.NodeAllocator nodeAllocator
    • root

      private int root
    • parent

      private int[] parent
    • left

      private int[] left
    • depth

      private byte[] depth
  • Constructor Details

    • IntAVLTree

      IntAVLTree(int initialCapacity)
    • IntAVLTree

      IntAVLTree()
  • Method Details

    • 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)