Antes de entender el Árbol rojo-negro y árbol AVL diferencias, debemos conocer el árbol Rojo-Negro y el árbol AVL por separado.
¿Qué es un árbol rojo-negro?
El árbol rojo-negro es un árbol autoequilibrado. árbol de búsqueda binaria en el que cada nodo contiene un bit adicional de información que denota el color del nodo. El color del nodo puede ser Rojo o Negro, dependiendo de la información de bits almacenada por el nodo.
Propiedades
Las siguientes son las propiedades asociadas con un árbol Rojo-Negro:
- El nodo raíz del árbol debe ser negro.
- Un nodo rojo sólo puede tener hijos negros. O podemos decir que dos nodos adyacentes no pueden ser de color rojo.
- Si el nodo no tiene un hijo izquierdo o derecho, entonces se dice que es un nodo hoja. Entonces, colocamos los hijos izquierdo y derecho debajo del nodo hoja conocido como nulo
La profundidad del negro o la altura del negro de un nodo de hoja se puede definir como la cantidad de negros que encontramos cuando nos movemos del nodo de hoja al nodo raíz. Una de las propiedades clave del árbol Rojo-Negro es que cada nodo de la hoja debe tener la misma profundidad de negro.
Entendamos esta propiedad a través de un ejemplo.
En el árbol de arriba, hay cinco nodos, uno de los cuales es rojo y los otros cuatro son negros. Hay tres nodos de hojas en el árbol de arriba. Ahora calculamos la profundidad del negro de cada nodo de la hoja. Como podemos observar, la profundidad del negro de los tres nodos de las hojas es 2; por tanto, es un árbol Rojo-Negro.
Si el árbol no obedece a ninguna de las tres propiedades anteriores, entonces no es un árbol Rojo-Negro.
Altura de un árbol rojo-negro.
Considere h como la altura del árbol que tiene n nodos. ¿Cuál sería el valor más pequeño de n? El valor de n es el más pequeño cuando todos los nodos son negros. Si el árbol contiene todos los nodos negros, entonces el árbol sería un árbol binario completo. Si la altura de un árbol binario completo es h, entonces el número de nodos en un árbol es:
norte = 2h -1
¿Cuál sería el mayor valor de n?
El valor de n es mayor cuando cada nodo negro tiene dos hijos rojos, pero el nodo rojo no puede tener hijos rojos, por lo que tendrá hijos negros. De esta forma, se alternan capas de niños negros y rojos. Entonces, si el número de capas negras es h, entonces el número de capas rojas también es h; por lo tanto, la altura total del árbol es 2h. El número total de nodos es:
norte = 2*2h-1
¿Qué es el árbol AVL?
Un árbol AVL es un árbol de búsqueda binario autoequilibrado si observamos el siguiente caso, que es un árbol de búsqueda binario y un árbol equilibrado.
En el árbol anterior, la complejidad temporal en el peor de los casos para buscar un elemento es O(h), es decir, la altura del árbol. En el caso anterior, el número de comparaciones realizadas para buscar 17 elementos es 4 y la altura del árbol también es 4.
Si consideramos el árbol binario sesgado, como se muestra a continuación:
En el árbol sesgado a la derecha de arriba, el número de comparaciones realizadas para buscar 17 elementos es 5, y el número de elementos presentes en el árbol también es 5. Por lo tanto, podemos decir que si el árbol es un árbol binario sesgado, entonces la complejidad del tiempo sería O(n).
Ahora, tenemos que equilibrar estos árboles sesgados para que tengan una complejidad temporal O(h). Existe un término conocido como factor de equilibrio , que se utiliza para autoequilibrar el árbol de búsqueda binaria. El factor de equilibrio se puede calcular como:
Factor de equilibrio = altura del subárbol izquierdo-altura del subárbol derechoEl valor del factor de equilibrio podría ser 1, 0 o -1. Si cada nodo en el árbol binario tiene un valor de 1, 0 o -1, entonces se dice que ese árbol es equilibrado. árbol binario o árbol AVL.
El árbol se conoce como árbol perfectamente equilibrado si el factor de equilibrio de cada nodo es 0. El árbol AVL es un árbol casi equilibrado porque cada nodo del árbol tiene el valor del factor de equilibrio 1, 0 o -1.
Diferencias entre el árbol Rojo-Negro y el árbol AVL.
Las siguientes son las diferencias entre el árbol Rojo-Negro y el árbol AVL:
El árbol Rojo-Negro es un árbol de búsqueda binario y el árbol AVL también es un árbol de búsqueda binario.
Las siguientes reglas se aplican en un Árbol Rojo-Negro:
- El nodo en un árbol Rojo-Negro es de color rojo o negro.
- El color del nodo raíz debe ser negro.
- Los nodos adyacentes no deben ser rojos. En otras palabras, podemos decir que el nodo rojo no puede tener hijos rojos, pero el nodo negro puede tener hijos negros.
- Debería haber la misma cantidad de nodos negros en cada camino; entonces, sólo un árbol puede considerarse árbol Rojo-Negro.
- Los nodos externos son los nodos nulos, que siempre son de color negro.
Regla del árbol AVL:
Cada nodo debe tener un factor de equilibrio como -1, 0 o 1.
En la figura anterior, debemos verificar si el árbol es rojo-negro o no. Para comprobar esto, primero debemos comprobar si el árbol es un árbol de búsqueda binario o no. Como podemos observar en la figura anterior, satisface todas las propiedades del árbol de búsqueda binario; por tanto, es un árbol de búsqueda binario. En segundo lugar, tenemos que verificar si cumple o no las reglas antes mencionadas. El árbol anterior satisface las cinco reglas anteriores; por lo tanto, concluye que el árbol anterior es un árbol Rojo-Negro.
En la figura anterior, debemos verificar si el árbol es un árbol AVL o no. Como cada nodo tiene un valor de factor de equilibrio como -1, 0 o 1, es un árbol AVL.
En el caso de un árbol Rojo-Negro, si se cumplen todas las reglas anteriores, siempre que un árbol sea un árbol de búsqueda binario, entonces se dice que el árbol es un árbol Rojo-negro.
En el caso del árbol AVL, si el factor de equilibrio es -1, 0 o 1, entonces se dice que el árbol anterior es un árbol AVL.
Si el árbol no está equilibrado, se utilizan dos herramientas para equilibrar el árbol en un árbol Rojo-Negro:
Si el árbol no está equilibrado, se utiliza una herramienta para equilibrar el árbol en el árbol AVL:
En el caso del árbol Rojo-Negro, las operaciones de inserción y eliminación son eficientes. Si el árbol se equilibra mediante el cambio de color, entonces las operaciones de inserción y eliminación son eficientes en el árbol Rojo-Negro.
En el caso del árbol AVL, la operación de búsqueda es eficiente ya que solo requiere una herramienta para equilibrar el árbol.
En el caso del árbol Rojo-Negro, la complejidad temporal de todas las operaciones, es decir, inserción, eliminación y búsqueda, es O(logn).
En el caso del árbol AVL, la complejidad temporal de todas las operaciones, es decir, inserción, eliminación y búsqueda, es O(logn).
Entendamos las diferencias en la forma tabular.
columpio java
| Parámetro | árbol negro rojo | Árbol AVL |
|---|---|---|
| buscando | El árbol Rojo Negro no proporciona una búsqueda eficiente ya que los árboles Rojo Negro están aproximadamente equilibrados. | Los árboles AVL proporcionan una búsqueda eficiente ya que son árboles estrictamente equilibrados. |
| Inserción y eliminación | La inserción y eliminación son más fáciles en el árbol Rojo Negro ya que requiere menos rotaciones para equilibrar el árbol. | La inserción y eliminación son complejas en el árbol AVL ya que requiere múltiples rotaciones para equilibrar el árbol. |
| Color del nodo | En el árbol Rojo-Negro, el color del nodo es Rojo o Negro. | En el caso de los árboles AVL, no hay color del nodo. |
| factor de equilibrio | No contiene ningún factor de equilibrio. Almacena sólo un bit de información que indica el color rojo o negro del nodo. | Cada nodo tiene un factor de equilibrio en el árbol AVL cuyo valor puede ser 1, 0 o -1. Requiere espacio adicional para almacenar el factor de equilibrio por nodo. |
| Estrictamente equilibrado | Los árboles rojo-negros no están estrictamente equilibrados. | Los árboles AVL están estrictamente equilibrados, es decir, la altura del subárbol izquierdo y la altura del subárbol derecho difieren como máximo en 1. |