Árbol biselado
De Wikipedia, la enciclopedia libre
Un Árbol biselado o Árbol Splay es un árbol binario de búsqueda, un tipo de estructura de datos usado en informática, en el que cualquier operación requiere un esquema de reordenado que se denomina biselación. Esta estructura de datos fue inventada por Robert Tarjan y Daniel Sleator.
Tabla de contenidos |
[editar] Descripción
El objetivo de este tipo de árboles es el reducir el tiempo de búsqueda de los valores de clave manteniendo los nodos más recientemente accedidos cercanos a la raíz, por lo que podrán ser encontrados más rápidamente. Los árboles binarios de búsqueda auto-ajustables intentan también acceder a los valores de clave más rápidamente pero manteniendo el árbol equilibrado en todo momento. Ejemplos de este árbol son el árbol AVL y el árbol Rojo-Negro.
En los árboles binarios de búsqueda auto-ajustables se garantiza que el tiempo en acceder a un valor de clave no excederá de O(log n). En los árboles biselados se puede necesitar de O(n), pero aseguran que este comportamiento no se producirá de manera repetida y además tienen como ventaja que no se necesita información adicional en cada nodo para controlar el equilibrio del árbol.
[editar] Operaciones
[editar] Búsqueda
La búsqueda de un valor de clave en un árbol biselado tiene la característica particular de que modifica la estructura del árbol. El descenso se efectúa de la misma manera que un árbol binario de búsqueda, pero si se encuentra un nodo cuyo valor de clave coincide con el buscado, se realiza una biselación (ascensión hasta la raíz) de ese nodo. Si no se encuentra, el nodo biselado es aquel examinado antes de llegar al enlace nulo. Así, la raíz contendrá el sucesor o predecesor en simétrico del nodo buscado.
[editar] Inserción
Es igual que en el árbol binario de búsqueda con la salvedad de que se realiza una biselación sobre el nodo insertado. Además, si el valor de clave a insertar ya existe en el árbol, se bisela el nodo que lo contiene.
[editar] Extracción
Esta operación requiere dos biselaciones. Primero se busca el nodo que contiene el valor de clave que se debe extraer. Si no se encuentra, el árbol es biselado en el último nodo examinado y no se realiza ninguna acción adicional. Si se encuentra, el nodo se bisela y se elimina. Con esto el árbol se queda separado en dos mitades, por lo que hay que seleccionar un nodo que haga las veces de raíz. Al ser un ABB y estar todos los valores de clave ordenados, podemos elegir como raíz el mayor valor del subárbol izquierdo o el menor valor de clave del derecho.
