ÁRBOL DE BÚSQUEDA ALEATORIZADO – TREAP

Treap es una estructura muy usada por su eficiencia y facilidad de codificación. Un treap consiste en introducir un número aleatorio en cada nodo. El número aleatorio será la prioridad del nodo. Las claves y las prioridades deben ser diferentes y pertenecer a un universo totalmente ordenado. En el árbol, las claves están almacenadas según un árbol binario de búsqueda, y las prioridades según una cola de prioridad. Por esta razón a la estructura se la denomina treaps que es un acrónimo de trees y heaps.

Como se dijo anteriormente un treap es la unión de arboles binarios con heaps, por tanto tienen que cumplir con las propiedades de ambos es decir:

Propiedad de Árbol Binario

Dada un nodo raíz X:

  • Los nodos ubicados a la izquierda del nodo X deben tener una clave menor que X
  • Los nodos ubicados a la derecha del nodo X deben tener una clave mayor que X.

Clave( hijo izquierda) < Clave(actual) > Clave(hijo derecha)

Propiedad de Heap:

Si tengo un Min-Heap: El nodo con prioridad mínima debe estar en la raíz, con ello queremos decir:

Prioridad (hijo) >= Prioridad (padre)

Si tengo un Max-Heap: El nodo con prioridad máxima debe estar en la raíz, con ello queremos decir:

Prioridad (padre) >= Prioridad (hijo)

Por tanto para definir nuestra estructura quedaría con los siguientes campos:

struct Node{
    int key , priority;            //clave y prioridad de un nodo
    Node* left , *right;           //subarbol izquierdo y derecho
    Node( int k ): key( k ) , priority( rand() ), left( NULL ) , right( NULL ){}
};

La prioridad no se ingresa pues posee un valor aleatorio.

1. Operaciones:

1.1 Búsqueda

La búsqueda se realiza igual que en un árbol binario, partiendo de la raíz pregunto si esta a la izquierda o derecha.

Node* search( Node *root , int key ){
    if( root == NULL ) return NULL;
    if( key < root -> key ) return search( root -> left , key );
    if( key > root -> key ) return search( root -> right , key );
    return root;
}

Para mayor información sobre la búsqueda revisar BST( Arbol de Busqueda Binario)

1.2 Inserción

La inserción puede ser por medio de rotaciones al igual que un AVL o RojiNegro, pero con rotaciones simples no muy complejas. Adicionalmente el Treap posee la operación de separación de un árbol en 2 arboles izquierdo y derecho dado un elemento a insertar. Mostraré ambas implementaciones

1.2.1 Inserción por medio de Rotaciones

Antes de empezar a explicar este tipo de inserción es necesario entender las rotaciones que se realizaran, una vez entendidas se procederá a explicar la inserción con un ejemplo y código fuente.

1.2.1.1 Rotaciones: Las rotaciones que se realizaran serán, rotación al a derecha y rotación a la izquierda se explicara paso a paso como se realizan las rotaciones.

a. Rotación a la derecha

Tengamos la siguiente imagen, la izquierda será el árbol inicial y la derecha será el árbol luego de rotarlo:

Root es la raíz que se pasara como argumento y Pivot será la nueva raíz luego de rotar, este caso se puede dar si por ejemplo tenemos un max-Heap donde el Nodo Root posee una prioridad menor que el Nodo Pivot. Como es max-Heap el nodo raíz debe tener el mayor valor.

Node* rotRight( Node *root ){   //Raiz es el argumento, se retornara pivot como raiz luego de rotar
    Node* pivot = root -> left;     //Asigno a pivot el subarbol izquierdo de root
    …
}

Los pasos a seguir con los punteros serán los siguientes:

Esto en código es:

...
root -> left = pivot -> right; //Puntero izquierdo de root apunta a derecho de pivot.
...

Esto en código es:

...
pivot -> right = root; //Puntero derecho de pivot apunta a root.
...

Retorno pivot como nueva raíz, el código adjunto es el siguiente:

//Rotación a la Derecha
Node* rotRight( Node *root ){       //Raiz es el argumento, se retornara pivot como raiz luego de rotar
    Node* pivot = root -> left;     //Asigno a pivot el subarbol izquierdo de root
    root -> left = pivot -> right;  //Puntero izquierdo de root apunta a derecho de pivot.
    pivot -> right = root;          //Puntero derecho de pivot apunta a root.
    return pivot;
}

