public class IntRBTArray extends Object
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 nodea[i+1]
is the element of the nodea[i+2]
is one of:
IntRBTArray.TERMINAL
: this is a terminal nodeIntRBTArray.LEFTDTR
: this node only has a left daughter, so
a[i+3]
is the first cell of the left daughter nodeIntRBTArray.RIGHTDTR
: this node only has a right daughter, so
a[i+3]
is the first cell of the right daughter nodeIntRBTArray.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 nodeNote 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).
Modifier and Type | Field and 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 and 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.
|
Modifier and Type | Method and Description |
---|---|
int |
get(int i)
Retrieve the value for a certain key.
|
int |
getPosition(int i)
Get the position of a value for a key.
|
void |
setRootAddress(int start)
Set the address of the root node of the tree.
|
int[] |
toArray()
Getter for the internal array.
|
public static final int TERMINAL
public static final int LEFTDTR
public static final int RIGHTDTR
public static final int TWODTRS
public IntRBTArray(int[] array, int start)
start
- Address of the root node of the tree.array
- The array containing the search tree.public IntRBTArray(int[] array)
0
.array
- The array containing the search tree.public int[] toArray()
public void setRootAddress(int start)
start
- the address.public int get(int i) throws NoSuchElementException
i
- The input key.NoSuchElementException
- If the key is not defined in the tree.public int getPosition(int i) throws NoSuchElementException
i
- The key.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
.NoSuchElementException
Copyright © 2006–2016 The Apache Software Foundation. All rights reserved.