Descrição Detalhada

template<class T>
class persistence::red_black_tree::Node< T >

Nó da ARN parcialmente persistente.

Veja também: RedBlackTree Para mais informação sobre a ARN.

Métodos Públicos
	Node (const T &val, int version)
	Construtor padrão. Mais...

Campos Originais
Campos existentes em um nó de uma ARN não-persistente.
Node *	child [2]
	Nós filhos do nó. Mais...

bool	red
	Cor do nó (vermelho ou preto) Este campo só armazena a cor de nós ativos, ou seja, nós com `copy = nullptr`. Mais...

const T	value
	Valor armazenado pelo nó Como este é um nó de uma árvore de busca binária, vale que os valores dos nós em sua subárvore esquerda (descendentes de `child[0]`) tem valor menor ou igual à `value`, e valores de nós em sua subárvore direita tem valor maior ou igual à `value`.

Campos Persistentes
Campos usados para manter o nó persistente.
int	timestamp
	Tempo de criação do nó. Mais...

Node *	copy
	Cópia do nó (se não é ativo). Mais...

Node *	parent
	Nó pai do nó. Mais...

Ponteiro extra
Campos associados ao ponteiro extra deste nó. O nó tem um ponteiro extra se `extraTimestamp != -1`. Nesse caso, esse ponteiro extra é extra, foi criado na versão extraTimestamp, e tem lado extraSide.
Node *	extra
	Ponteiro extra. Mais...

bool	extraSide
	Lado do ponteiro extra. Mais...

int	extraTimestamp
	Tempo de criação do ponteiro extra. Mais...

Construtores & Destrutores

template<class T>

persistence::red_black_tree::Node< T >::Node	(	const T &	val,
		int	version
	)

Construtor padrão.

Parâmetros

val	Valor para o nó.
version	Versão de criação.

Campos

template<class T>

Node* persistence::red_black_tree::Node< T >::child[2]

Nós filhos do nó.

0 é o nó esquerdo e 1 o direito.

template<class T>

Node* persistence::red_black_tree::Node< T >::copy

Cópia do nó (se não é ativo).

Operações de modificação podem causar a cópia de nós. Nesse caso, o nó que foi criado pela cópia deste é armazenado neste campo.

Se copy = null, o nó é ativo e é válido para as versões a partir da versão timestamp até a mais atual. Caso contrário, o nó é valido para as versões a partir de timestamp até copy.timestamp - 1.

template<class T>

Node* persistence::red_black_tree::Node< T >::extra

Ponteiro extra.

Se extraTimestamp = -1, esse campo é inválido e deve ser ignorado. Caso contrário, representa o ponteiro extra do nó. Seu valor pode ser nulo. O campo extraSide indica se este é um ponteiro esquerdo ou direito.

template<class T>

bool persistence::red_black_tree::Node< T >::extraSide

Lado do ponteiro extra.

Se extraTimestamp = -1, esse campo é inválido e deve ser ignorado. Caso contrário, representa o lado do ponteiro extra.

Veja também: extra

Anotações: É necessário armazenar este valor pois o ponteiro extra pode ser nulo, ou podem existir valores repetidos na árvore, e nesses casos não é possível inferir o lado do ponteiro apenas comparando seu valor com value.

template<class T>

int persistence::red_black_tree::Node< T >::extraTimestamp

Tempo de criação do ponteiro extra.

O campo armazena a versão em que o ponteiro extra foi adicionado ao nó, ou -1 se este nó não tem ponteiro extra.

template<class T>

Node* persistence::red_black_tree::Node< T >::parent

Nó pai do nó.

Este campo só armazena os pais de nós ativos, ou seja, nós com copy = nullptr. Caso o nó não seja ativo, nullptr é armazenado.

Mais especificamente, o campo armazena qual nó ativo, se algum, aponta para este nó.

template<class T>

bool persistence::red_black_tree::Node< T >::red

Cor do nó (vermelho ou preto) Este campo só armazena a cor de nós ativos, ou seja, nós com copy = nullptr.