b. Rotación a la Izquierda

Tengamos la siguiente imagen, la izquierda será el árbol inicial y la derecha será el árbol, luego de rotarlo

La rotación a la izquierda es similar a la rotación a la derecha, los pasos serian los siguientes:

...
root -> right = pivot -> left; //Puntero derecho de root apunta a derecho de pivot.
...

...
pivot -> left = root; //Puntero izquierdo de pivot apunta a root.
...

//Rotación a la Izquierda
Node* rotLeft( Node *root ){        //Raiz es el argumento, se retornara pivot como raiz luego de rotar
    Node* pivot = root -> right;    //Asigno a pivot el subarbol derecho de root
    root -> right = pivot -> left;  //Puntero derecho de root apunta a derecho de pivot.
    pivot -> left = root;           //Puntero izquierdo de pivot apunta a root.
    return pivot;
}

Estas son las rotaciones necesarias para el Treap, ahora si se procederá a explicar la inserción en el Treap.

1.2.1.2 Inserción

Tengamos el siguiente árbol:

La parte superior me indica la clave y la que esta entre paréntesis me indica la prioridad generada, en este caso trabajaremos con propiedades de Max-Heap.

Ahora queremos ingresar el nodo con clave = 9 y prioridad = 51. Entonces seguimos los siguientes pasos:

  1. Buscamos el nodo como en un BST por su clave.
  2. Una vez encontrado la ubicación del nodo.
  3. Si cumple con las propiedades de Heap entonces termina.
  4. Sino por medio de rotaciones voy ubicando el nodo a ingresar hasta que cumpla con las propiedades de heap.

La declaración de la función y el paso 1 para inserción sería:

Node* insert( Node *root , Node *novo ){ //Ingreso árbol actual y el nuevo nodo a insertar
    if( root == NULL ) return novo;            //Encontré posición para nodo
    if( root -> key < novo -> key ){              //Buscamos por la derecha
        root -> right = insert( root -> right , novo );
        …
    }
    else{				        //Buscamos por la izquierda
        root -> left = insert( root -> left , novo );
        …
    }
    …
}

La 1era imagen me muestra el paso 1. Ubicamos el nodo por la clave siguiendo una búsqueda binaria sobre la clave.

Como tenemos Prioridad (hijo = 59) >= Prioridad (padre = 9) no cumple con propiedades de max-Heap, por tanto realizamos una rotación a la izquierda. Ello se muestra en la 2da  imagen.

Como aun no se cumple propiedades del heap se sigue realizando rotaciones, en la 2da imagen se realiza una rotación a la derecha dando como resultado la 3ra imagen.

De esa manera seguimos rotando como se muestra en las siguientes imágenes:

Como podemos observar en estas últimas imágenes se realizan las últimas rotaciones, en la 2da imagen se realiza una rotación a la izquierda y el nodo ingresado quedaría ubicado en la raíz:

Ahora si cumple con las propiedades del heap y de un árbol binario. De esa forma se realiza una inserción mediante rotaciones.

El código de inserción final con las rotaciones sería de la siguiente manera:

//Inserción: Recibo un arbol y el nodo a insertar
Node* insert( Node *root , Node *novo ){       //Ingreso árbol actual y el nuevo nodo a insertar
    if( root == NULL ) return novo;            //Encontre posición para nodo
    if( root -> key < novo -> key ){           //Buscamos por la derecha
        root -> right = insert( root -> right , novo );
        if( root -> right -> priority > root -> priority ) root = rotLeft( root ); //rotacion izquierda
    }
    else{				                       //Buscamos por la izquierda
        root -> left = insert( root -> left , novo );
        if( root -> left -> priority > root -> priority ) root = rotRight( root ); //rotacion derecha
    }
    return root;
}

1.2.2 Inserción por medio de Separación de un árbol

Tengamos con el mismo ejemplo

La parte superior me indica la clave y la que esta entre paréntesis me indica la prioridad generada, en este caso trabajaremos con propiedades de Max-Heap.

Ahora queremos ingresar el nodo con clave = 9 y prioridad = 51. Entonces seguimos los siguientes pasos:

  1. Buscamos al igual que el anterior como un BST por clave.
  2. En cada paso de búsqueda si prioridad (nuevo) <= prioridad (actual) sigo buscando.
  3. Sino en la posición actual separo en 2 arboles.
  4. Inserto el elemento asignando los punteros respectivos.

