Al convertir a un árbol rojo-negro, ¿hay alguna razón para elegir una forma sobre otra?

Question

Tengo una biblioteca de lista enlazada / métodos árbol binario para su uso cuando los contenedores estándar no encajan - por ejemplo, Cuando hay diferentes tipos de nodos, o cuando necesito convertir de árbol binario para enumerar y viceversa. Incluye manejo de árbol rojo-negro.

Uno de los métodos se convierte de una lista de doble ligado a un árbol binario sencillo perfectamente equilibrada en el tiempo O(n) (dado que el número de elementos se conoce de antemano). El algoritmo se conoce como "plegado" - que es el segundo medio de un algoritmo de reequilibrio árbol binario que una vez que se publicó en el Dr. Dobbs. Los pasos son básicamente ...

• Dado el tamaño del árbol, acerca de los tamaños de los subárboles izquierdo y derecho

• Recurse para el subárbol izquierdo

• Pop un nodo de la lista para su uso como la raíz

• Recurse para el subárbol derecho

• Enlace los subárboles de la raíz

También tengo un método similar que crea un árbol rojo-negro. El principio es el mismo, pero la recursividad no pierde de vista la altura del nodo - altura cero nodos se crean rojo, todas las demás son de color negro. El cálculo de la altura de partida se basa en el conjunto de bits más alta en el tamaño del árbol, y se fiddled de modo que un árbol de tamaño perfectamente equilibrado (2^n)-1 tiene sólo nodos negros (la recursión sólo va hacia abajo a la altura de uno).

El punto aquí es que sólo tengo nodos rojos en el nivel de hoja, y un máximo de precisión mitad de los nodos son rojos.

La cosa es que, si bien esto es una forma sencilla de generar un árbol rojo-negro válida, no es la única opción. Evitando tener todas las hojas de color rojo en un árbol perfectamente balanceado fue una elección arbitraria. Podría tener capas alternas de nodos rojos y negros. O podría reducir el número de nodos rojos drásticamente en algunos casos mediante la detección de los subárboles que son perfectamente equilibrado y (si es necesario nodos rojo) haciendo la raíz subárbol rojo en vez de todas sus hojas.

La pregunta es - ¿hay alguna razón práctica para elegir una forma de árbol rojo-negro válida sobre otro

Esto es pura curiosidad - Sé que no tengo ninguna razón práctica? -, pero ¿alguien sabe de una aplicación especializada en esta elección es significativa

Answer 1

En el análisis estándar del costo amortizado de la modificación de árboles rojo-negro utilizando el método de la pysicist, nodos negros con cero o dos niños de color rojo se les asigna un potencial positivo de uno, lo que significa que representan lugares problemáticos en el árbol donde supletoria puede ser necesario hacer el trabajo. nodos linfáticos rojas y negras con exactamente un niño de color rojo se les asigna un potencial de cero.

Por lo tanto, para reducir el costo de las modificaciones, dar a cada nodo de un niño negro rojo.

---

La razón ¿Por qué nodos negros con un niño de color rojo son bendecidos se explica mejor por analogía redundantes números binarios. primero voy a explicar cómo se relacionan los árboles rojo-negro a números binarios y luego voy a explicar por qué los nodos de una red-niño son útiles.

Como ya sabrán, árboles rojo-negro son una forma de representar árboles 2-4, en el que cada camino simple de la raíz a una hoja tiene la misma longitud, pero nodos con 2, 3 o 4 niños. El algoritmo más simple para añadir o eliminar un nodo en un árbol 2-4 es el mismo algoritmo que sumar o restar una de un número binario redundante .

A número binario redundante es un número en el que el dígito ITH representa 2 ⁱ , al igual que en un número binario estándar, pero el dígito ITH puede ser 0, 1, o 2 . Se les llama redundante porque hay varias maneras de escribir un número dado. 4 _diciembre se puede escribir 100 o 20 o 12.

Para añadir una a un número binario redundante, incrementar el dígito menos significativo; si es 3, configurarlo para 1 e incrementar el siguiente dígito menos significativo, y así sucesivamente. El algoritmo se detiene cuando encuentra un 0 o 1.

Para añadir una hoja de un árbol 2-4, añadir un niño a su padre previsto. Si el padre cómo tiene cinco hijos, dividirlo en dos nodos y hacerlos hijos de su padre. Continúe hasta llegar a un nodo que no necesita la división. Por lo tanto, el camino hacia la raíz se detiene cuando encuentra un nodo con dos o tres hijos.

Para unido el coste amortizado de incrementar un número binario redundante, utilice el método físicos y asignar un potencial de 1 a cada 2 dígitos. Un XALL a incremento que toca k dígitos comunicados de K-1 potencial, dándole un coste amortizado de O (1).

Este análisis es similar al coste amortizado de incrementar un número binario estándar, pero un número binario estándar no puede soportar tanto incremento y decremento en O (1) amortizado: considerar 2 ^k - 1. es k 1 dígitos. cuesta Incremento Θ (k). Si que es seguido por una disminución, cuesta a la par Θ (k) y eleva el número de nuevo a su antiguo estado.

binaria redundante es especial en que 1 dígitos detener las operaciones en cascada de ambos incremento y decremento. 2-4 árboles son especiales en que el 3-nodos detener las operaciones en cascada de ambos de inserción y supresión.

En árboles rojo-negro, un nodo con un niño rojo solo es una representación de un 3-nodo en un árbol 2-4. Estos nodos son especiales y robusto frente a inserciones o eliminaciones en sus sub-estructuras, por lo que debería favorecer a ellos en la construcción de árboles rojo-negro que va a ver una gran cantidad de cambios.

Si sabe que va a ver sólo inserciones, favorecer a los nodos con dos niños negros. Si sabe que va a ver sólo elimina, favorecer a los nodos con dos niños de color rojo.

Answer 2

La respuesta corta es: Depende

.

Básicamente, cualquier árbol válida será suficiente. Sin embargo, en términos de amortizado análisis - que podría ser muy posiblemente que usted tendrá que elegir la la mayor parte de árbol correcto que a la larga le dará el comportamiento más optimizado.

por ejemplo. si siempre elegir un árbol válida, pero que es propenso a una gran cantidad de operaciones de equilibrado, obtendrá un mal desempeño amortizado. Un ejemplo obvio es un árbol completamente negro, que es perfectamente válido, sin embargo, realiza mal cuando modificado.

Depende, porque esto generalmente será de aplicación específica.