## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- Alphabetical List
- Class List
- Class Hierarchy
- Class Members

# csRedBlackTree< K > Class Template Reference
[Containers]

A red-black-tree. More...

`#include <csutil/redblacktree.h>`

List of all members.

## Public Member Functions

bool | Contains (const K &key) const
| Check whether a key is in the tree.
| csRedBlackTree (const csRedBlackTree &other)
| csRedBlackTree (size_t allocatorBlockSize=4096)
| Construct a new tree.
bool | Delete (const K &key)
| Delete a key.
void | DeleteAll ()
| Delete all keys.
void | Empty ()
| Delete all the keys. (Idiomatic alias for DeleteAll().).
bool | In (const K &key) const
| Check whether a key is in the tree.
const K * | Insert (const K &key)
| Insert a key.
bool | IsEmpty () const
| Returns whether this tree has no nodes.
template<typename K2>
const K & | Find (const K2 &other, const K &fallback) const
template<typename K2>
const K * | Find (const K2 &other) const
| Locate key that is equal to 'other'.
template<typename CB>
void | TraverseInOrder (CB &callback) const
| Traverse tree.

## Protected Types

enum | NodeColor

## Protected Member Functions

void | DeleteFixup (Node *node)
| Fix up the RB tree after a deletion.
void | DeleteNode (Node *node)
| Delete a node from the tree.
void | InsertFixup (Node *node)
| Fix up the RB tree after an insert.
bool | IsBlack (Node *node) const
| Check whether a node is black. Note that 0 nodes are by definition black.
bool | IsRed (Node *node) const
| Check whether a node is red.
Node * | LocateNode (Node *node, const K &key) const
| Find the node for a key.
void | RecursiveCopy (Node *&to, Node *parent, const Node *from)
| Duplicate a subtree.
Node * | RecursiveInsert (Node *parent, Node *&node, const K &key)
| Locate the place where a new node needs to be inserted.
template<typename CB>
void | RecursiveTraverseInOrder (Node *node, CB &callback) const
| Traverse tree.
void | RotateLeft (Node *pivot)
| Left-rotate subtree around 'pivot'.
void | RotateRight (Node *pivot)
| Right-rotate subtree around 'pivot'.
Node * | Successor (Node *node) const
| Return smallest node with a key greater than 'node's.
template<typename K2>
K & | Find (const K2 &other, K &fallback)
template<typename K2>
K * | Find (const K2 &other)
| Locate key that is equal to 'other'.
template<typename K2>
K & | RecursiveFind (Node *node, const K2 &other, K &fallback)
template<typename K2>
const K & | RecursiveFind (Node *node, const K2 &other, const K &fallback) const
template<typename K2>
K * | RecursiveFind (Node *node, const K2 &other)
template<typename K2>
const K * | RecursiveFind (Node *node, const K2 &other) const
| Locate key that is equal to 'other'.

## Protected Attributes

csBlockAllocator< Node, csBlockAllocatorAlignPolicy< 2 > > | nodeAlloc
Node * | root

## Classes

struct | Node
| A node in the tree. More...

## Detailed Description

### template<typename K>
class csRedBlackTree< K >

A red-black-tree.

Remarks:
  Does not allow duplicate keys.

  Uses csComparator<> for key comparisons.

  Only stores keys. If you need a key-value-map, look at csRedBlackTreeMap.

Definition at line 41 of file redblacktree.h.

## Constructor & Destructor Documentation

template<typename K>
csRedBlackTree< K >::csRedBlackTree | ( | size_t | allocatorBlockSize = `4096` | ) | `[inline]`

Construct a new tree.

Parameters:

  | allocatorBlockSize | Block size in bytes used by the internal block allocator for nodes.

Definition at line 433 of file redblacktree.h.

## Member Function Documentation

template<typename K>
bool csRedBlackTree< K >::Contains | ( | const K & | key | ) | const`[inline]`

Check whether a key is in the tree.

Remarks:
  This is rigidly equivalent to Contains(key), but may be considered more idiomatic by some.

Definition at line 475 of file redblacktree.h.

template<typename K>
bool csRedBlackTree< K >::Delete | ( | const K & | key | ) | `[inline]`

Delete a key.

Returns:
  Whether the deletion was successful. Fails if the key is not in the tree.

Definition at line 458 of file redblacktree.h.

template<typename K>
void csRedBlackTree< K >::DeleteAll | ( |  | ) | `[inline]`

| Delete all keys. Reimplemented in csRedBlackTreeMap< K, T >. Definition at line 492 of file redblacktree.h.

template<typename K>
void csRedBlackTree< K >::DeleteFixup | ( | Node * | node | ) | `[inline, protected]`