Del nuevo nodo tengo una prioridad de 51 la cual es mayor al de la raíz que es 39, como estamos con un max-heap este valor tendría que ser la nueva raiz, entonces no puedo seguir realizando búsqueda por clave, por ello hago partición del árbol para insertar el nuevo nodo. Esta parte de partición la realizaremos como en un BST normal sin considerar la prioridad.

La porción de código de inserción sería de la siguiente manera:

//Inserción: Recibo un arbol y el nodo a insertar
Node* insert( Node *root , Node *novo ){
    if( root == NULL ) return novo;
    if( root -> priority < novo -> priority ){ //si no cumple propiedad de heap en la ubicacion actual
          split( root , novo -> key , novo -> left , novo -> right );  //insertamos nodo mediante split
          return novo; //retorno nuevo nodo con sus respectivos subárboles izquierdo y derecho
    }
   //Búsqueda del elemento por la clave.
    if( root -> key < novo -> key ) root -> right = insert( root -> right , novo );
    else root -> left = insert( root -> left , novo );
    return root;
}

1.2.2.1 Split( Separación en 2 arboles)

La función de separación de un árbol lo llamaremos Split, y funciona de la siguiente manera. Supongamos que tenemos el siguiente árbol binario:

Entonces insertamos el nodo con clave 26. Al insertar 26 todos los nodos mayores a 26 tienen que estar a la derecha y los menores a la izquierda.

Veamos los pasos con la imagen siguiente:

A medida que vamos avanzando en la búsqueda de la posición del nodo, vamos partiendo el árbol. Al llegar a la ubicación como se ve en la última imagen, a la izquierda de 28, L y R se forman con los retornos de las llamadas recursivas, teniendo lo siguiente:

El Árbol R se forma por los subárboles R’.

De la misma forma el árbol L se forma con los subárboles L’.

Al final el árbol R y L serán hijo derecho e izquierdo del nuevo nodo insertado respectivamente, quedando lo siguiente:

De esta forma se da la inserción por medio de la separación de arboles. La implementación requiere conocimiento de manejo de punteros.

//Split: Ingresa la raíz del árbol, la clave del nodo a insertar y los subárboles izquierdo y derecho
void split( Node* root , int key , Node *&L , Node*&R ){
    if( root == NULL ){ L = R = NULL; return; }
    else if( root -> key < key ){ split( root ->right , key , root -> right , R ); L = root;}
    else{ split( root -> left , key , L , root -> left ); R = root; }
}

1.3 Eliminación

La eliminación es similar a la inserción también se puede dar de 2 formas, la primera con rotaciones y la segunda por medio de la unión de arboles.

1.3.1 Eliminación mediante rotaciones

La eliminación mediante rotaciones es lo inverso a la inserción. Tengamos el árbol:

Ahora queremos eliminar el nodo con clave = 9 y prioridad = 51. Entonces seguimos los siguientes pasos:

  1. Buscamos el nodo como en un BST por su clave.
  2. Una vez encontrado el nodo.
  3. Mediante rotaciones lo hago descender hasta que se convierta en una hoja, en las rotaciones se considera la prioridad mas no la clave.
  4. Una vez que el nodo a eliminar sea una hoja lo elimino.
//Declaracion del método, recibo un arbol y la clave del nodo a eliminar
Node* erase( Node* root , int key ){
    if( root == NULL ){ return root; }
    //Realizo la busqueda por clave
    if( root -> key < key ) root -> right = erase( root -> right , key );
    else if( root -> key > key ) root -> left = erase( root -> left , key );
    else{
           …
    }
    return root;
}

Del ejemplo el paso 1 me indica que el nodo a eliminar es la raíz, ahora para saber que rotación debo hacer tengo que tener en cuenta el tipo de heap que estoy usando, como en nuestro caso es un max-Heap, tengo que ver la prioridad  máxima entre el hijo izquierdo y el hijo derecho.

