Durante bastante tiempo luché con el árbol rojo-negro (en adelante, kchd ). Toda la información que encontré fue en el espíritu de "las hojas y la raíz del árbol son siempre negras PORQUE", "5 propiedades principales de un árbol rojo-negro" o "3 casos al equilibrar y 12 casos al eliminar un nodo". Este arreglo no me convenía.
No quería memorizar las propiedades del árbol, el pseudocódigo y las opciones de equilibrio, quería saber por qué. ¿Cómo ayudan los colores a equilibrar? ¿Por qué un nódulo rojo no puede tener un hijo rojo? ¿Por qué la profundidad de un árbol se mide "altura negra"?
Recibí respuestas a estas preguntas solo cuando me dieron un enlace a una conferencia sobre dos o tres árboles, con la que comenzaremos.
Este artículo se divide en 3 partes lógicas. Recomiendo leerlos en el orden en que se muestran. La primera parte (esta) estará destinada a una introducción al ccd y a conocerlo. En la segunda parte, hablaremos sobre el equilibrio y la inserción en ccd. En la tercera y última parte, analizaremos el proceso de eliminación de un nodo. Tenga paciencia y disfrute leyendo :)
Descargo de responsabilidad
En este artículo no habrá información sobre los pros y contras del árbol, su aplicación, etc .: hay mucha información sobre las asintóticas del árbol y cómo trabajar con él en Internet.
El material está destinado a quienes ya están familiarizados con las ccd y ahora quieren comprenderlas, así como a quienes recién las están conociendo.
El artículo no contendrá detalles de la implementación de la estructura.
— . .
-
- , -
, , - - , , , . - - .
- - , . - ( , ). 2-, - 3-. : . :
, .
- , - .
- - , .
, , 5. - 5 .
12. 12 (, ), "" ( , ), .. . 5-12.
. 17. . 5-12-17.
- , . ! "" . . 12, 5, - 17.
, , - . : , "" . 3 :
. , ( ).
. ( ).
. , .
.
, . 3. , . , 3 5. 3 5 . 3-5.
, :)
4 3-5. 3-4-5, , , . ? , .. "" 4 .
. , 4 , - , 4. 5. :
5 ? : - , - . 5 4, 5 , .. . 5 , "", 4-12 (, 5 , "" ).
, . :
, , .
, , , .
, , .
, . , , - . , - (, 4-5-12, , 5 4 12). , . , , ( , 7? 9?).
, , , . , , , . .
, , , . , , ( ). - .
-
, - - . - . ?
, 3-. 3- 2- . - , , , ( ), .
, , .
, - . , , ( , ).
-
, - , , 3- ( ). , , . , ( ).
1.
. , , - 3- 2-3 . , 4-, :)
2.
. , : .
3.
null- (, ) - . , . , , .
Dado que hemos tocado los nodos nulos, debe decirse que todos los nodos del árbol siempre deben tener dos descendientes, y si la referencia al descendiente es cero, entonces conduce exactamente al nodo nulo. De hecho, esto plantea una pregunta en la implementación, fue más conveniente para mí agregar un nodo nulo (menos problemas con los iteradores, el equilibrio, etc.).
Propiedad 4.
La altura del árbol se mide solo por nodos negros y se llama "altura negra". Aquí nuevamente, todo en general se vuelve obvio: el nodo rojo es solo una adición al nodo negro, es parte de él, por lo tanto, se considera que la altura se basa en nodos negros.
Con esto concluye la introducción. En la siguiente parte, hablaremos sobre cómo insertar nodos en un árbol y equilibrarlo.