| Fix up the RB tree after a deletion. Definition at line 237 of file redblacktree.h.

template<typename K>
void csRedBlackTree< K >::DeleteNode | ( | Node * | node | ) | `[inline, protected]`

| Delete a node from the tree. Definition at line 204 of file redblacktree.h.

template<typename K>
void csRedBlackTree< K >::Empty | ( |  | ) | `[inline]`

| Delete all the keys. (Idiomatic alias for DeleteAll().). Reimplemented in csRedBlackTreeMap< K, T >. Definition at line 498 of file redblacktree.h.

template<typename K>
template<typename K2>
const K* csRedBlackTree< K >::Find | ( | const K2 & | other | ) | const`[inline]`

| Locate key that is equal to 'other'. Definition at line 480 of file redblacktree.h.

template<typename K>
template<typename K2>
K* csRedBlackTree< K >::Find | ( | const K2 & | other | ) | `[inline, protected]`

| Locate key that is equal to 'other'. Definition at line 401 of file redblacktree.h.

template<typename K>
bool csRedBlackTree< K >::In | ( | const K & | key | ) | const`[inline]`

| Check whether a key is in the tree. Definition at line 466 of file redblacktree.h.

template<typename K>
const K* csRedBlackTree< K >::Insert | ( | const K & | key | ) | `[inline]`

Insert a key.

Returns:
  A pointer to the copy of the key stored in the tree, or 0 if the key already exists.

Definition at line 446 of file redblacktree.h.

template<typename K>
void csRedBlackTree< K >::InsertFixup | ( | Node * | node | ) | `[inline, protected]`

| Fix up the RB tree after an insert. Definition at line 143 of file redblacktree.h.

template<typename K>
bool csRedBlackTree< K >::IsBlack | ( | Node * | node | ) | const`[inline, protected]`

| Check whether a node is black. Note that 0 nodes are by definition black. Definition at line 137 of file redblacktree.h.

template<typename K>
bool csRedBlackTree< K >::IsEmpty | ( |  | ) | const`[inline]`

| Returns whether this tree has no nodes. Reimplemented in csRedBlackTreeMap< K, T >. Definition at line 500 of file redblacktree.h.

template<typename K>
bool csRedBlackTree< K >::IsRed | ( | Node * | node | ) | const`[inline, protected]`

| Check whether a node is red. Definition at line 140 of file redblacktree.h. Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup().

template<typename K>
Node* csRedBlackTree< K >::LocateNode | ( | Node * | node,
|  | const K & | key
| ) | const`[inline, protected]`

| Find the node for a key. Definition at line 308 of file redblacktree.h.

template<typename K>
void csRedBlackTree< K >::RecursiveCopy | ( | Node *& | to,
|  | Node * | parent,
|  | const Node * | from
| ) | `[inline, protected]`

| Duplicate a subtree. Definition at line 413 of file redblacktree.h.

template<typename K>
template<typename K2>
const K* csRedBlackTree< K >::RecursiveFind | ( | Node * | node,
|  | const K2 & | other
| ) | const`[inline, protected]`

| Locate key that is equal to 'other'. Definition at line 341 of file redblacktree.h.

template<typename K>
Node* csRedBlackTree< K >::RecursiveInsert | ( | Node * | parent,
|  | Node *& | node,
|  | const K & | key
| ) | `[inline, protected]`

| Locate the place where a new node needs to be inserted. Definition at line 76 of file redblacktree.h. Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::RecursiveInsert().

template<typename K>
template<typename CB>
void csRedBlackTree< K >::RecursiveTraverseInOrder | ( | Node * | node,
|  | CB & | callback
| ) | const`[inline, protected]`

| Traverse tree. Definition at line 391 of file redblacktree.h.

template<typename K>
void csRedBlackTree< K >::RotateLeft | ( | Node * | pivot | ) | `[inline, protected]`

| Left-rotate subtree around 'pivot'. Definition at line 99 of file redblacktree.h. Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup().

template<typename K>
void csRedBlackTree< K >::RotateRight | ( | Node * | pivot | ) | `[inline, protected]`

| Right-rotate subtree around 'pivot'. Definition at line 118 of file redblacktree.h. Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup().

template<typename K>
Node* csRedBlackTree< K >::Successor | ( | Node * | node | ) | const`[inline, protected]`

| Return smallest node with a key greater than 'node's. Definition at line 321 of file redblacktree.h.

template<typename K>
template<typename CB>
void csRedBlackTree< K >::TraverseInOrder | ( | CB & | callback | ) | const`[inline]`

| Traverse tree. Reimplemented in csRedBlackTreeMap< K, T >. Definition at line 505 of file redblacktree.h.

The documentation for this class was generated from the following file:

- csutil/redblacktree.h