Node* erase( Node* root , int key ){
    if( root == NULL ){ return root; }
    if( root -> key < key ) root -> right = erase( root -> right , key );
    else if( root -> key > key ) root -> left = erase( root -> left , key );
    else{
        //Si tengo ambos hijos puedo comparar prioridades
        if( root -> left != NULL ){
            if( root -> right != NULL ){
                //Elijo el de mayor prioridad
                if( root -> left -> priority < root -> right -> priority ){
                   …
                }else{
                    …
                }
            }
            else…
        }
        else …
    }
    return root;
}

Si el de máxima prioridad es el nodo derecho, este tendrá que ser la nueva raíz, por tanto se tendrá que realizar una rotación a la izquierda.

Si el de máxima prioridad es el nodo izquierdo, este tendrá que ser la nueva raíz, por tanto se tendrá que realizar una rotación a la derecha.

Veamos las imágenes para el mayor entendimiento:

Como muestra la imagen tengo que hacer descender el nodo con clave 9 a la izquierda y colocar el nodo 15 como nueva raíz, luego de la rotación izquierda tendríamos.

En código tendríamos lo siguiente:

...
if( root -> left -> priority < root -> right -> priority ){
    root = rotLeft( root );
    root -> left = erase( root -> left , key );
}else
...

Ahora el de mayor prioridad es el hijo izquierdo por tanto este tiene que ser la raíz, realizamos rotación a la derecha.

En código tendríamos lo siguiente:

...
else{
   root = rotRight( root ); //rotacion derecha
   root -> right = erase( root -> right , key );
}
...

Y así hasta que lleguemos a la hoja.

Como se pudo observar es el mismo procedimiento que inserción solo que de manera inversa, ahora que tenemos el nodo en la hoja basta con colocarlo como NULL para su eliminación.

Código de eliminación:

//Eliminacion: Recibo un arbol y la clave del nodo a eliminar
Node* erase( Node* root , int key ){
    if( root == NULL ){ return root; }
    //Realizo la busqueda por clave
    if( root -> key < key ) root -> right = erase( root -> right , key );
    else if( root -> key > key ) root -> left = erase( root -> left , key );
    else{
        //Si tengo ambos hijos puedo comparar prioridades
        if( root -> left != NULL ){
            if( root -> right != NULL ){
                //Elijo el de mayor prioridad
                if( root -> left -> priority < root -> right -> priority ){
                    root = rotLeft( root );  //rotacion izquierda
                    root -> left = erase( root -> left , key );
                }else{
                    root = rotRight( root ); //rotacion derecha
                    root -> right = erase( root -> right , key );
                }
            }
            else{ //Si tengo solo hijo izquierdo basta con cambiar con dicho nodo y eliminar el actual
                Node* aux = root -> left;  delete root; return aux;
            }
        }
        else{
            //Si tengo solo hijo derecho basta con cambiar con dicho nodo y eliminar el actual
            if( root -> right != NULL ){
                Node* aux = root -> right;  delete root; return aux;
            }
            else{ //Si mi nodo actual es hoja lo elimino
                delete root;  return NULL;
            }
        }
    }
    return root;
}

1.3.2 Eliminación mediante unión de arboles

Teniendo el árbol anterior como ejemplo:

Ahora queremos eliminar el nodo con clave = 9 y prioridad = 51. Entonces seguimos los siguientes pasos:

  1. Buscamos el nodo como en un BST por su clave.
  2. Una vez encontrado el nodo.
  3. Mezclo sus hijos izquierdo y derecho en un solo árbol T.
  4. Eliminamos el nodo encontrado y retornamos el nuevo árbol T
//Eliminacion: Recibo un arbol y la clave del nodo a eliminar
Node* erase( Node* root , int key ){
    if( root == NULL ) return NULL;
    if( root -> key == key ){ //si lo encontre, mezclo sus subarboles
        Node *aux = merge( root -> left , root -> right );
        delete root; //elimino nodo actual
        return aux; //retorno nuevo arbol
    }
   //Busqueda de nodo por clave
    if( root -> key < key ) root -> right = erase( root -> right , key );
    else root -> left = erase( root -> left , key );
    return root;
}

Entonces en el caso ejemplo el nodo es la raíz, tendremos 2 subárboles el izquierdo y derecho.

1.3.2.1 Merge( Mezcla de 2 Arboles)

Por medio de este método realizaremos la eliminación, explicare como mezclar 2 subárboles. Debemos tener en cuenta que todas las claves del árbol izquierdo deben ser menores que las claves del árbol derecho.

La declaración del método es:

