¿Por qué no puede RB-Tree ser una lista?

Question

Tengo un problema con los rb-árboles. Según Wikipedia, rb necesidades de árboles para seguir el siguiente:

1. Un nodo es rojo o negro.
2. La raíz es de color negro. (Esta regla se utiliza en algunas definiciones y no a otros. Desde la raíz siempre se puede cambiar de rojo a negro, pero no necesariamente viceversa esta regla tiene poco efecto en el análisis.)
3. Todas las hojas son de color negro.
4. Los dos hijos de cada nodo rojo son de color negro.
5. Cada camino simple a partir de un nodo dado a cualquiera de sus hojas descendientes contiene el mismo número de nodos negros.

Como sabemos, una las necesidades rb-árbol que ser equilibrado y tiene la altura de O (log (n)). Pero, si insertamos un creciente serie de números (1,2,3,4,5 ...) y, teóricamente, obtendremos un árbol que se verá como una lista y tendremos la altura de O (n) con toda su nodos negro, que no contradice las propiedades rb-árbol mencionado anteriormente. Así que, ¿dónde estoy mal ??

gracias.

Answer 1

Su ejemplo contradice la propiedad número 5, así que no es un árbol Rojo-Negro válido.

El árbol que tenemos es:

b(1, nil, b(2, nil, b(3, nil, b(4, nil, b(5, nil, nil)))))

así que para llegar a las dos últimas hojas (los hijos de 5 nodo), tenemos que visitar cinco nodos negro (representado por cada b), para llegar a la hoja bajo el nodo 4 tenemos que visitar cuatro nodos negros, etc. . esto significa que hay caminos sencillos de la raíz a algunos de estos descendientes que contienen un número diferente de nodos negros, que invalida propiedad 5.

Answer 2

Un poco más abajo en el artículo :

  

Inserción comienza añadiendo el nodo   tanto como la inserción árbol binario de búsqueda   hace y coloreando de rojo .