Class IntAVLTree


  • abstract class IntAVLTree
    extends java.lang.Object
    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.
    • 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 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
      • 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)