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

void	splay (const Key &key)

	GenTdSplayTreeRk (Compare &__cmp)
	Constructor.

	GenTdSplayTreeRk (Compare &&__cmp)

void	swap (GenTdSplayTreeRk &tree)

virtual	~GenTdSplayTreeRk ()
	Destructor.

Node *	insert (Node *p)

Node *	insert_dup (Node *p)

Node *	search (const Key &key)

Node *	search_or_insert (Node *p)

Node *	remove (const Key &key)

Node *&	getRoot ()
	Get the top down splay tree's root.

bool	verify () const

size_t	size () const
	Retorna la cantidad de nodos que contiene el treap.

bool	is_empty () const
	Retorna true si el treap está vacío.

std::pair< int, Node * >	position (const Key &key)

std::pair< int, Node * >	find_position (const Key &key)

Node *	select (const size_t &i)

Documentación de las funciones miembro

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

std::pair<int, Node*> GenTdSplayTreeRk< NodeType, Key, Compare >::find_position ( const Key & key )

inline

Retorna la posición infija (ordenada) de la clave key.

find_position(key) busca en el árbo splay extendido la clave key (lo cual toma tiempo $O(\lg n)$ ) y retorna la posición infija del nodo que contiene la clave junto con el nodo. En caso de que la clave no esté en el árbol, position(key) retorna la posición donde debería estar si key perteneciese al árbol.

El valor de retorno es un pair<int,Node*>. El campo first es la posición infija y second el nodo.

Si key no se encuentra en el árbol, entonces se pueden distinguir tres casos:

Si key es menor que la mínima clave del árbol, entonces first -1 y second es el nodo contentivo de la clave mínima.
Si key es mayor que la máxima clave del árbol, entonces first es COUNT(r) (número de nodos del árbol) y second es el nodo contentivo de la clave máxima.
En cualquier otro caso, first es la posición que tendría la clave key en árbol y second nodo p es una clave inmediatamente adyancente a key. Note que second puede tener una clave menor o mayor, pero se garantiza que es inmediatamente continua a key.

Parámetros

[in] key clave a buscar y a determinar posición infija.

Devuelve: un par conteniendo la posición infija de la clave key dentro del conjunto ordenado junto con el nodo si la clave se encuentra en el mapeo; de lo contrarion, se retorna -1 y el nodo es indeterminado.

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

Compare& GenTdSplayTreeRk< 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< class > class NodeType, typename Key, class Compare>

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

inline

Inserts a node in a top down splay tree.

Devuelve: a pointer to the inserted node if node is not found in tree; NULL otherwise.

Parámetros

p	a pointer to the node to be inserted

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

std::pair<int, Node*> GenTdSplayTreeRk< NodeType, Key, Compare >::position ( const Key & key )

inline

Retorna la posición infija (ordenada) de la clave key.

position(key) busca en el árbol splay extendido la clave key (lo cual toma tiempo $O(\lg n)$ ) y retorna la posición infija del nodo que contiene la clave.

Parámetros

[in] key clave a buscar y a determinar posición infija.

Devuelve: un par conteniendo la posición infija de la clave key dentro del conjunto ordenado junto con el nodo si la clave se encuentra en el mapeo; de lo contrarion, se retorna -1 y el nodo es indeterminado.

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

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

inline

Remove a key from a top down splay tree.

Searches a key in a top down splay tree and remove the containing the key if this is found.

Devuelve: a pointer to node containing the removed key.

Parámetros

key to search

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

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

inline

Searches a key in a top down splay tree.

Devuelve: a pointer to the node containing the key if the key is found; NULL otherwise.

Parámetros

key	key to search

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

Node* GenTdSplayTreeRk< NodeType, Key, Compare >::select ( const size_t & i )

inline

Retorna el nodo cuya posición infija en el treap extendido es i.

select(i) retorna el nodo del árbol splay extendido cuya posición infija es i.

Parámetros

[in] i posición infija a seleccionar.

Devuelve: puntero al nodo correspondiente a la posición infija i.

Excepciones

out_of_range si i es mayor o igual que la cantidad de nodos que contiene el árbol.

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

void GenTdSplayTreeRk< NodeType, Key, Compare >::splay ( const Key & key )

inline

search key within tree and splay that node, if not found it return Node::NullPtr

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

tpl_splay_treeRk.H

Tipos públicos

Métodos públicos

Documentación de las funciones miembro