Los árboles de dispersión son árboles de búsqueda binarios autoequilibrados o autoajustados. En otras palabras, podemos decir que los árboles splay son las variantes de los árboles binarios de búsqueda. El requisito previo para los árboles de dispersión es que debemos conocer los árboles de búsqueda binarios.
Como ya sabemos, la complejidad temporal de un árbol de búsqueda binario en todos los casos. La complejidad temporal de un árbol de búsqueda binario en el caso promedio es O(iniciar sesión) y la complejidad temporal en el peor de los casos es O(n). En un árbol de búsqueda binario, el valor del subárbol izquierdo es menor que el nodo raíz y el valor del subárbol derecho es mayor que el nodo raíz; en tal caso, la complejidad del tiempo sería O(iniciar sesión) . Si el árbol binario está sesgado hacia la izquierda o hacia la derecha, entonces la complejidad temporal sería O (n). Para limitar la asimetría, el AVL y árbol rojo-negro entró en escena, teniendo O(iniciar sesión ) complejidad temporal para todas las operaciones en todos los casos. También podemos mejorar esta complejidad temporal realizando implementaciones más prácticas, por lo que el nuevo árbol ¿Qué es un árbol Splay?
Un árbol splay es un árbol que se equilibra a sí mismo, pero Los árboles AVL y Red-Black también son árboles autoequilibrados. Lo que hace que el árbol splay sea único en dos árboles. Tiene una propiedad extra que lo hace único: la extensión.
Un árbol splay contiene las mismas operaciones que un Árbol de búsqueda binaria , es decir, inserción, eliminación y búsqueda, pero también contiene una operación más, es decir, mostrar. Entonces. todas las operaciones en el árbol de expansión van seguidas de la expansión.
Los árboles splay no son árboles estrictamente equilibrados, pero sí árboles aproximadamente equilibrados. Entendamos la operación de búsqueda en el árbol de distribución.
Supongamos que queremos buscar 7 elementos en el árbol, que se muestra a continuación:
Para buscar cualquier elemento en el árbol de distribución, primero realizaremos la operación estándar del árbol de búsqueda binaria. Como 7 es menor que 10, llegaremos a la izquierda del nodo raíz. Después de realizar la operación de búsqueda, debemos realizar la visualización. Aquí expandir significa que la operación que estamos realizando en cualquier elemento debe convertirse en el nodo raíz después de realizar algunos reordenamientos. La reordenación del árbol se realizará mediante las rotaciones.
Nota: El árbol extendido se puede definir como el árbol autoajustado en el que cualquier operación realizada en el elemento reorganizaría el árbol de modo que el elemento en el que se realizó la operación se convierta en el nodo raíz del árbol.
Rotaciones
Hay seis tipos de rotaciones que se utilizan para ensanchar:
- Rotación en zig (rotación hacia la derecha)
- Rotación Zag (rotación a la izquierda)
- Zig zag (Zig seguido de zag)
- Zag zig (Zag seguido de zig)
- Zig zig (dos rotaciones a la derecha)
- Zag zag (dos rotaciones a la izquierda)
Factores necesarios para seleccionar un tipo de rotación.
Los siguientes son los factores utilizados para seleccionar un tipo de rotación:
- ¿El nodo que intentamos rotar tiene un abuelo?
- ¿El nodo es hijo izquierdo o derecho del padre?
- ¿El nodo es hijo izquierdo o derecho del abuelo?
Casos para las rotaciones
Caso 1: Si el nodo no tiene abuelo y es el hijo derecho del padre, entonces realizamos la rotación hacia la izquierda; de lo contrario, se realiza la rotación correcta.
Caso 2: Si el nodo tiene un abuelo, según los siguientes escenarios; la rotación se realizaría:
Escenario 1: Si el nodo tiene el derecho del padre y el padre también tiene el derecho de su padre, entonces zig zig derecha rotación derecha es interpretado.
Escenario 2: Si el nodo está a la izquierda de un padre, pero el padre está a la derecha de su padre, entonces zig zag rotación derecha izquierda es interpretado.
Escenario 3: Si el nodo está a la derecha del padre y el padre está a la derecha de su padre, entonces zig zig izquierda rotación izquierda es interpretado.
Escenario 4: Si el nodo está a la derecha de un padre, pero el padre está a la izquierda de su padre, entonces rotación en zig zag derecha-izquierda es interpretado.
Ahora, comprendamos las rotaciones anteriores con ejemplos.
Para reorganizar el árbol, necesitamos realizar algunas rotaciones. Los siguientes son los tipos de rotaciones en el árbol de distribución:
Las rotaciones en zig se utilizan cuando el elemento que se va a buscar es un nodo raíz o el hijo de un nodo raíz (es decir, el hijo izquierdo o derecho).
Los siguientes son los casos que pueden existir en el árbol de distribución durante la búsqueda:
Caso 1: Si el elemento de búsqueda es un nodo raíz del árbol.
Caso 2: Si el elemento de búsqueda es hijo del nodo raíz, entonces habrá dos escenarios:
- Si el niño es un niño izquierdo, se realizaría la rotación derecha, conocida como rotación en zig-derecha.
- Si el niño es derecho, se realizaría la rotación hacia la izquierda, conocida como rotación en zig hacia la izquierda.
Veamos los dos escenarios anteriores a través de un ejemplo.
Considere el siguiente ejemplo:
En el ejemplo anterior, tenemos que buscar 7 elementos en el árbol. Seguiremos los siguientes pasos:
Paso 1: Primero, comparamos 7 con un nodo raíz. Como 7 es menor que 10, es un hijo izquierdo del nodo raíz.
Paso 2: Una vez encontrado el elemento realizaremos el esparcimiento. La rotación hacia la derecha se realiza para que 7 se convierta en el nodo raíz del árbol, como se muestra a continuación:
Consideremos otro ejemplo.
En el ejemplo anterior, tenemos que buscar 20 elementos en el árbol. Seguiremos los siguientes pasos:
Paso 1: Primero, comparamos 20 con un nodo raíz. Como 20 es mayor que el nodo raíz, es el hijo derecho del nodo raíz.
Paso 2: Una vez encontrado el elemento realizaremos el esparcimiento. La rotación hacia la izquierda se realiza de modo que 20 elementos se conviertan en el nodo raíz del árbol.
A veces surge la situación cuando el artículo que se va a buscar tiene un padre además de un abuelo. En este caso, tenemos que realizar cuatro rotaciones para ensanchar.
Entendamos este caso a través de un ejemplo.
Supongamos que tenemos que buscar 1 elemento en el árbol, que se muestra a continuación:
Paso 1: Primero, tenemos que realizar una operación de búsqueda BST estándar para buscar el elemento 1. Como 1 es menor que 10 y 7, estará a la izquierda del nodo 7. Por lo tanto, el elemento 1 tiene un padre, es decir, 7, así como un abuelo, es decir, 10.
Paso 2: En este paso, tenemos que realizar el esparcimiento. Necesitamos convertir el nodo 1 en un nodo raíz con la ayuda de algunas rotaciones. En este caso, no podemos simplemente realizar una rotación en zig o zag; Tenemos que implementar la rotación en zig zig.
Para convertir el nodo 1 en un nodo raíz, necesitamos realizar dos rotaciones hacia la derecha conocidas como rotaciones en zig zig. Cuando realizamos la rotación correcta, el 10 se moverá hacia abajo y el nodo 7 subirá como se muestra en la siguiente figura:
Nuevamente, realizaremos una rotación en zig hacia la derecha, el nodo 7 se moverá hacia abajo y el nodo 1 subirá como se muestra a continuación:
Como observamos en la figura anterior, el nodo 1 se ha convertido en el nodo raíz del árbol; por lo tanto, la búsqueda se completa.
Supongamos que queremos buscar 20 en el siguiente árbol.
Para buscar 20, necesitamos realizar dos rotaciones hacia la izquierda. Los siguientes son los pasos necesarios para buscar 20 nodos:
Paso 1: Primero, realizamos la operación de búsqueda BST estándar. Como 20 es mayor que 10 y 15, estará a la derecha del nodo 15.
Paso 2: El segundo paso es realizar el esparcimiento. En este caso se realizarían dos rotaciones hacia la izquierda. En la primera rotación, el nodo 10 se moverá hacia abajo y el nodo 15 se moverá hacia arriba como se muestra a continuación:
En la segunda rotación hacia la izquierda, el nodo 15 se moverá hacia abajo y el nodo 20 se convertirá en el nodo raíz del árbol, como se muestra a continuación:
Como hemos observado que se realizan dos rotaciones hacia la izquierda; por eso se le conoce como rotación en zig zig hacia la izquierda.
Hasta ahora, hemos leído que tanto los padres como los abuelos tienen una relación RR o LL. Ahora veremos la relación RL o LR entre el padre y el abuelo.
Entendamos este caso a través de un ejemplo.
Supongamos que queremos buscar 13 elementos en el árbol que se muestra a continuación:
Paso 1: Primero, realizamos la operación de búsqueda BST estándar. Como 13 es mayor que 10 pero menor que 15, el nodo 13 será el hijo izquierdo del nodo 15.
Paso 2: Dado que el nodo 13 está a la izquierda del 15 y el nodo 15 está a la derecha del nodo 10, existe la relación RL. Primero, realizamos la rotación hacia la derecha en el nodo 15, el 15 se moverá hacia abajo y el nodo 13 subirá, como se muestra a continuación:
Aún así, el nodo 13 no es el nodo raíz y el 13 está a la derecha del nodo raíz, por lo que realizaremos una rotación hacia la izquierda conocida como rotación en zag. El nodo 10 se moverá hacia abajo y el 13 se convertirá en el nodo raíz como se muestra a continuación:
Como podemos observar en el árbol de arriba, el nodo 13 se ha convertido en el nodo raíz; por lo tanto, la búsqueda se completa. En este caso, primero hemos realizado la rotación en zig y luego la rotación en zag; por eso se le conoce como rotación en zigzag.
Entendamos este caso a través de un ejemplo.
Supongamos que queremos buscar 9 elementos en el árbol, que se muestra a continuación:
Paso 1: Primero, realizamos la operación de búsqueda BST estándar. Como 9 es menor que 10 pero mayor que 7, será el hijo derecho del nodo 7.
Paso 2: Dado que el nodo 9 está a la derecha del nodo 7 y el nodo 7 está a la izquierda del nodo 10, existe la relación LR. Primero, realizamos la rotación hacia la izquierda en el nodo 7. El nodo 7 se moverá hacia abajo y el nodo 9 se moverá hacia arriba como se muestra a continuación:
Aún así, el nodo 9 no es un nodo raíz y el 9 está a la izquierda del nodo raíz, por lo que realizaremos la rotación hacia la derecha conocida como rotación en zig. Después de realizar la rotación hacia la derecha, el nodo 9 se convierte en el nodo raíz, como se muestra a continuación:
Como podemos observar en el árbol de arriba, el nodo 13 es un nodo raíz; por lo tanto, la búsqueda se completa. En este caso, primero hemos realizado la rotación en zag (rotación a la izquierda) y luego se realiza la rotación en zig (rotación a la derecha), por lo que se conoce como rotación en zag zig.
Ventajas del árbol Splay
- En el árbol de distribución, no necesitamos almacenar información adicional. Por el contrario, en los árboles AVL, necesitamos almacenar el factor de equilibrio de cada nodo que requiere espacio adicional, y los árboles Rojo-Negro también requieren almacenar un bit adicional de información que denota el color del nodo, ya sea Rojo o Negro.
- Es el tipo más rápido de árbol de búsqueda binaria para diversas aplicaciones prácticas. Se utiliza en Compiladores de Windows NT y GCC .
- Proporciona un mejor rendimiento ya que los nodos a los que se accede con frecuencia se acercarán al nodo raíz, por lo que se puede acceder rápidamente a los elementos en los árboles extendidos. Se utiliza en la implementación de la caché, ya que los datos a los que se accedió recientemente se almacenan en la caché, de modo que no necesitamos ir a la memoria para acceder a los datos y lleva menos tiempo.
Desventaja del árbol Splay
El principal inconveniente del árbol splay sería que los árboles no están estrictamente equilibrados, es decir, están aproximadamente equilibrados. A veces, los árboles extendidos son lineales, por lo que requerirá una complejidad de tiempo O (n).
Operación de inserción en el árbol Splay
En el inserción operación, primero insertamos el elemento en el árbol y luego realizamos la operación de extensión en el elemento insertado.
15, 10, 17, 7
Paso 1: Primero, insertamos el nodo 15 en el árbol. Después de la inserción, debemos realizar el ensanchamiento. Como 15 es un nodo raíz, no es necesario realizar la separación.
Paso 2: El siguiente elemento es 10. Como 10 es menor que 15, el nodo 10 será el hijo izquierdo del nodo 15, como se muestra a continuación:
Ahora, realizamos esparciendo . Para convertir 10 en nodo raíz, realizaremos la rotación hacia la derecha, como se muestra a continuación:
Paso 3: El siguiente elemento es 17. Como 17 es mayor que 10 y 15, se convertirá en el hijo derecho del nodo 15.
Ahora, realizaremos el esparcimiento. Como 17 es tener un padre y un abuelo, realizaremos rotaciones en zig zig.
En la figura anterior, podemos observar que 17 se convierte en el nodo raíz del árbol; por lo tanto, se completa la inserción.
Etapa 4: El siguiente elemento es 7. Como 7 es menor que 17, 15 y 10, el nodo 7 quedará como hijo de 10.
Ahora tenemos que abrir el árbol. Como 7 tiene un padre y un abuelo, realizaremos dos rotaciones a la derecha como se muestra a continuación:
Aún así, el nodo 7 no es un nodo raíz, es un hijo izquierdo del nodo raíz, es decir, 17. Por lo tanto, necesitamos realizar una rotación más hacia la derecha para convertir el nodo 7 en un nodo raíz como se muestra a continuación:
Algoritmo para la operación de inserción
Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n)
En el algoritmo anterior, T es el árbol y n es el nodo que queremos insertar. Hemos creado una variable temporal que contiene la dirección del nodo raíz. Ejecutaremos el bucle while hasta que el valor de temp sea NULL.
Una vez completada la inserción, se realizaría el ensanchamiento.
Algoritmo para la operación de reproducción
Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y
En la implementación anterior, x es el nodo en el que se realiza la rotación, mientras que y es el hijo izquierdo del nodo x.
Implementación de rotación izquierda (T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
En la implementación anterior, x es el nodo en el que se realiza la rotación e y es el hijo derecho del nodo x.
Eliminación en el árbol Splay
Como sabemos, los árboles de visualización son variantes del árbol de búsqueda binaria, por lo que la operación de eliminación en el árbol de visualización sería similar a la BST, pero la única diferencia es que la operación de eliminación es seguida en los árboles de visualización por la operación de visualización.
Tipos de eliminaciones:
Hay dos tipos de eliminaciones en los árboles de expansión:
- Apertura de abajo hacia arriba
- Juego de arriba hacia abajo
Apertura de abajo hacia arriba
En la expansión ascendente, primero eliminamos el elemento del árbol y luego realizamos la expansión en el nodo eliminado.
Entendamos la eliminación en el árbol Splay.
Supongamos que queremos eliminar 12, 14 del árbol que se muestra a continuación:
fusionar ordenación java
- Primero, simplemente realizamos la operación de eliminación BST estándar para eliminar 12 elementos. Como 12 es un nodo hoja, simplemente eliminamos el nodo del árbol.
La eliminación aún no se ha completado. Necesitamos mostrar el padre del nodo eliminado, es decir, 10. Tenemos que realizar Ampliar(10) en el árbol. Como podemos observar en el árbol anterior, 10 está a la derecha del nodo 7 y el nodo 7 está a la izquierda del nodo 13. Entonces, primero, realizamos la rotación hacia la izquierda en el nodo 7 y luego realizamos la rotación hacia la derecha en el nodo 13, como se muestra a continuación:
Aún así, el nodo 10 no es un nodo raíz; El nodo 10 es el hijo izquierdo del nodo raíz. Entonces, necesitamos realizar la rotación derecha en el nodo raíz, es decir, 14 para convertir el nodo 10 en un nodo raíz como se muestra a continuación:
- Ahora, tenemos que eliminar el elemento 14 del árbol, que se muestra a continuación:
Como sabemos, no podemos simplemente eliminar el nodo interno. Reemplazaremos el valor del nodo usando predecesor del orden o sucesor del orden . Supongamos que usamos un sucesor de orden en el que reemplazamos el valor con el valor más bajo que existe en el subárbol derecho. El valor más bajo en el subárbol derecho del nodo 14 es 15, por lo que reemplazamos el valor 14 con 15. Dado que el nodo 14 se convierte en el nodo hoja, simplemente podemos eliminarlo como se muestra a continuación:
Aún así, la eliminación no se completa. Necesitamos realizar una operación más, es decir, expandir, en la que debemos convertir el padre del nodo eliminado en el nodo raíz. Antes de la eliminación, el padre del nodo 14 era el nodo raíz, es decir, 10, por lo que en este caso necesitamos realizar cualquier separación.
Juego de arriba hacia abajo
En la distribución de arriba hacia abajo, primero realizamos la distribución en la que se va a realizar la eliminación y luego eliminamos el nodo del árbol. Una vez eliminado el elemento, realizaremos la operación de unión.
Entendamos la distribución de arriba hacia abajo a través de un ejemplo.
Supongamos que queremos eliminar 16 del árbol que se muestra a continuación:
Paso 1: En la expansión de arriba hacia abajo, primero realizamos la expansión en el nodo 16. El nodo 16 tiene tanto padre como abuelo. El nodo 16 está a la derecha de su padre y el nodo padre también está a la derecha de su padre, por lo que esta es una situación de zag zag. En este caso, primero realizaremos la rotación hacia la izquierda en el nodo 13 y luego en el 14 como se muestra a continuación:
El nodo 16 todavía no es un nodo raíz y es un hijo derecho del nodo raíz, por lo que debemos realizar una rotación hacia la izquierda en el nodo 12 para convertir el nodo 16 en un nodo raíz.
Una vez que el nodo 16 se convierta en un nodo raíz, eliminaremos el nodo 16 y obtendremos dos árboles diferentes, es decir, el subárbol izquierdo y el subárbol derecho como se muestra a continuación:
Como sabemos, los valores del subárbol izquierdo son siempre menores que los valores del subárbol derecho. La raíz del subárbol izquierdo es 12 y la raíz del subárbol derecho es 17. El primer paso es encontrar el elemento máximo en el subárbol izquierdo. En el subárbol izquierdo, el elemento máximo es 15, y luego debemos realizar la operación de extensión en 15.
Como podemos observar en el árbol de arriba, el elemento 15 tiene un padre y un abuelo. Un nodo está a la derecha de su padre, y el nodo padre también está a la derecha de su padre, por lo que debemos realizar dos rotaciones hacia la izquierda para convertir el nodo 15 en un nodo raíz, como se muestra a continuación:
Después de realizar dos rotaciones en el árbol, el nodo 15 se convierte en el nodo raíz. Como podemos ver, el hijo derecho del 15 es NULL, por lo que adjuntamos el nodo 17 en la parte derecha del 15 como se muestra a continuación, y esta operación se conoce como unirse operación.
Nota: Si el elemento que se va a eliminar no está presente en el árbol de visualización, se realizará la visualización. La extensión se realizaría en el último elemento al que se accedió antes de alcanzar NULL.
Algoritmo de operación de eliminación
If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root
En el algoritmo anterior, primero verificamos si la raíz es nula o no; si la raíz es NULL significa que el árbol está vacío. Si el árbol no está vacío, realizaremos la operación de extensión sobre el elemento que se va a eliminar. Una vez completada la operación de expansión, compararemos los datos raíz con el elemento que se desea eliminar; si ambos no son iguales significa que el elemento no está presente en el árbol. Si son iguales, entonces pueden ocurrir los siguientes casos:
Caso 1 : La izquierda de la raíz es NULL y la derecha de la raíz se convierte en el nodo raíz.
Caso 2 : Si existen tanto la izquierda como la derecha, entonces expandimos el elemento máximo en el subárbol izquierdo. Cuando se completa la expansión, el elemento máximo se convierte en la raíz del subárbol izquierdo. El subárbol derecho se convertiría en el hijo derecho de la raíz del subárbol izquierdo.