Referencia de la Clase Arbol_Rojinegro< T >

Clase Arbol_RojiNegro: -Un árbol rojo-negro resulta de la representación de un árbol 2-3-4 mediante un árbol binario. Más...

#include <Arbol_Rojinegro.h>

Diagrama de herencias de Arbol_Rojinegro< T >

Lista de todos los miembros.

Tipos públicos
typedef T	value_type
	Nombre estándar del tipo de elemento contenido.
Métodos públicos
	Arbol_Rojinegro ()
	Arbol_Rojinegro (Bin_Tree &o)
	Constructor.
	Arbol_Rojinegro (const T &val)
	~Arbol_Rojinegro ()
	Constructor a partir de un valor.
bool	isEmpty () const
	Retorna "true" si el sub-árbol está vacío.
unsigned	count () const
unsigned	countChildren () const
unsigned	size () const
	Usa count() para retornar la cantidad de valores almacenados en el sub-árbol.
bool	ok () const
void	erase ()
	Elimina el árbol y sus descendientes.
void	copy (const Bin_Tree &other)
Bin_Tree &	copyDeep (const Bin_Tree &other)
void	swap (Bin_Tree &other)
void	move (Bin_Tree &other)
void	changeRoot (const value_type &d)
void	changeChild (unsigned n, const value_type &d)
void	makeLeftChild (Bin_Tree &T)
void	makeRightChild (Bin_Tree &T)
value_type &	dato () const
	Valor almacenado en la raíz del sub-árbol.
value_type &	operator * () const
	Valor almacenado en la raíz del sub-árbol.
value_type *	operator-> () const
	Puntero al valor almacenado en la raíz del sub-árbol.
bool	equals (const Bin_Tree &o) const
	¿¿¿ (*this==o) ???
bool	same (const Bin_Tree &o) const
	Retorna true si "o" comparte la raíz con "*this".
Bin_Tree	root () const
	Raíz del sub-árbol.
Bin_Tree	padre () const
	Acceso al padre.
Bin_Tree	left () const
	Acceso al hijo izquierdo.
Bin_Tree	right () const
	Acceso al hijo derecho.
Bin_Tree	child (int i) const
	Acceso al i-ésimo hijo del árbol.
bool	isLeaf () const
	Retorna "true" si el árbol es una hoja.
bool	isRoot () const
	Retorna "true" si el árbol no tiene padre.
unsigned	refs () const
	Cantidad de referencias de la raíz del árbol.
Atributos públicos
bool	color
	Destructor.
Amigas
bool	operator== (const Bin_Tree< T > &p, const Bin_Tree< T > &q)
	¿¿¿ (p == q) ???
bool	operator!= (const Bin_Tree< T > &p, const Bin_Tree< T > &q)
	¿¿¿ (p != q) ???

---

Descripción detallada

template<class T>
class Arbol_Rojinegro< T >

Clase Arbol_RojiNegro: -Un árbol rojo-negro resulta de la representación de un árbol 2-3-4 mediante un árbol binario.

-Cada nodo de un árbol rojo negro contiene la siguiente información: color, valor, hijo izquierdo, hijo derecho y padre. -Si un hijo o el padre de un nodo no existe, el apuntador correspondiente contiene el valor NULL, el cual consideraremos como un nodo cuyo color es negro. -En lo sucesivo nos referiremos a los nodos distintos a las hojas (NULL) como nodos internos del árbol y a las hojas y al padre de la raíz como nodos externos.

Todo árbol Rojinegro satisface las siguientes propiedades: -Todo nodo es rojo o negro -La raíz es negra -Toda hoja (NULL) es negra. -Si un nodo es rojo, entonces sus dos hijos son negros. -Para cada nodo, todas las rutas de un nodo a las hojas (NULLs) contienen el mismo número de nodos negros. El número de nodos negros en esta ruta se conoce como altura-negra del nodo.

Definición en la línea 26 del archivo Arbol_Rojinegro.h.

---

Documentación de los 'Tipos Definidos' miembros de la clase

typedef T Bin_Tree< T >::value_type [inherited]

Nombre estándar del tipo de elemento contenido.

Definición en la línea 57 del archivo Bin_Tree.h.

---

Documentación del constructor y destructor

template<class T>

Arbol_Rojinegro< T >::Arbol_Rojinegro

(

)

[inline]

Definición en la línea 28 del archivo Arbol_Rojinegro.h.

template<class T>

Arbol_Rojinegro< T >::Arbol_Rojinegro

(

Bin_Tree &

o

)

[inline]

Constructor.

Definición en la línea 29 del archivo Arbol_Rojinegro.h.

template<class T>

Arbol_Rojinegro< T >::Arbol_Rojinegro

(

const T &

val

)

[inline]

Definición en la línea 30 del archivo Arbol_Rojinegro.h.

template<class T>

