|int||get (int i) throws NoSuchElementException|
|int||getPosition (int i) throws NoSuchElementException|
|IntRBTArray (int array)|
|IntRBTArray (int array, int start)|
|void||setRootAddress (int start)|
|static final int||LEFTDTR = 1|
|static final int||RIGHTDTR = 2|
|static final int||TERMINAL = 0|
|static final int||TWODTRS = 3|
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.
i is the position of the first cell encoding a tree node in array
a. Then the expected memory layout of
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).