Node* merge( Node* L , Node* R ){ //Recibo 2 arboles
    Node *root;			       //Este sera nuestro nuevo arbol
    …
    return root;
}

Si tengo alguno de los arboles como Nulo entonces el nuevo árbol será el no nulo, o nulo si ambos son nulos.

Node* merge( Node* L , Node* R ){
    Node *root;
    if( L == NULL || R == NULL ) root = ( L != NULL ?L : R );
    …
    return root;
}

Ahora si no son nulos debemos tener en cuenta que estamos trabajando con un max-heap por tanto al mezclar ambos arboles, la raíz debe tener el máximo valor, entonces tenemos que comparar la prioridad de ambos arboles y elegir el máximo.

La nueva raíz será ese nodo, como las claves del subárbol derecho de la nueva raíz tiene claves mayores entonces todo ese subárbol ya formara parte del nuevo árbol, teniendo:

Ahora tendremos que comparar el subárbol izquierdo de la nueva raíz con el árbol izquierdo inicial.

Eso seria en código como sigue:

Node* merge( Node* L , Node* R ){
    ...
    else if( L -> priority < R -> priority ){ R -> left = merge( L , R -> left ); root = R; }
    else
    ...
}

De la misma manera comparamos las claves y elegimos raíz con su subárbol respectivo. En este caso seria el árbol izquierdo con su subárbol izquierdo.

La porción de código de esta parte seria:

Node* merge( Node* L , Node* R ){
    ...
    if( L -> priority < R -> priority ){ ... }
    else{ L -> right = merge( L -> right , R ); root = L; }
    ...
}

Ahora comparamos los dos siguientes arboles:

En este caso tendríamos como el inicial la raíz seria el árbol derecho.

Al final solo nos quedara 2 nodos que tendremos que unir finalizada la recursión. Ahora debemos unir los arboles de las llamadas recursivas.

De esta manera se realiza la unión de 2 arboles, el código de todo lo visto para el método merge es como sigue:

//Merge: Recibo un Arbol Izquierdo y un Arbol Derecho
//Todas las claves de L deben ser menores que R
Node* merge( Node* L , Node* R ){
    Node *root;			          //Este sera nuestro nuevo arbol
    if( L == NULL || R == NULL ) root = ( L != NULL ? L : R );
    else if( L -> priority < R -> priority ){ R -> left = merge( L , R -> left ); root = R; }
    else{ L -> right = merge( L -> right , R ); root = L; }
    return root;
}

Códigos en C++:

Implementación de la Estructura con Rotaciones: Treap-Rotaciones
Implementación de la Estructura con Merge y Split: Treap-Merge-Split

Problemas en Jueces

La mayor parte de problemas en los cuales se usa esta estructura pediran obtener el valor del k-esimo menor elemento, el k-esimo menor elemento es el elemento en la posicion k luego de ingresar valores, teniendo estos valores ordenados. Por ejemplo si inserto -1 , 2 ,3. Y deseo saber el valor para k = 2 (comenzando los indices de k desde 1) me devolveria el valor de 2. La implementacion de la funcion que halle el k-esimo menor elemento se encuentra en el siguiente problema resuelto – ORDERSET.

Ahora si les dejo algunos problemas que se resuelven con Treap, cabe mencionar que dichos problemas tambien pueden ser resueltos por medio de otras estructuras como Splay Tree.

SPOJ: 3273 – Order Statistic Set (ORDERSET)Solucion

CodeforcesString Manipulation 1.0

LightOJ: 1087 – Diablo

TJU: 2159 – Black Box

POJ:

1442 – Black Box

2201 – Cartesian Tree

Por Jhosimar George Arias Figueroa

4 Respuestas a “ÁRBOL DE BÚSQUEDA ALEATORIZADO – TREAP

  1. Yo trabajo para una pequeña empresa y que no tienen un sitio web. ¿Cuál es la manera más fácil , más barato para iniciar un sitio web de aspecto profesional? .

  2. whoah this blog is wonderful i like reading your articles. afebbadfeakekebd

  3. Excelente post, sin embargo hay una implementación más simple:
    http://codepad.org/2FPgI6wr

    Más info en http://codeforces.com/blog/entry/11148 o google translate de http://e-maxx.ru/algo/treap

  4. Hola!, me parece muy paja que hagas esto 🙂 . Road to ICPC Mundial!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s