Arbol_Rojinegro< T >::~Arbol_Rojinegro

(

)

[inline]

Constructor a partir de un valor.

Definición en la línea 31 del archivo Arbol_Rojinegro.h.

---

Documentación de las funciones miembro

bool Bin_Tree< T >::isEmpty

(

)

const [inline, inherited]

Retorna "true" si el sub-árbol está vacío.

Definición en la línea 74 del archivo Bin_Tree.h.

unsigned Bin_Tree< T >::count

(

)

const [inherited]

Retorna la cantidad de valores almacenados en el sub-árbol.

• Calcula el número de sub-árboles no vacíos del árbol.

  Complejidad:

  O( count() ) ==> tiempo
  O( height() ) ==> espacio.

  Ver también:

  http://www.di-mare.com/adolfo/binder/c05.htm#sc03

unsigned Bin_Tree< T >::countChildren

(

)

const [inherited]

Retorna la cantidad de hijos del árbol.

Complejidad:

O( 1 )

unsigned Bin_Tree< T >::size

(

)

const [inline, inherited]

Usa count() para retornar la cantidad de valores almacenados en el sub-árbol.

Definición en la línea 78 del archivo Bin_Tree.h.

bool Bin_Tree< T >::ok

(

)

const [inline, inherited]

Definición en la línea 81 del archivo Bin_Tree.h.

void Bin_Tree< T >::erase

(

)

[inline, inherited]

Elimina el árbol y sus descendientes.

• T.left().erase(); // No cambia "T" porque el que cambia es "T.left()"
• T.makeLeftChild( Bin_Tree<E>() ); // borra el hijo izquierdo
• T.makeRightChild( Bin_Tree<E>() ); // borra el hijo derecho

  Complejidad:

  O( count() ) ==> tiempo
  O( height() ) ==> espacio.

  Ver también:

  http://www.di-mare.com/adolfo/binder/c04.htm#sc03

Definición en la línea 96 del archivo Bin_Tree.h.

void Bin_Tree< T >::copy

(

const Bin_Tree< T > &

other

)

[inline, inherited]

Copia superficial desde "o".

• El valor anterior de "*this" se pierde.

  Complejidad:

  O( 1 ).

  Devuelve:

  *this.

  Ver también:

  http://www.di-mare.com/adolfo/binder/c04.htm#sc05

Definición en la línea 104 del archivo Bin_Tree.h.

Bin_Tree& Bin_Tree< T >::copyDeep

(

const Bin_Tree< T > &

other

)

[inherited]

Copia profunda de "other".

• Copia todo el valor de "other" sobre "*this", de forma que el nuevo valor de "*this" sea un duplicado exacto del valor de "other".
• El valor anterior de "*this" se pierde.
• El objeto "other" mantiene su valor anterior.
• Luego de la copia, cuando el valor de "other" cambia, el de "*this" no cambiará, y viceversa, pues la copia es una copia profunda; no es superficial.
• Si "*this" es "other" entonces su valor no cambia.
• Después de esta operación siempre ocurre que *this == other .

  Complejidad:

  O( count() ) + O( other.count() ).

  Devuelve:

  *this.

  Ver también:

  http://www.di-mare.com/adolfo/binder/c04.htm#sc05

void Bin_Tree< T >::swap

(

Bin_Tree< T > &

other

)

[inherited]

Intercambia los valores de "*this" y "o".

• Debido a que algunos métodos retornan copias del valor de "*this" en lugar de una referencia, como ocurre con Bin_Tree::child(), a veces swap() no tiene el resultado esperado por el programador.
• Por ejemplo, si se invoca T.child(i). swap( T.child(j) ) el resultado no es intercambiar los hijos, sino más bien intercambiar los valores de los sub-árboles temporales T.child(i) y T.child(j). La forma correcta de intercambiar hijos es usar makeLeftChild() y/o makeRightChild().

Complejidad:

O( 1 ).

Devuelve:

*this.

Ver también:

http://www.di-mare.com/adolfo/binder/c04.htm#sc08

void Bin_Tree< T >::move

(

Bin_Tree< T > &

other

)

[inherited]

Traslada a "*this" el valor de "other".

• El valor anterior de "*this" se pierde.
• El nuevo valor de "*this" es el que "other" tuvo.
• "other" queda en el estado en que lo dejaría other.erase().
• Si "*this" es "other" entonces su valor no cambia.
• En general, después de esta operación casi nunca ocurre que this->equal(other) es "true".

  Complejidad:

  O( count() )

  Devuelve:

  *this.

  Ver también:

  http://www.di-mare.com/adolfo/binder/c04.htm#sc07

void Bin_Tree< T >::changeRoot

(

const value_type &

d

)

[inherited]

Sustituye por "d" el valor almacenado en la raíz del árbol.

• Si el árbol está vacío, le agrega su raíz.

