Share via

Clase CRBTree

  • Artículo

Esta clase proporciona métodos para crear y usar un árbol Rojo-Negro.

Sintaxis

template <typename K,
          typename V,
          class KTraits = CElementTraits<K>,
          class VTraits = CElementTraits<V>>
class CRBTree

Parámetros

K
Tipo de elemento clave.

V
Tipo de elemento de valor.

KTraits
Código usado para copiar o mover elementos de clave. Consulte CElementTraits (clase) para más información.

VTraits
Código usado para copiar o mover elementos de valor.

Miembros

Definiciones de tipos públicas

Nombre Descripción
CRBTree::KINARGTYPE Tipo usado cuando se pasa una clave como argumento de entrada.
CRBTree::KOUTARGTYPE Tipo utilizado cuando se devuelve una clave como argumento de salida.
CRBTree::VINARGTYPE Tipo que se usa cuando se pasa un valor como argumento de entrada.
CRBTree::VOUTARGTYPE Tipo que se usa cuando se pasa un valor como argumento de salida.

Clases públicas

Nombre Descripción
CRBTree::CPair Class Clase que contiene los elementos de clave y valor.

Constructores públicos

Nombre Descripción
CRBTree::~CRBTree El destructor .

Métodos públicos

Nombre Descripción
CRBTree::FindFirstKeyAfter Llame a este método para buscar la posición del elemento que usa la siguiente clave disponible.
CRBTree::GetAt Llame a este método para obtener el elemento en una posición determinada del árbol.
CRBTree::GetCount Llame a este método para obtener el número de elementos del árbol.
CRBTree::GetHeadPosition Llame a este método para obtener el valor de posición del elemento en la cabeza del árbol.
CRBTree::GetKeyAt Llame a este método para obtener la clave de una posición determinada en el árbol.
CRBTree::GetNext Llame a este método para obtener un puntero a un elemento almacenado en el objeto CRBTree y avanzar la posición al siguiente elemento.
CRBTree::GetNextAssoc Llame a este método para obtener la clave y el valor de un elemento almacenado en la asignación y avanzar la posición al siguiente elemento.
CRBTree::GetNextKey Llame a este método para obtener la clave de un elemento almacenado en el árbol y avanzar la posición al siguiente elemento.
CRBTree::GetNextValue Llame a este método para obtener el valor de un elemento almacenado en el árbol y avanzar la posición al siguiente elemento.
CRBTree::GetPrev Llame a este método para obtener un puntero a un elemento almacenado en el objeto CRBTree y después actualice la posición al elemento anterior.
CRBTree::GetTailPosition Llame a este método para obtener el valor de posición del elemento en la cola del árbol.
CRBTree::GetValueAt Llame a este método para recuperar el valor almacenado en una posición determinada del objeto CRBTree.
CRBTree::IsEmpty Llame a este método para probar un objeto de árbol vacío.
CRBTree::RemoveAll Llame a este método para quitar todos los elementos del objeto CRBTree.
CRBTree::RemoveAt Llame a este método para quitar el elemento en la posición especificada del objeto CRBTree.
CRBTree::SetValueAt Llame a este método para cambiar el valor almacenado en una posición determinada del objeto CRBTree.

Comentarios

Un árbol Rojo-Negro es un árbol de búsqueda binario que usa un bit adicional de información por nodo para asegurarse de que sigue siendo "equilibrado", es decir, de que el alto del árbol no crece de forma desproporcionada y afecta al rendimiento.

Esta clase de plantilla está diseñada para usarse en CRBMap y CRBMultiMap. La mayor parte de los métodos que componen estas clases derivadas se proporcionan mediante CRBTree.

Para obtener una explicación más completa de las distintas clases de colección y sus características y características de rendimiento, consulte Clases de colección de ATL.

Requisitos

Encabezado: atlcoll.h

Clase CRBTree::CPair

Clase que contiene los elementos de clave y valor.

class CPair : public __POSITION

Comentarios

Los métodos CRBTree::GetAt, CRBTree::GetNext y CRBTree::GetPrev usan esta clase para tener acceso a los elementos de clave y valor almacenados en la estructura de árbol.

Los miembros son los siguientes:

Miembro de datos Descripción
m_key Miembro de datos que almacena el elemento clave.
m_value Miembro de datos que almacena el elemento value.

CRBTree::~CRBTree

El destructor .

~CRBTree() throw();

Comentarios

Libera los recursos asignados. Llama a CRBTree::RemoveAll para eliminar todos los elementos.

CRBTree::FindFirstKeyAfter

Llame a este método para buscar la posición del elemento que usa la siguiente clave disponible.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Parámetros

key
Valor de clave.

Valor devuelto

Devuelve el valor de posición del elemento que usa la siguiente clave disponible. Si no hay más elementos, se devuelve NULL.

Comentarios

Este método facilita el recorrido a través del árbol sin tener que calcular los valores de posición de antemano.

CRBTree::GetAt

Llame a este método para obtener el elemento en una posición determinada del árbol.

CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;

Parámetros

pos
Valor de la posición.

key
Variable que recibe la clave.

value
Variable que recibe el valor.

Valor devuelto

Los dos primeros formularios devuelven un puntero a CPair. El tercer formulario obtiene una clave y un valor para la posición especificada.

Comentarios

El valor de posición se puede determinar previamente con una llamada a un método como CRBTree::GetHeadPosition o CRBTree::GetTailPosition.

En las compilaciones de depuración, se producirá un error de aserción si pos es igual a NULL.

CRBTree::GetCount

Llame a este método para obtener el número de elementos del árbol.

size_t GetCount() const throw();

Valor devuelto

