Árbol rojo y negro
Los árboles rojos y negros son árboles que a menudo se mencionan en estructuras de datos y algoritmos, pero no pueden explicarse en detalle. También son árboles que a menudo se solicitan en entrevistas técnicas. Sin embargo, ya sean los materiales en libros o en línea, generalmente son más rígidos y difíciles de entender. ¿Puedes entender los árboles rojos y negros de una manera más intuitiva? Este artículo explicará las operaciones de inserción y eliminación de árboles rojos y negros de manera gráfica.
Aprender la estructura del árbol es un proceso progresivo. Los árboles con los que generalmente entramos en contacto son árboles binarios. En términos simples, cada nodo no hojado tiene y solo dos niños, llamados el niño izquierdo y el niño derecho. Hay un tipo especial de árbol en un árbol binario llamado árbol de búsqueda binario. Un árbol de búsqueda binario es un árbol ordenado. Para cada nodo no hojado, el valor de su subárbol izquierdo es más pequeño que él, y el valor de su subárbol derecho es mayor que el de él. Un paso más que un árbol de búsqueda binario es un árbol de balance binario. Además de garantizar el orden, el árbol de balance binario también puede mantener la diferencia de altura entre los subárboles izquierdo y derecho de cada nodo y no más de 1.
Un árbol rojo y negro es un árbol de búsqueda binario, pero agrega un bit de almacenamiento a cada nodo para representar el color del nodo, que puede ser rojo o negro. Al limitar cómo cada nodo está sombreando en cualquier camino desde la raíz hasta la hoja, el árbol rojo-negro asegura que ningún camino sea el doble que los otros caminos, acercándose al equilibrio.
El árbol rojo y negro satisface 5 propiedades:
Tenga en cuenta que en un árbol rojo-negro, apunte al niño del nodo de la hoja del árbol binario tradicional a nulo, y llame a Nil el nodo de la hoja en el árbol rojo-negro. El nodo nil contiene un puntero al nodo principal, que puede ser la razón por la cual se necesita cambiar a Null a nulo.
1. Insertar operación
Primero, inserte el nuevo nodo en la forma de insertar el árbol de búsqueda binario (los nuevos nodos insertados están todos en los nodos de la hoja) y dibujándolo en rojo. Luego, vuelva a dibujar su color o gire para mantener las propiedades del árbol rojo y negro. El ajuste se divide en las siguientes tres situaciones:
1 nuevo nodo n no tiene nodo principal (es decir, se encuentra en la raíz)
Pinte el nuevo nodo n como negro.
2 El nodo principal P del nuevo nodo n es negro
No hay necesidad de ajustar.
3 El nodo principal P del nuevo nodo n es rojo
Debido a que el árbol rojo y negro no permite dos nodos rojos consecutivos (propiedad 4), debe ajustarse. Según el color del nodo del tío de N, se divide en dos situaciones: (Tomamos el nodo principal de N como el niño izquierdo como ejemplo, y P como el niño correcto como una situación similar, por lo que no lo explicaré en detalle)
3.1 El nodo del tío U del nuevo nodo n es rojo. El nodo P y el nodo del tío U del nuevo nodo N están pintados como negros, y el nodo del abuelo G está pintado como rojo, para asegurarse de que el número de nodos negros contenidos en el camino de G a cada nodo nulo sea consistente con el original. Pero dado que convertimos G en rojo, si el padre de G también es rojo, puede conducir a dos nodos rojos consecutivos (violando la naturaleza 4), por lo que es necesario volver a verificar si G viola la naturaleza del árbol rojo y negro.
3.2 El nodo del tío U del nuevo nodo n es negro. Si el nuevo nodo n es el hijo izquierdo de su nodo principal P: dibuje su nodo principal P como negro, dibuje su nodo de abuelo G como rojo y luego gire G recto una vez.
Si el nuevo nodo N es el niño derecho de su nodo principal P: realice una rotación izquierda en su nodo principal, el problema se transformará en la situación del niño izquierdo.
2. Eliminar operación
El método en "Introducción a los algoritmos" y Wikipedia es eliminar un nodo negro D, "empujar hacia abajo" el negro de D a su nodo infantil C, es decir, C tiene una capa adicional de negro además de su propio color, y luego continúa moviendo la capa adicional de negro a lo largo del árbol hasta que entra un nodo rojo, y se convierte en un negro para asegurarse de que el número de nodos negros en el camino no se mueva en el camino o se mueva a la raíz o se mueva a la raíz o se mueva a la raíz de la raíz o se mueva a la raíz de la raíz o se mueva en el camino de la ruta, no se mueva en el camino de la ruta, no se mueva en el camino de la ruta. Árbol, de modo que el número de nodos negros en todos los caminos se reduce en uno y permanece igual. Durante el movimiento ascendente, es posible que se deben rotar y modificar algunos colores del nodo para garantizar que el número de nodos negros en la ruta permanezca sin cambios.
Este enfoque puede ser beneficioso para la implementación del código (que puede usarse de manera iterativa), pero no es conveniente entender (creo personalmente). Con el propósito de comprender la prioridad, hice la siguiente clasificación en función de si el niño del nodo eliminado D es nulo:
1 Ambos niños cuyo nodo D fue eliminado son nulos
1.1 Si el nodo Deletido D es rojo, simplemente reemplace D con nulo.
1.2 El nodo Deletido D es negro (tomemos D como ejemplo)
1.2.1 Ambos hijos del nodo B, cuyo hermano D, fueron eliminados, son nulos
El nodo hermano B de D está pintado como rojo y el nodo principal P está pintado como negro.
Medio rojo y mitad negro en la figura significa que el nodo puede ser rojo o negro. Si P resultó ser rojo, el número de nodos negros en la ruta después de la modificación es el mismo que antes de la eliminación D; Si P resultó ser negro, la eliminación de D dará como resultado un número menos de nodos negros en la ruta que antes de la eliminación, por lo que debe continuar verificando si el cambio en el número de nodos negros en el camino que pasa a través de P afecta las propiedades del árbol rojo y negro.
1.2.2 El nodo hermano B del nodo D tiene un hijo, no nulo
El niño debe estar rojo, de lo contrario, el número de nodos negros en el camino desde el nodo principal de D hasta cada nodo de hoja variará (violación 5).
Si este niño es el niño derecho, dibuje el niño derecho de B como negro, dibuje B como el color original de su nodo principal P, dibuje P como negro y luego gire P con una izquierda.
Si este niño es el niño izquierdo, dibuje al niño izquierdo de B como negro, B como rojo y luego gire B a la derecha una vez, el problema se transformará en la situación del niño derecho.
1.2.3 Ambos hijos del nodo B, que han sido eliminados, no son nulos
Si B es rojo, entonces los dos hijos de B deben ser negros. Dibuje B como negro, el niño de la izquierda de B como rojo, y luego realice una rotación izquierda de P.
Si B es negro, entonces los dos hijos de B deben ser rojos. Dibuje el nodo principal de B como negro, el niño derecho de B como negro, el color original de B como su nodo principal P, y luego gire P con una izquierda.
2 Ambos niños cuyo nodo D fue eliminado no son nulos
Según el árbol de búsqueda binario para eliminar los nodos, encuentre los nodos sucesores de D, intercambie el contenido de D y S (el color permanece sin cambios), y el nodo eliminado se convierte en S. Si S tiene un nodo que no es nulo, luego continúe reemplazando S con el nodo sucesor de S hasta que ambos niños del nodo eliminado son nil. El problema se convierte en la situación en la que ambos niños del nodo eliminado D son nulos.
3 El nodo eliminado D tiene un hijo, no nulo
Este niño C debe ser un nodo rojo, de lo contrario, el número de nodos negros en la ruta de D a cada nodo nulo será diferente (violación 5).
El contenido de D y C se intercambia (el color sigue siendo el mismo), el nodo eliminado se convierte en C y el problema se convierte en la situación en la que ambos niños del nodo eliminado D son nulos.
Recorrido de árboles binarios
Hay tres tipos de transversales en los árboles binarios: anticipado por pedido, transversal medio y atravesante posterior. Hay dos tipos de implementaciones transversales: recursión e iteración. En este artículo, discutiremos cómo usar un código más elegante para implementar el recorrido de los árboles binarios.
Primero, definiré un nodo de un árbol binario:
clase pública treeNode {int val; TreeNode izquierda; TreeNode derecho; public treeNode (int x) {val = x; }}
1. Recorrido por adelantado
En pocas palabras, el recorrido por adelantado es acceder primero al nodo principal, luego acceder al niño izquierdo y finalmente acceder al niño derecho, es decir, atravesar el orden de los padres, izquierda y derecha.
La implementación recursiva es muy simple, el código es el siguiente:
Solución de clase pública {list <Integer> result = new ArrayList <Integer> (); Lista pública <integer> PreorderTraversal (treeNode root) {dfs (root); resultado de retorno; } private void dfs (treeNode root) {if (root == null) {return; } resultado.Add (root.val); dfs (root.left); dfs (root.right); }} La implementación iterativa requiere una pila para almacenar el nodo correcto al que no se accede. El código es el siguiente:
Solución de clase pública {Lista pública <Integer> PreorderTraversal (treeNode root) {list <integer> result = new ArrayList <Integer> (); if (root == null) {return resultado; } Pila <reeNode> stack = new Stack <TeNode> (); stack.push (raíz); while (! stack.isEmpty ()) {treeNode Curr = stack.pop (); resultado.Add (Curr.Val); if (Curr.right! = Null) {stack.push (Curr.right); } if (Curr.left! = NULL) {stack.push (Curr.left); }} Resultado de retorno; }}
2. Inordenado
En pocas palabras, el recorrido del orden medio es acceder primero al niño izquierdo, luego acceder al nodo principal y finalmente acceder al niño derecho, es decir, transversal en el orden de izquierda, padre y derecha.
El código recursivo también es más fácil, como se muestra a continuación:
Solución de clase pública {Public List <Integer> InFORDERTRAVERSAL (TreeNode Root) {list <Integer> result = new ArrayList <Integer> (); recurse (raíz, resultado); resultado de retorno; } private void recurse (treeNode root, list <integer> resultado) {if (root == null) return; recurse (root.left, resultado); resultado.Add (root.val); recurse (raíz. derecho, resultado); }} El método de escritura anterior es diferente del código recursivo de recorrido por adelantado. Utilizamos variables de miembros para almacenar los resultados del recorrido en el recorrido por pedido, y aquí usamos parámetros de método para guardar los resultados de la transferencia. Ambos métodos de escritura están bien, usa lo que quieras.
La implementación iterativa del recorrido de orden medio no es tan simple como el recorrido por adelantado. Aunque también requiere una pila, las condiciones para la terminación iterativa son diferentes. Imagine que para un árbol binario, el nodo al que accedemos primero es su nodo más izquierdo. Por supuesto, podemos llegar a su nodo más izquierdo a través de un bucle de tiempo, pero cuando recurrimos, ¿cómo sabemos si se ha accedido al niño izquierdo de un nodo? Utilizamos una variable CURR para registrar el nodo accedido actualmente. Cuando hemos accedido al nodo derecho de un subárbol, debemos recurrir al nodo principal del subárbol. En este momento, Curr es nulo, por lo que podemos usar esto para distinguir si se ha accedido al subárbol izquierdo de un nodo. El código es el siguiente:
Solución de clase pública {Public List <Integer> InFORDERTRAVERSAL (TreeNode Root) {list <Integer> result = new ArrayList <Integer> (); Pila <reeNode> stack = new Stack <Teenode> (); TreeNode Curr = root; while (curr! = null || Curr = Curr.Lft; } curr = stack.pop (); resultado.Add (Curr.Val); Curr = Curr.right; } resultado de retorno; }}
3. Postorder transversal
En pocas palabras, el recorrido posterior al orden es acceder primero al niño izquierdo, acceder al niño derecho y finalmente acceder al nodo principal, es decir, transversal en el orden de izquierda, derecha y padre.
Al imitar el recorrido del orden medio, puede escribir fácilmente una implementación recursiva del recorrido posterior al orden:
Solución de clase pública {Lista pública <Integer> PostOrderTraversal (treeNode root) {list <integer> result = new ArrayList <Integer> (); recurse (raíz, resultado); resultado de retorno; } private void recurse (treeNode root, list <integer> resultado) {if (root == null) return; recurse (root.left, resultado); recurse (raíz. derecho, resultado); resultado.Add (root.val); }} La iteración del recorrido posterior al orden también requiere una identificación para distinguir si se ha accedido a los niños izquierdo y derecho de un nodo. Si no, se accederá a los niños izquierdo y derecho a su vez. Si se ha accedido, se accederá al nodo. Para este fin, utilizamos una variable previa para representar el nodo que visitamos. Si el nodo que visitamos es el niño izquierdo o derecho del nodo actual, significa que se ha accedido a los niños izquierdo y derecho del nodo actual, y luego podemos acceder al nodo. De lo contrario, necesitamos ingresar a los niños izquierdo y derecho para acceder a él a su vez. El código es el siguiente:
Solución de clase pública {Lista pública <integer> PostOrderTraversal (treeNode root) {list <Integer> result = new LinkedList <Integer> (); Pila <reeNode> stack = new Stack <Teenode> (); if (root! = null) stack.push (raíz); TreeNode pre = raíz; while (! stack.isEmpty ()) {treeNode Curr = stack.peek (); if (Curr.left == Pre || Curr.right == Pre || (Curr.Left == NULL && Curr.Right == NULL)) {resultado.Add (Curr.val); stack.pop (); pre = Curr; } else {if (Curr.right! = null) stack.push (Curr.right); if (Curr.left! = NULL) Stack.push (Curr.Left); }} Resultado de retorno; }} Hay otra implementación relativamente simple de la iteración del recorrido posterior al orden. Sabemos que el orden del recorrido por adelantado es padre, izquierda y derecha, mientras que el orden del recorrido posterior al pedido es de izquierda, derecha y padre. Entonces, si modificamos ligeramente el recorrido por adelantado y lo cambiamos al orden del padre, derecha y izquierda, entonces es justo lo opuesto al orden del recorrido posterior al pedido. Después de acceder a él en este orden, podemos invertir el resultado de acceso en el final. La implementación iterativa del recorrido por adelantado es relativamente fácil. Según el método de escritura anterior, podemos implementarlo de la siguiente manera:
Solución de clase pública {Lista pública <integer> PostOrderTraversal (treeNode root) {list <Integer> result = new LinkedList <Integer> (); Pila <reeNode> stack = new Stack <Teenode> (); if (root! = null) stack.push (raíz); while (! stack.isEmpty ()) {treeNode Curr = stack.pop (); resultado.Add (Curr.Val); if (Curr.left! = NULL) Stack.push (Curr.Left); if (Curr.right! = null) stack.push (Curr.right); } Colección.reverse (resultado); resultado de retorno; }}
4. Resumen
La implementación recursiva de los tres recorridos es fácil. Es mejor escribir la implementación de iteración del recorrido por preorden, y solo se necesita una pila; El recorrido de orden medio es el más difícil. Además de determinar si la pila está vacía, la condición del bucle también debe determinar si el nodo actual está vacío para indicar si el subárbol izquierdo ha sido atravesado; Si la iteración de la transversal posterior se convierte en la iteración transversal de pedido anticipado, es mucho más fácil. De lo contrario, también es necesario registrar el nodo de acceso anterior para indicar si se ha accedido a los subárboles izquierdo y derecho del nodo actual.