#include <tpl_rb_tree.H>

Tipos públicos
typedef NodeType< Key >	Node

typedef Key	key_type
	El tipo de clave que contiene el nodo.

Métodos públicos
Compare &	key_comp ()
	Retorna una referencia al criterio de comparación.

Compare &	get_compare ()

	Gen_Rb_Tree (Compare &&__cmp)
	Instancia un árbol rojo-negro.

	Gen_Rb_Tree (Compare &__cmp)

void	swap (Gen_Rb_Tree &tree)

virtual	~Gen_Rb_Tree ()
	Destruye un árbol rojo-negro.

Node *	search (const Key &key)

Node *&	getRoot ()
	Obtiene un puntero a la raíz del árbol.

Node *	insert (Node *p)

Node *	search_or_insert (Node *p)

Node *	insert_dup (Node *p)

bool	verify ()

Node *	remove (const Key &key)

Descripción detallada

template<template< typename > class NodeType, typename Key, class Compare>
class Aleph::Gen_Rb_Tree< NodeType, Key, Compare >

Árbol binario de búsqueda rojo-negro.

Un árbol binario de búsqueda rojo negro es un árbol binario de búsqueda cuya altura está acotada a $O(\lg n)$ y sus operaciones de modificación acotadas en tiempo por $O(\lg n)$ nodos inspeccionados.

Esta clase es genérica en el sentido de que maneja nodos con o sin destructor virtual. No está destinada a usarse normalmente. En su lugar, use las clases derivadas Rb_Tree o Rb_Tree_Vtl.

Parámetros

NodeType	el tipo de nodo entre RbNode y RbNodeVtl (no están documentados).
Key	el tipo de clave que albergan los nodos del árbol.
Compare	clase de comparación entre las claves.

Ver también: Rb_Tree Rb_Tree_Vtl

Documentación de las funciones miembro

template<template< typename > class NodeType, typename Key, class Compare>

Compare& Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::get_compare ( )

inline

Esta es una función miembro sobrecargada que se suministra por conveniencia. Difiere de la anterior función solamente en los argumentos que acepta.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert ( Node * p )

inline

Inserta el nodo p en el árbol rojo-negro. Si la clave de p no está contenida en el árbol, entonces el nodo es insertado y se retorna el puntero a p. De lo contrario no ocurre la inserción y se retorna NULL.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::insert_dup ( Node * p )

inline

Inserta el nodo p en el árbol rojo-negro. Si la clave de p no está contenida en el árbol, entonces el nodo es insertado y se retorna el puntero a p. De lo contrario no ocurre la inserción y se retorna NULL.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::remove ( const Key & key )

inline

Elimina el nodo contentivo de la clave key. Si la clave se encuentra en el árbol, entonces se elimina el nodo que la contiene y se retorna su dirección. De lo contrario se retorna NULL.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search ( const Key & key )

inline

Busca un nodo con clave key. Retorna un puntero al nodo contentivo de key si éste se encuentra en el árbol; NULL de lo contrario.

template<template< typename > class NodeType, typename Key, class Compare>

Node* Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::search_or_insert ( Node * p )

inline

Busca la clave de p en el árbol rojo negro o lo inserta en caso de no encontrarse.

search_or_insert(p) busca en el árbol rojo-negro un nodo cuya clave sea KEY(p). Si la clave se encuentra, entonces se rerona un puntero al nodo que la alberga. De lo contrario se inserta p en el árbol binario de búsqueda this.

Parámetros

[in] p el nodo a buscar o insertar.

Devuelve: puntero al nodo insertado si la clave de p no está contenida dentro del árbol; De lo contrario, se retorna un puntero al nodo dentro del árbol que contiene a KEY(p).

template<template< typename > class NodeType, typename Key, class Compare>

void Aleph::Gen_Rb_Tree< NodeType, Key, Compare >::swap ( Gen_Rb_Tree< NodeType, Key, Compare > & tree )

inline

Intercambia todos los elementos del treap this con el treap tree en tiempo contante (y extremadamente rápido).

Parámetros

[in] tree el treap a intercambiar con this

La documentación para esta clase fue generada a partir del siguiente fichero:

tpl_rb_tree.H

Tipos públicos

Métodos públicos

Descripción detallada

template<template< typename > class NodeType, typename Key, class Compare> class Aleph::Gen_Rb_Tree< NodeType, Key, Compare >

Documentación de las funciones miembro

template<template< typename > class NodeType, typename Key, class Compare>
class Aleph::Gen_Rb_Tree< NodeType, Key, Compare >