public class IntArrayRBTcommon extends Object
Modifier and Type | Field and Description |
---|---|
protected static boolean |
black |
protected boolean[] |
color |
protected static int |
default_size |
protected int |
greatestNode |
protected int |
growth_factor |
protected int |
initialSize |
protected int[] |
key |
protected int[] |
klrp |
protected int[] |
klrp1 |
protected int[] |
klrp2 |
protected int[] |
klrp3 |
protected int[] |
left |
protected static int |
MAXklrp0 |
protected static int |
MAXklrpMask |
protected int |
multiplication_limit |
protected int |
next |
static int |
NIL |
protected int[] |
parent |
protected static boolean |
red |
protected int[] |
right |
protected int |
root |
protected int |
size |
protected static boolean |
useklrp |
Constructor and Description |
---|
IntArrayRBTcommon()
Constructor for IntArrayRBT.
|
IntArrayRBTcommon(int initialSize) |
Modifier and Type | Method and Description |
---|---|
boolean |
contains(int k) |
boolean |
containsKey(int k) |
protected void |
deleteFixup(int x) |
protected void |
deleteNode(int z) |
protected int[] |
ensureArrayCapacity(int[] array,
int newSize) |
protected void |
ensureCapacityKlrp(int requiredSize)
There are two strategies for storing data, controlled by useklrp.
|
int |
findInsertionPointNoDups(int k)
Find the node such that key[node] ≥ k and key[previous(node)] < k.
|
protected int |
findKey(int k) |
protected int |
findKeyDown(int k,
int node) |
void |
flush() |
protected int |
getFirstNode() |
protected int |
getKey(int node) |
protected int |
getLeft(int node) |
protected int |
getParent(int node) |
protected int |
getRight(int node) |
protected int |
getXXX(int node,
int offset) |
protected void |
initVars() |
protected void |
leftRotate(int x) |
int |
maxDepth() |
protected int |
maxDepth(int node,
int depth) |
int |
minDepth() |
protected int |
minDepth(int node,
int depth) |
protected int |
newNode(int k) |
protected int |
nextNode(int node) |
protected int |
nextPowerOf2(int v) |
int |
nodeDepth(int k) |
protected int |
nodeDepth(int node,
int depth,
int k) |
protected int |
previousNode(int node) |
void |
printKeys() |
protected void |
printKeys(int node,
int offset,
StringBuffer buf) |
protected void |
rightRotate(int x) |
protected boolean |
satisfiesRBProps(int node,
int blackDepth,
int currentBlack) |
boolean |
satisfiesRedBlackProperties() |
protected void |
setAsRoot(int x) |
protected int |
setKey(int node,
int value) |
protected int |
setLeft(int node,
int value) |
protected int |
setParent(int node,
int value) |
protected int |
setRight(int node,
int value) |
protected void |
setupArrays() |
protected int |
setXXX(int node,
int offset,
int value) |
int |
size() |
protected static final boolean useklrp
protected int[] key
protected int[] left
protected int[] right
protected int[] parent
protected int[] klrp
protected int[] klrp1
protected int[] klrp2
protected int[] klrp3
protected static final int MAXklrp0
protected static final int MAXklrpMask
protected boolean[] color
protected int next
protected int size
protected int root
protected int greatestNode
protected static final int default_size
protected final int initialSize
protected final int growth_factor
protected final int multiplication_limit
public static final int NIL
protected static final boolean red
protected static final boolean black
public IntArrayRBTcommon()
public IntArrayRBTcommon(int initialSize)
protected int getXXX(int node, int offset)
protected int setXXX(int node, int offset, int value)
protected int getKey(int node)
protected int setKey(int node, int value)
protected int getLeft(int node)
protected int setLeft(int node, int value)
protected int getRight(int node)
protected int setRight(int node, int value)
protected int getParent(int node)
protected int setParent(int node, int value)
protected int nextPowerOf2(int v)
protected void setupArrays()
protected void initVars()
public void flush()
public final int size()
protected void ensureCapacityKlrp(int requiredSize)
requiredSize
- -protected int newNode(int k)
protected final void setAsRoot(int x)
protected final int[] ensureArrayCapacity(int[] array, int newSize)
array
- - the array to expand - may be klrp0, 1, 2, 3, etc.newSize
- = the total size - if in parts, the size of the partprotected final void leftRotate(int x)
protected final void rightRotate(int x)
protected int findKey(int k)
k
- -protected int findKeyDown(int k, int node)
public int findInsertionPointNoDups(int k)
k
- -public final boolean containsKey(int k)
public final boolean contains(int k)
protected final int getFirstNode()
protected final int nextNode(int node)
protected final int previousNode(int node)
protected void deleteNode(int z)
protected void deleteFixup(int x)
public boolean satisfiesRedBlackProperties()
protected boolean satisfiesRBProps(int node, int blackDepth, int currentBlack)
public int maxDepth()
public int minDepth()
public int nodeDepth(int k)
protected int nodeDepth(int node, int depth, int k)
protected int maxDepth(int node, int depth)
protected int minDepth(int node, int depth)
public final void printKeys()
protected final void printKeys(int node, int offset, StringBuffer buf)
Copyright © 2015. All rights reserved.