Aleph::Gen_Rb_Tree< NodeType, Key, Compare > Class Template Reference

#include <tpl_rb_tree.H>

Classes
struct	Iterator

Public Types
typedef NodeType< Key >	Node
typedef Key	key_type
	El tipo de clave que contiene el nodo.

Public Member Functions
Compare &	key_comp ()
	Retorna una referencia al criterio de comparación.
Compare &	get_compare ()
	Gen_Rb_Tree (Compare __cmp=Compare())
	Instancia un árbol rojo-negro.
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 () const
Node *	remove (const Key &key)

Detailed Description

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 y sus operaciones de modificación acotadas en tiempo por 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.

Parameters

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.

See also

Rb_Tree Rb_Tree_Vtl

Member Function Documentation

get_compare()

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

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

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

insert()

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 nullptr.

insert_dup()

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 nullptr.

remove()

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 nullptr.

search()

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; nullptr de lo contrario.

search_or_insert()

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.

Parameters

[in]

p

el nodo a buscar o insertar.

Returns

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).

swap()

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).

Parameters

[in]

tree

el treap a intercambiar con this

---

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

• tpl_rb_tree.H