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.
Modifier and Type | Field and Description |
---|---|
protected Random |
rand |
black, color, default_size, greatestNode, growth_factor, initialSize, key, klrp, klrp1, klrp2, klrp3, left, MAXklrp0, MAXklrpMask, multiplication_limit, next, NIL, parent, red, right, root, size, useklrp
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
|
boolean |
deleteKey(int aKey) |
int |
findInsertionPoint(int k)
Find the node such that key[node] ≥ k and key[previous(node)] < k.
|
int |
findKey(int k)
Find the first node such that k <= key[node].
|
int |
getKeyForNode(int node) |
int |
insertKey(int k) |
int |
insertKeyWithDups(int k) |
IntListIterator |
iterator() |
ComparableIntIterator |
iterator(IntComparator comp)
Method iterator.
|
IntPointerIterator |
pointerIterator() |
IntPointerIterator |
pointerIterator(int aKey) |
ComparableIntPointerIterator |
pointerIterator(IntComparator comp,
int[] detectIllegalIndexUpdates,
int typeCode) |
protected int |
treeInsert(int k) |
protected int |
treeInsertWithDups(int k) |
contains, containsKey, deleteFixup, deleteNode, ensureArrayCapacity, ensureCapacity, ensureCapacityKlrp, findInsertionPointNoDups, findKeyDown, flush, getFirstNode, getKey, getLeft, getParent, getRight, getXXX, initVars, leftRotate, maxDepth, maxDepth, minDepth, minDepth, newNode, nextNode, nextPowerOf2, nodeDepth, nodeDepth, previousNode, printKeys, printKeys, rightRotate, satisfiesRBProps, satisfiesRedBlackProperties, setAsRoot, setKey, setLeft, setParent, setRight, setupArrays, setXXX, size
protected final Random rand
public IntArrayRBT()
public IntArrayRBT(int initialSize)
public int getKeyForNode(int node)
protected int treeInsert(int k)
protected int treeInsertWithDups(int k)
public int insertKey(int k)
public int add(int k)
public boolean addAdded(int k)
k
- public int insertKeyWithDups(int k)
public int findKey(int k)
findKey
in class IntArrayRBTcommon
public int findInsertionPoint(int k)
k
- the keypublic boolean deleteKey(int aKey)
public ComparableIntIterator iterator(IntComparator comp)
public IntListIterator iterator()
public IntPointerIterator pointerIterator()
public IntPointerIterator pointerIterator(int aKey)
public ComparableIntPointerIterator pointerIterator(IntComparator comp, int[] detectIllegalIndexUpdates, int typeCode)
Copyright © 2014. All rights reserved.