Descrição Detalhada

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

Árvore rubro-negra (ARN) parcialmente persistente.

Feita utilizando o método de Node copying, por Driscoll et. al. [1] , para tornar a estrutura persistente e baseado na implementação (não persistente) de Cormen et. al. CormenRedBlack .

O tipo T deve ser comparável usando o operador <.

Ao criar a árvore, esta tem versão 0 e está vazia. Cada operação de modificação (Insert, Remove) modifica a versão mais nova da árvore e cria uma nova versão. As operações de acesso (Find) podem ser realizadas qualquer versão já criada da ARN.

Biblioteca Pública
Estas funções podem ser usadas mesmo sem saber a estrutura por trás, como em um set, que é implementado usando uma ARN mas cujas funções não dependem disso e podem ser implementadas com outras estruturas. As funções servem como uma ED que armazena um conjunto de elementos, parcialmente persistente, com inserção e remoção em tempo logaritmico.
const T *	Find (const T &x, int version)
	Busca por um valor em dada versão da ARN. Mais...

void	Insert (const T &value)
	Inserção de valor na ARN. Mais...

const T *	Remove (const T &value)
	Remoção de valor na ARN. Mais...

int	current ()
	Versão atual da ARN. Mais...

Campos, Construção e Acesso
std::vector< Node< T > * >	roots
	Raízes de todas as versões. Mais...

	RedBlackTree ()
	Construtor. Mais...

	~RedBlackTree ()
	Destrutor. Mais...

Node< T > *	Child (Node< T > *u, bool side, int version) const
	Retorna um filho de um nó em dada versão. Mais...

Funções Auxiliares de Modificação
As seguintes funções são auxiliares e usadas internamente durante operações de modificação. Estas funções sempre recebem um nó `u`, e é necessário que `u` tenha sido criado na atual operação (de acesso ou modificação) ou tenha sido ativo no início desta operação. Todas as funções terão então a pre-condição: "u ou sua cópia são ativos". Como sempre queremos modificar ou acessar a versão mais nova do nó `u`, essa condição garante que estas funções precisem apenas modificar `u` ou sua cópia.
Node< T > *	Active (Node< T > *u)
	Versão ativa de um nó. Mais...

Node< T > *	Child (Node< T > *u, bool side)
	Retorna um filho de um nó na versão atual. Mais...

void	Modify (Node< T > u, bool side, Node< T > v)
	Modificação de filho de um nó. Mais...

Node< T > *	Copy (Node< T > *u)
	Copia um nó. Mais...

void	Rotate (Node< T > *u, bool side)
	Rotaciona um nó. Mais...

void	Transplant (Node< T > u, Node< T > x)
	Subsitui um nó. Mais...

Node< T > *	MinElement (Node< T > *u)
	Menor elemento em uma subárvore na versão atual. Mais...

void	AddBlack (Node< T > *y, bool side)
	Arruma violações causadas por remoção. Mais...

Construtores & Destrutores

template<class T>

persistence::red_black_tree::RedBlackTree< T >::RedBlackTree ( )

Construtor.

Constrói a estrutura com apenas uma versão 0 vazia.

template<class T>

persistence::red_black_tree::RedBlackTree< T >::~RedBlackTree ( )

Destrutor.

O destrutor apaga também todos os nós criados pela estrutura.

Métodos

template<class T>

Node<T>* persistence::red_black_tree::RedBlackTree< T >::Active ( Node< T > * u )

Versão ativa de um nó.

Parâmetros

u	Um nó da ARN.

Retorna: Versão ativa de u.

Pré-Condição: u ou sua cópia são ativos.

template<class T>

void persistence::red_black_tree::RedBlackTree< T >::AddBlack	(	Node< T > *	y,
		bool	side
	)

Arruma violações causadas por remoção.

Parâmetros

y,side Nó da ARN e lado tal que os caminhos até links nulos que passam por y em direção à side tem um nó preto a menos que os outros.

Pré-Condição: y ou sua cópia são ativos.

Aviso: A função pode causar a cópia ou modificação de y e outros nós.

template<class T>

Node<T>* persistence::red_black_tree::RedBlackTree< T >::Child	(	Node< T > *	u,
		bool	side,
		int	version
	)		const

Retorna um filho de um nó em dada versão.

Parâmetros

u	Um nó da ARN cuja versão inclui `version`, ou seja, `version` ∈ `[u.version, u.copy.version - 1]`.
side	Lado do filho desejado.
version	Versão desejada.

Retorna: O filho side de u na versão version.

Anotações: Essa função é utilizada em operações de acesso.

template<class T>

Node<T>* persistence::red_black_tree::RedBlackTree< T >::Child	(	Node< T > *	u,
		bool	side
	)

Retorna um filho de um nó na versão atual.

