RBTree (ERNST API)

java.lang.Object
- cnslab.cnsmath.RBTree<T>

```
public class RBTree<T extends Comparable>
extends Object
```
RedBlack trees.

Version:

0.93
For an introduction to this package see Overview .

Author:

Doug Lea

Field Summary

Fields
Modifier and Type	Field and Description
`protected int`	`count_`
`FireEvent`	`firstFire` save time for noTillInputEvent iteration
`InputEvent`	`firstInput` save time for noTillFireEvent iteration
`Map`	`flags`
`boolean`	`iterExit` make iterate exit

Constructor Summary

Constructors
Constructor and Description

RBTree()
Constructs a new empty tree.

RBTree(RBCell<T> x)
Constructs a new tree with a root node x.

Constructors
Constructor and Description
`RBTree()` Constructs a new empty tree.
`RBTree(RBCell<T> x)` Constructs a new tree with a root node x.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`add(T element)` Implements collections.UpdatableBag.add.
`void`	`addIfAbsent(T element)` Implements collections.UpdatableBag.addIfAbsent Time complexity: O(log n).
`void`	`clear()` Implements collections.UpdatableCollection.clear.
`protected void`	`decCount()`
`void`	`exclude(T element)` Implements collections.UpdatableCollection.exclude.
`protected void`	`incCount()`
`boolean`	`includes(T element)` Implements collections.Collection.includes.
`void`	`inorderTreeWalk(RBCell<T> x, PrintStream p)` Prints the keys of current tree in inorder (ascending).
`void`	`inorderTreeWalk(RBCell<T> x, StringWrap p)`
`int`	`occurrencesOf(T element)` Implements collections.Collection.occurrencesOf.
`void`	`removeOneOf(T element)` Implements collections.UpdatableCollection.removeOneOf.
`void`	`replaceAllOf(T oldElement, T newElement)` Implements collections.UpdatableCollection.replaceAllOf.
`void`	`replaceOneOf(T oldElement, T newElement)` Implements collections.UpdatableCollection.replaceOneOf Time complexity: O(log n).
`RBCell<T>`	`root()` Returns the root of the tree.
`protected void`	`setCount(int c)` set the element count and update version_ if changed
`T`	`take()` Implements collections.UpdatableCollection.take.
`boolean`	`treeNoTillFireEvent(RBCell<T> x)`
`boolean`	`treeNoTillFireEvent2(RBCell<T> x)`
`boolean`	`treeNoTillInputEvent(RBCell<T> x)`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - count_
```
protected int count_
```
  - iterExit
```
public boolean iterExit
```
    make iterate exit
  - firstFire
```
public FireEvent firstFire
```
    save time for noTillInputEvent iteration
  - firstInput
```
public InputEvent firstInput
```
    save time for noTillFireEvent iteration
  - flags
```
public Map flags
```
- Constructor Detail
  - RBTree
```
public RBTree()
```
    Constructs a new empty tree.
  - RBTree
```
public RBTree(RBCell<T> x)
```
    Constructs a new tree with a root node x.
    
    Parameters:
    x - The root node of the tree.
- Method Detail
  - root
```
public RBCell<T> root()
```
    Returns the root of the tree.
    
    Returns:
    The root of the tree.
  - incCount
```
protected final void incCount()
```
  - decCount
```
protected final void decCount()
```
  - setCount
```
protected final void setCount(int c)
```
    set the element count and update version_ if changed
  - includes
```
public boolean includes(T element)
```
    Implements collections.Collection.includes. Time complexity: O(log n).
    
    See Also:
    collections.Collection#includes
  - occurrencesOf
```
public int occurrencesOf(T element)
```
    Implements collections.Collection.occurrencesOf. Time complexity: O(log n).
    
    See Also:
    collections.Collection#occurrencesOf
  - clear
```
public void clear()
```
    Implements collections.UpdatableCollection.clear. Time complexity: O(1).
    
    See Also:
    collections.UpdatableCollection#clear
  - exclude
```
public void exclude(T element)
```
    Implements collections.UpdatableCollection.exclude. Time complexity: O(log n * occurrencesOf(element)).
    
    See Also:
    collections.UpdatableCollection#exclude
  - removeOneOf
```
public void removeOneOf(T element)
```
    Implements collections.UpdatableCollection.removeOneOf. Time complexity: O(log n).
    
    See Also:
    collections.UpdatableCollection#removeOneOf
  - replaceOneOf
```
public void replaceOneOf(T oldElement,
                T newElement)
```
    Implements collections.UpdatableCollection.replaceOneOf Time complexity: O(log n).
    
    See Also:
    collections.UpdatableCollection#replaceOneOf
  - replaceAllOf
```
public void replaceAllOf(T oldElement,
                T newElement)
```
    Implements collections.UpdatableCollection.replaceAllOf. Time complexity: O(log n * occurrencesOf(oldElement)).
    
    See Also:
    collections.UpdatableCollection#replaceAllOf
  - take
```
public T take()
```
    Implements collections.UpdatableCollection.take. Time complexity: O(log n). Takes the least element.
    
    See Also:
    collections.UpdatableCollection#take
  - addIfAbsent
```
public void addIfAbsent(T element)
```
    Implements collections.UpdatableBag.addIfAbsent Time complexity: O(log n).
    
    See Also:
    collections.UpdatableBag#addIfAbsent
  - add
```
public void add(T element)
```
    Implements collections.UpdatableBag.add. Time complexity: O(log n).
    
    See Also:
    collections.UpdatableBag#add
  - treeNoTillFireEvent
```
public boolean treeNoTillFireEvent(RBCell<T> x)
```
  - treeNoTillFireEvent2
```
public boolean treeNoTillFireEvent2(RBCell<T> x)
```
  - treeNoTillInputEvent
```
public boolean treeNoTillInputEvent(RBCell<T> x)
```
  - inorderTreeWalk
```
public void inorderTreeWalk(RBCell<T> x,
                   PrintStream p)
```
    Prints the keys of current tree in inorder (ascending). Runs in Theta(n) time.
    
    Parameters:
    x - The node from which to start.
  - inorderTreeWalk
```
public void inorderTreeWalk(RBCell<T> x,
                   StringWrap p)
```

Class RBTree<T extends Comparable>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

count_

iterExit

firstFire

firstInput

flags

Constructor Detail

RBTree

RBTree

Method Detail

root

incCount

decCount

setCount

includes

occurrencesOf

clear

exclude

removeOneOf

replaceOneOf

replaceAllOf

take

addIfAbsent

add

treeNoTillFireEvent

treeNoTillFireEvent2

treeNoTillInputEvent

inorderTreeWalk

inorderTreeWalk