Devuelve el número de elementos (cada par clave-valor es un elemento) almacenado en el árbol.

CRBTree::GetHeadPosition

Llame a este método para obtener el valor de posición del elemento en la cabeza del árbol.

POSITION GetHeadPosition() const throw();

Valor devuelto

Devuelve el valor de posición del elemento en la cabeza del árbol.

Comentarios

El valor devuelto por GetHeadPosition se puede usar con métodos como CRBTree::GetKeyAt o CRBTree::GetNext para recorrer el árbol y recuperar valores.

CRBTree::GetKeyAt

Llame a este método para obtener la clave de una posición determinada en el árbol.

const K& GetKeyAt(POSITION pos) const throw();

Parámetros

pos
Valor de la posición.

Valor devuelto

Devuelve la clave almacenada en posición pos en el árbol.

Comentarios

Si pos no es un valor de posición válido, los resultados son impredecibles. En las compilaciones de depuración, se producirá un error de aserción si pos es igual a NULL.

CRBTree::GetNext

Llame a este método para obtener un puntero a un elemento almacenado en el objeto CRBTree y avanzar la posición al siguiente elemento.

const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();

Parámetros

pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valor devuelto

Devuelve un puntero al siguiente valor CPair del árbol.

Comentarios

El contador de posición pos se actualiza después de cada llamada. Si el elemento recuperado es el último del árbol, pos se establece en NULL.

CRBTree::GetNextAssoc

Llame a este método para obtener la clave y el valor de un elemento almacenado en la asignación y avanzar la posición al siguiente elemento.

void GetNextAssoc(
    POSITION& pos,
    KOUTARGTYPE key,
    VOUTARGTYPE value) const;

Parámetros

pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

key
Parámetro de plantilla que especifica el tipo de clave del árbol.

value
Parámetro de plantilla que especifica el tipo de valor del árbol.

Comentarios

El contador de posición pos se actualiza después de cada llamada. Si el elemento recuperado es el último del árbol, pos se establece en NULL.

CRBTree::GetNextKey

Llame a este método para obtener la clave de un elemento almacenado en el árbol y avanzar la posición al siguiente elemento.

const K& GetNextKey(POSITION& pos) const throw();

Parámetros

pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valor devuelto

Devuelve una referencia a la siguiente clave del árbol.

Comentarios

Actualiza el contador de posición actual, pos. Si no hay más entradas en el árbol, el contador de posición se establece en NULL.

CRBTree::GetNextValue

Llame a este método para obtener el valor de un elemento almacenado en el árbol y avanzar la posición al siguiente elemento.

const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();

Parámetros

pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valor devuelto

Devuelve una referencia al siguiente valor del árbol.

Comentarios

Actualiza el contador de posición actual, pos. Si no hay más entradas en el árbol, el contador de posición se establece en NULL.

CRBTree::GetPrev

Llame a este método para obtener un puntero a un elemento almacenado en el objeto CRBTree y después actualice la posición al elemento anterior.

const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();

Parámetros

pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valor devuelto

Devuelve un puntero al valor CPair anterior almacenado en el árbol.

Comentarios

Actualiza el contador de posición actual, pos. Si no hay más entradas en el árbol, el contador de posición se establece en NULL.

CRBTree::GetTailPosition

Llame a este método para obtener el valor de posición del elemento en la cola del árbol.

POSITION GetTailPosition() const throw();

Valor devuelto

Devuelve el valor de posición del elemento situado en la cola del árbol.

Comentarios

El valor devuelto por GetTailPosition se puede usar con métodos como CRBTree::GetKeyAt o CRBTree::GetPrev para recorrer el árbol y recuperar valores.

CRBTree::GetValueAt

Llame a este método para recuperar el valor almacenado en una posición determinada del objeto CRBTree.

const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();

Parámetros

pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Valor devuelto

Devuelve una referencia al valor almacenado en la posición especificada del objeto CRBTree.

CRBTree::IsEmpty

Llame a este método para probar un objeto de árbol vacío.

bool IsEmpty() const throw();

Valor devuelto

Devuelve TRUE si el árbol está vacío, FALSE de lo contrario.

CRBTree::KINARGTYPE

Tipo usado cuando se pasa una clave como argumento de entrada.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

Tipo utilizado cuando se devuelve una clave como argumento de salida.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

Llame a este método para quitar todos los elementos del objeto CRBTree.

void RemoveAll() throw();

Comentarios

Borra el objeto CRBTree, liberando la memoria usada para almacenar los elementos.

CRBTree::RemoveAt

Llame a este método para quitar el elemento en la posición especificada del objeto CRBTree.

void RemoveAt(POSITION pos) throw();

Parámetros

pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

Comentarios

Quita el par clave-valor almacenado en la posición especificada. La memoria usada para almacenar el elemento se libera. La posición a la que hace referencia pos no es válida y, mientras que el valor POSITION de cualquier otro elemento del árbol sigue siendo válido, no conservan necesariamente el mismo orden.

CRBTree::SetValueAt

Llame a este método para cambiar el valor almacenado en una posición determinada del objeto CRBTree.

void SetValueAt(POSITION pos, VINARGTYPE value);

Parámetros

pos
Contador de posición, devuelto por una llamada anterior a métodos como CRBTree::GetHeadPosition o CRBTree::FindFirstKeyAfter.

value
Valor del objeto que se va a agregar a CRBTree.

Comentarios

Cambia el elemento de valor almacenado en la posición especificada del objeto CRBTree.

CRBTree::VINARGTYPE

Tipo que se usa cuando se pasa un valor como argumento de entrada.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

Tipo que se usa cuando se pasa un valor como argumento de salida.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Consulte también

Información general sobre la clase