Class IntRBTArray


  • public class IntRBTArray
    extends Object
    Helper class to read array-based binary search trees with integers as keys and values. No write access to the tree is provided. See IntRedBlackTree on how to generate such an array representation. The name is a bit of a misnomer, since nothing in this class is specific to red-black trees.

    Suppose i is the position of the first cell encoding a tree node in array a. Then the expected memory layout of a is:

    • a[i] is the key of the node
    • a[i+1] is the element of the node
    • a[i+2] is one of:
      • IntRBTArray.TERMINAL: this is a terminal node
      • IntRBTArray.LEFTDTR: this node only has a left daughter, so a[i+3] is the first cell of the left daughter node
      • IntRBTArray.RIGHTDTR: this node only has a right daughter, so a[i+3] is the first cell of the right daughter node
      • IntRBTArray.TWODTRS: this node has two daughters. a[i+3] contains the address of the right daughter, and a[i+4] is the start of the left daughter node

    Note that the array from which an IntRBTArray object is constructed can contain other data as well. However, we assume that the addressing (the right daughter addresses, to be precise), must be absolute (i.e., not relative to some starting point within the array).

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static int LEFTDTR
      Code for a node with only a left daughter.
      static int RIGHTDTR
      Code for a node with only a right daughter.
      static int TERMINAL
      Code for a terminal node in the array.
      static int TWODTRS
      Code for a node with two daughters.
    • Constructor Summary

      Constructors 
      Constructor Description
      IntRBTArray​(int[] array)
      This constructor assumes that the root node is located at 0.
      IntRBTArray​(int[] array, int start)
      Constructor that takes a start point as parameter.
    • Field Detail

      • TERMINAL

        public static final int TERMINAL
        Code for a terminal node in the array.
        See Also:
        Constant Field Values
      • LEFTDTR

        public static final int LEFTDTR
        Code for a node with only a left daughter.
        See Also:
        Constant Field Values
      • RIGHTDTR

        public static final int RIGHTDTR
        Code for a node with only a right daughter.
        See Also:
        Constant Field Values
      • TWODTRS

        public static final int TWODTRS
        Code for a node with two daughters.
        See Also:
        Constant Field Values
    • Constructor Detail

      • IntRBTArray

        public IntRBTArray​(int[] array,
                           int start)
        Constructor that takes a start point as parameter.
        Parameters:
        start - Address of the root node of the tree.
        array - The array containing the search tree.
      • IntRBTArray

        public IntRBTArray​(int[] array)
        This constructor assumes that the root node is located at 0.
        Parameters:
        array - The array containing the search tree.
    • Method Detail

      • toArray

        public int[] toArray()
        Getter for the internal array.
        Returns:
        The internal array.
      • setRootAddress

        public void setRootAddress​(int start)
        Set the address of the root node of the tree.
        Parameters:
        start - the address.
      • get

        public int get​(int i)
                throws NoSuchElementException
        Retrieve the value for a certain key.
        Parameters:
        i - The input key.
        Returns:
        The value, if key was found.
        Throws:
        NoSuchElementException - If the key is not defined in the tree.
      • getPosition

        public int getPosition​(int i)
                        throws NoSuchElementException
        Get the position of a value for a key.
        Parameters:
        i - The key.
        Returns:
        The address of the value for i, if it's found; -1, else. This routine may also return -1 when the tree is corrupted. Of course, with a corrupted tree, results will in general be unpredictable. However, this routine will not throw an ArrayIndexOutOfBoundsException.
        Throws:
        NoSuchElementException