Scribd
Cargar
4 vistas19 páginas

Introducción a los Treaps y su Manejo

El documento describe el concepto de treaps, que combinan propiedades de árboles binarios de búsqueda (ABB) y montículos (heaps) mediante la inserción y eliminación de nodos basados en claves y prioridades. Se explican los procesos de inserción, búsqueda y eliminación de nodos, incluyendo el uso de rotaciones para mantener las propiedades del treap. Además, se presentan ejemplos y fragmentos de código para ilustrar la implementación de estas operaciones.

Cargado por

xi7yu
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd
4 vistas19 páginas

Introducción a los Treaps y su Manejo

El documento describe el concepto de treaps, que combinan propiedades de árboles binarios de búsqueda (ABB) y montículos (heaps) mediante la inserción y eliminación de nodos basados en claves y prioridades. Se explican los procesos de inserción, búsqueda y eliminación de nodos, incluyendo el uso de rotaciones para mantener las propiedades del treap. Además, se presentan ejemplos y fragmentos de código para ilustrar la implementación de estas operaciones.

Cargado por

xi7yu
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd

TREAPS

TREAP

TREE

HEAP

Es un ABB

2
Llamada Prioridad

LA INSERCIN DE UN NODO

CLAVE Determinada, En las hojas de un AB

Todas CLAVES Cumplen Propiedad ABB

Puede ser Propiedad HEAP

Propiedad HEAP Tener Prioridades de los hijo mayores al padre

PARA REESTABLECER Propiedad HEAP

Al nodo, recin insertado

Se hace ASCENDER

Mediante ROTACIONES

Padre Prioridad MAYOR

Padre Prioridad MENOR

Nuevo Nodo RAIZ

EJEMPLO

Clave

9 , 4, 15, 2, 5, 12, 20, 7, 8

Prioridad 10, 12, 13, 22, 24, 18, 40, 33, 11

Se ilustra un treap, donde en la parte superior se muestra la clave y en la inferior de cada nodo la prioridad. El rbol se form ingresando las claves de acuerdo a un orden creciente de las prioridades; es decir en orden: 10, 12, 13, 18, 22, 24, 33 y 40. El nodo con menor valor de prioridad se ubica en la raz

No se cumple la propiedad, que la prioridad del nodo 8 sea mayor que la de su padre, puede restablecerse esta condicin mediante la rotacin a la izquierda en el nodo padre, el 7 en este caso.

Del nodo con clave 8 hacia abajo se tiene un heap, pero no hacia arriba. Por esto es preciso efectuar otra rotacin a la izquierda en el nodo padre del 8, el nodo con clave 5

Finalmente volviendo a rotar a la izquierda en el nodo con clave 4, padre del nodo con clave 8, se logra el treap

El descarte del nodo con clave 8, sigue el proceso inverso a su insercin, se lo hace descender, mediante rotaciones con el nodo hijo que tenga menor prioridad, hasta llegar a ser una hoja. La operacin descarte se ve simplificada si los enlaces derecho e izquierdo de las hojas apuntan a un nodo de fondo o centinela que tenga un valor mayor de prioridad que los valores de prioridad que puedan tener los nodos.

LA INSERCIN DE UN NODO
void insertar(Clave k, Float p, Nodo t) {// k es el dato a insertar, p es la prioridad aleatoria if (t== null) t = new Nodo(k,p); else if(k < [Link]){ insertar(k , p , [Link]); if( [Link]. Prioridad() < [Link]()) rotarDerecha(t); } else{ insertar(k , p , [Link]); if( [Link]() < [Link]()) rotarIzquierda(t); } }

ROTACIONES

Void rotarIzq(Nodo p){ q=[Link]; [Link]=[Link]; [Link]=p }

Void rotarDer(Nodo p){ q=[Link]; [Link]=[Link]; [Link]=p }

BSQUEDA
Desde la raz

INICIA

Comparando el valor del dato a buscar

Con el valor del nodo

MENOR

Invoca al hijo Izquierdo Invoca al hijo Derecho

MAYOR

FINALIZA

Valores coinciden, Retorna true.

LA BSQUEDA DE UN NODO

Boolean buscar( T k, Nodo t) { if(t== null) return false; if([Link]==k) return true; if(k<[Link]) return buscar(k , [Link] ); else return buscar(k , [Link] ); }

ELIMINACIN
Mediante ROTACIONES

BSQUEDA dato

Se desciende

HASTA

ELIMINACIN

ELIMINACIN

LA ELIMINACIN DE UN NODO

Nodo eliminar(T k, Nodo t) { Nodo r=null; if([Link] == k){ r= t; t=eliminar_Raiz(t); } if(k <[Link]) r= eliminar(k, [Link] ); else r= eliminar(k, [Link] ); return r; }

LA ELIMINACIN DE UN NODO
Nodo eliminar_Raiz( Nodo t ) { if([Link]() || t==null) return null; if([Link] < [Link]){ rotarDerecha(t) ; eliminar_Raiz([Link]); } else { rotarIzquierda(t); eliminar_Raiz([Link]); }

Gracias por su atencin

YURLEY XIOMARA ROJAS SANCHEZ


1150273 [Link]@[Link]

GUSTAVO ALFONSO TARAZONA PAEZ


1150471 GUSTAVOTARAZONA@[Link]

JULIO -2012 copyright

También podría gustarte