Parâmetros

u	Um nó da ARN.
side	Lado desejado do filho.

Pré-Condição: u ou sua cópia são ativos.

Veja também: Child

template<class T>

Node<T>* persistence::red_black_tree::RedBlackTree< T >::Copy ( Node< T > * u )

Copia um nó.

Cria uma cópia de u com as versões mais atuais de seus campos. Usado por Modify.

Parâmetros

u	Um nó da ARN.

Retorna: Uma cópia de u.

Pré-Condição: u deve ser um nó ativo.

Aviso: Esta modificação pode causar a cópia ou modificação dos ancestrais de u.

template<class T>

int persistence::red_black_tree::RedBlackTree< T >::current ( )

inline

Versão atual da ARN.

Retorna: Quantas operações de modificação já foram realizadas na estrutura.

template<class T>

const T* persistence::red_black_tree::RedBlackTree< T >::Find	(	const T &	x,
		int	version
	)

Busca por um valor em dada versão da ARN.

Parâmetros

x	Valor a ser buscado.
version	Versão da árvore na qual o valor deve ser buscado.

Retorna: Um ponteiro para o valor de algum nó com valor val na árvore, ou nulo se tal nó não existir.

template<class T>

void persistence::red_black_tree::RedBlackTree< T >::Insert ( const T & value )

Inserção de valor na ARN.

Cria um novo nó com valor val e adiciona este nó à versão mais recente da árvore.

Parâmetros

value Valor a ser adicionado.

template<class T>

Node<T>* persistence::red_black_tree::RedBlackTree< T >::MinElement ( Node< T > * u )

Menor elemento em uma subárvore na versão atual.

Parâmetros

u	Um nó da ARN.

Retorna: Menor elemento na subárvore de u, na versão atual.

Pré-Condição: u ou sua cópia são ativos.

template<class T>

void persistence::red_black_tree::RedBlackTree< T >::Modify	(	Node< T > *	u,
		bool	side,
		Node< T > *	v
	)

Modificação de filho de um nó.

Modifica o lado side de u para apontar para v.

Parâmetros

u	Um nó da ARN.
side	Lado do nó a ser modificado.
v	Novo valor para ponteiro.

Pré-Condição: u ou sua cópia são ativos.; v ou sua cópia são ativos.

Anotações: Não é possível inferir side a partir de u e v apenas comparando seus valores, já que pode ser nulo ou a árvore pode ter muitos nós com o mesmo valor.

Aviso: Esta modificação pode causar a cópia ou modificação de u e seus ancestrais.

template<class T>

const T* persistence::red_black_tree::RedBlackTree< T >::Remove ( const T & value )

Remoção de valor na ARN.

Busca por algum nó com valor igual val e remove este nó da versão mais recente da árvore. Retorna um ponteiro para o valor do nó removido, ou nulo se não existe tal nó.

Parâmetros

value Valor a ser removido.

template<class T>

void persistence::red_black_tree::RedBlackTree< T >::Rotate	(	Node< T > *	u,
		bool	side
	)

Rotaciona um nó.

Rotaciona u de forma que seu filho de lado side tome seu lugar, enquanto mantém as propriedades de uma árvore binária.

Parâmetros

u	Um nó da ARN.
side	Lado da rotação.

Pré-Condição: u ou sua cópia são ativos.; u deve ter um filho de lado side na versão mais atual.

Aviso: Esta rotação pode causar a cópia ou modificação de u, seu filho de lado side e de seus ancestrais.; A rotação não mantém as propriedades rubro-negras.

template<class T>

void persistence::red_black_tree::RedBlackTree< T >::Transplant	(	Node< T > *	u,
		Node< T > *	x
	)

Subsitui um nó.

A subárvore de u é substituida pela subárvore de x, isto é, x é desconectado de seu pai, se existir, e então troca-se o filho do pai de u de u para x.

Parâmetros

u,x	Nós da ARN.

Pré-Condição: u ou sua cópia são ativos.; x ou sua cópia são ativos.

Aviso: A substituição pode causar a cópia ou modificação de u, x, e seus ancestrais.

Campos

template<class T>

std::vector<Node<T>*> persistence::red_black_tree::RedBlackTree< T >::roots

Raízes de todas as versões.

roots[i] é a raiz da ARN em sua versão i. O vetor é inicializado com apenas um elemento com valor nulo, pois a estrutura começa em sua versão 0, vazia.

A documentação para esta classe foi gerada a partir do seguinte arquivo:

/home/travis/build/yancouto/mestrado/source/persistence/RedBlackTree.hpp

Descrição Detalhada

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

Biblioteca Pública

Campos, Construção e Acesso

Funções Auxiliares de Modificação

Construtores & Destrutores

Métodos

Campos

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