void Bin_Tree< T >::changeChild	(	unsigned	n,
		const value_type &	d
	)			[inherited]

Sustituye por "d" el valor almacenado en el hijo número "n" del árbol.

• Si no existe el hijo número "n", lo agrega como una hoja con valor "d".
• Si ya existe el hijo número "n", le sustituye su valor por "d".
• Si "n" no es uno de {0,1} no hace nada.

void Bin_Tree< T >::makeLeftChild

(

Bin_Tree< T > &

T

)

[inherited]

Pone al árbol "T" como sub-árbol izquierdo de "*this".

• Elimina el sub-árbol izquierdo de "*this" si "T" está vacío.

  Precondición:

  ! isEmpty()

void Bin_Tree< T >::makeRightChild

(

Bin_Tree< T > &

T

)

[inherited]

Pone al árbol "T" como sub-árbol derecho de "*this".

• Elimina el sub-árbol derecho de "*this" si "T" está vacío.

  Precondición:

  ! isEmpty()

value_type& Bin_Tree< T >::dato

(

)

const [inline, inherited]

Valor almacenado en la raíz del sub-árbol.

Definición en la línea 125 del archivo Bin_Tree.h.

value_type& Bin_Tree< T >::operator *

(

)

const [inline, inherited]

Valor almacenado en la raíz del sub-árbol.

Definición en la línea 127 del archivo Bin_Tree.h.

value_type* Bin_Tree< T >::operator->

(

)

const [inline, inherited]

Puntero al valor almacenado en la raíz del sub-árbol.

Definición en la línea 129 del archivo Bin_Tree.h.

bool Bin_Tree< T >::equals

(

const Bin_Tree< T > &

o

)

const [inline, inherited]

¿¿¿ (*this==o) ???

Definición en la línea 139 del archivo Bin_Tree.h.

bool Bin_Tree< T >::same

(

const Bin_Tree< T > &

o

)

const [inline, inherited]

Retorna true si "o" comparte la raíz con "*this".

Definición en la línea 141 del archivo Bin_Tree.h.

Bin_Tree Bin_Tree< T >::root

(

)

const [inline, inherited]

Raíz del sub-árbol.

Definición en la línea 147 del archivo Bin_Tree.h.

Bin_Tree Bin_Tree< T >::padre

(

)

const [inline, inherited]

Acceso al padre.

• Si el sub-árbol no tiene padre retorna el árbol vacío.

Definición en la línea 150 del archivo Bin_Tree.h.

Bin_Tree Bin_Tree< T >::left

(

)

const [inline, inherited]

Acceso al hijo izquierdo.

• Si el sub-árbol no tiene hijo izquierdo retorna el árbol vacío.

Definición en la línea 156 del archivo Bin_Tree.h.

Bin_Tree Bin_Tree< T >::right

(

)

const [inline, inherited]

Acceso al hijo derecho.

• Si el sub-árbol no tiene hijo derecho retorna el árbol vacío.

Definición en la línea 163 del archivo Bin_Tree.h.

Bin_Tree Bin_Tree< T >::child

(

int

i

)

const [inline, inherited]

Acceso al i-ésimo hijo del árbol.

• Si el sub-árbol no tiene es hijo retorna el árbol vacío.
• ( i == 0 ) ==> Hijo izquierdo.
• ( i == 1 ) ==> Hijo derecho.

Definición en la línea 172 del archivo Bin_Tree.h.

bool Bin_Tree< T >::isLeaf

(

)

const [inline, inherited]

Retorna "true" si el árbol es una hoja.

• Retorna "false" para un árbol vacío.

Definición en la línea 185 del archivo Bin_Tree.h.

bool Bin_Tree< T >::isRoot

(

)

const [inline, inherited]

Retorna "true" si el árbol no tiene padre.

• Retorna "false" para un árbol vacío.

Definición en la línea 190 del archivo Bin_Tree.h.

unsigned Bin_Tree< T >::refs

(

)

const [inline, inherited]

Cantidad de referencias de la raíz del árbol.

Definición en la línea 192 del archivo Bin_Tree.h.

---

Documentación de las funciones relacionadas y clases amigas

bool operator==	(	const Bin_Tree< T > &	p,
		const Bin_Tree< T > &	q
	)			[friend, inherited]

¿¿¿ (p == q) ???

Definición en la línea 330 del archivo Bin_Tree.h.

bool operator!=	(	const Bin_Tree< T > &	p,
		const Bin_Tree< T > &	q
	)			[friend, inherited]

¿¿¿ (p != q) ???

Definición en la línea 333 del archivo Bin_Tree.h.

---

Documentación de los datos miembro

template<class T>

bool Arbol_Rojinegro< T >::color

Destructor.

Definición en la línea 32 del archivo Arbol_Rojinegro.h.

---

La documentación para esta clase fué generada a partir del siguiente archivo:

• Arbol_Rojinegro.h

---