public class IntArrayRBT extends IntArrayRBTcommon
This tree implementation knows two modes of insertion: keys that are already in the tree can be rejected, or inserted as duplicates. Duplicate key insertion is randomized so that the tree's performance degrades gracefully in the presence of many identical keys.
black, color, default_size, greatestNode, growth_factor, initialSize, klrp, klrp1, klrp2, klrp3, MAXklrp0, MAXklrpMask, multiplication_limit, next, NIL, red, root, size
Constructor and Description |
---|
IntArrayRBT()
Constructor for IntArrayRBT.
|
IntArrayRBT(int initialSize) |
Modifier and Type | Method and Description |
---|---|
int |
add(int k) |
boolean |
addAdded(int k)
like add, but returns boolean flag true if not present before
|
void |
clear() |
boolean |
debugScanFor(int key) |
boolean |
deleteKey(int aKey) |
int |
getKeyForNode(int node) |
int |
insertKey(int k) |
int |
insertKeyShowNegative(int k) |
IntListIterator |
iterator() |
<T extends FeatureStructure> |
pointerIterator(FSRBTSetIndex<T> fsSetIndex,
int[] detectIllegalIndexUpdates,
IntComparator comp) |
<T extends FeatureStructure> |
pointerIterator(IntComparator comp,
FSRBTSetIndex<T> fsSetIndex) |
protected int |
treeInsert(int k) |
protected int |
treeInsert(int k,
boolean withDups) |
protected int |
treeInsertWithDups(int k) |
compare, contains, containsKey, deleteFixup, deleteNode, ensureArrayCapacity, ensureCapacityKlrp, findInsertionPoint, findInsertionPointCmn, findInsertionPointNoDups, findKey, findKeyDown, flush, getFirstNode, getLeft, getParent, getRight, getXXX, initVars, leftRotate, maxDepth, maxDepth, minDepth, minDepth, newNode, nextNode, nextPowerOf2, nodeDepth, nodeDepth, previousNode, printKeys, printKeys, rightRotate, satisfiesRBProps, satisfiesRedBlackProperties, setAsRoot, setLeft, setParent, setRight, setupArrays, setXXX, size
public IntArrayRBT()
public IntArrayRBT(int initialSize)
protected int treeInsert(int k)
k
- the value to insertprotected int treeInsertWithDups(int k)
protected int treeInsert(int k, boolean withDups)
public int insertKey(int k)
public int add(int k)
public boolean addAdded(int k)
k
- -public int insertKeyShowNegative(int k)
public boolean deleteKey(int aKey)
public void clear()
public IntListIterator iterator()
public <T extends FeatureStructure> IntPointerIterator pointerIterator(IntComparator comp, FSRBTSetIndex<T> fsSetIndex)
public <T extends FeatureStructure> ComparableIntPointerIterator<T> pointerIterator(FSRBTSetIndex<T> fsSetIndex, int[] detectIllegalIndexUpdates, IntComparator comp)
public boolean debugScanFor(int key)
public int getKeyForNode(int node)
getKeyForNode
in class IntArrayRBTcommon
Copyright © 2006–2022 The Apache Software Foundation. All rights reserved.