public class IntArrayRBTcommon extends Object
Modifier and Type | Field and Description |
---|---|
protected static boolean |
black |
protected boolean[] |
color |
protected static int |
default_size |
int |
greatestNode |
protected int |
growth_factor |
protected int |
initialSize |
protected int[] |
klrp |
protected int[] |
klrp1 |
protected int[] |
klrp2 |
protected int[] |
klrp3 |
protected static int |
MAXklrp0 |
protected static int |
MAXklrpMask |
protected int |
multiplication_limit |
protected int |
next |
static int |
NIL |
protected static boolean |
red |
protected int |
root |
protected int |
size |
Constructor and Description |
---|
IntArrayRBTcommon()
Constructor for IntArrayRBT.
|
IntArrayRBTcommon(int initialSize) |
Modifier and Type | Method and Description |
---|---|
protected int |
compare(int v1,
int v2) |
boolean |
contains(int k) |
boolean |
containsKey(int k) |
protected void |
deleteFixup(int x) |
protected void |
deleteNode(int z)
delete node z
Step 1: locate a node to delete at the bottom of the tree.
|
protected int[] |
ensureArrayCapacity(int[] array,
int newSize) |
protected void |
ensureCapacityKlrp(int requiredSize)
There are two strategies for storing data, controlled by useklrp.
|
int |
findInsertionPoint(int k)
Find the node such that key[node] ≥ k and key[previous(node)] < k.
|
int |
findInsertionPointCmn(int k,
boolean moveToLeftmost) |
int |
findInsertionPointNoDups(int k)
Find the node such that key[node] ≥ k and key[previous(node)] < k.
|
int |
findKey(int k) |
protected int |
findKeyDown(int k,
int node) |
void |
flush() |
int |
getFirstNode() |
protected int |
getKeyForNode(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) |
int |
nextNode(int node)
Method: if there's a right descendant, return the left-most chain down on that link
Else, go up until parent has a right descendant not the previous, and return that.
|
protected int |
nextPowerOf2(int v) |
int |
nodeDepth(int k) |
protected int |
nodeDepth(int node,
int depth,
int k) |
int |
previousNode(int node)
Method: if there's a left descendant, go to the right-most bottom of that
Otherwise, ascend up until the parent's left descendant isn't the previous link
|
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 |
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 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
public 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 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)
node
- -value
- -protected int getKeyForNode(int node)
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)
public int findKey(int k)
k
- -protected int findKeyDown(int k, int node)
public int findInsertionPoint(int k)
k
- the keypublic int findInsertionPointNoDups(int k)
k
- -public int findInsertionPointCmn(int k, boolean moveToLeftmost)
public final boolean containsKey(int k)
public final boolean contains(int k)
public final int getFirstNode()
public final int nextNode(int node)
node
- starting pointpublic final int previousNode(int node)
node
- the current node indexprotected void deleteNode(int z)
z
- node to be removed, logicallyprotected void deleteFixup(int x)
protected int compare(int v1, int v2)
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.