Aleph-w  1.9
General library for algorithms and data structures
Public Types | Public Member Functions | List of all members
Aleph::Rb_Tree< Key, Compare > Struct Template Reference
Trees

#include <tpl_rb_tree.H>

+ Inheritance diagram for Aleph::Rb_Tree< Key, Compare >:
+ Collaboration diagram for Aleph::Rb_Tree< Key, Compare >:

Public Types

using Base = Gen_Rb_Tree< RbNode, Key, Compare >
 
typedef RbNode< 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 ()
 
void swap (Gen_Rb_Tree &tree)
 
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<typename Key, class Compare = Aleph::less<Key>>
struct Aleph::Rb_Tree< Key, Compare >

Árbol binario de búsqueda rojo-negro con nodos sin destructor virtual.

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 maneja nodos sin destructor virtual.

Parameters
Keyel tipo de clave que albergan los nodos del árbol.
Compareclase de comparación entre las claves.
See also
Rb_Tree_Vtl

Member Function Documentation

◆ get_compare()

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

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

◆ insert()

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

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

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

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

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

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

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

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

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

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]pel 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()

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

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

Parameters
[in]treeel treap a intercambiar con this
The documentation for this struct was generated from the following file:
Leandro Rabindranath León