Duda conceptual

[IgnacioHqz]

Hola, estudiando la materia de los árboles me confundí un poco con el concepto de hoja.
Para todos los árboles una hoja es el nodo que no tiene más hijos verdad? Y en el caso de los árboles rojo-negro el nodo hoja también sería el nodo que no tiene más hijos o es el nodo negro que está vacío? (es decir, que no tiene valor pero sabemos que es negro)
Si me pudieran aclarar el concepto se los agradecería ya que me empecé a confundir con lo que he encontrado en internet.

Muchas gracias!

[Bjnazar]

Hola, estudiando la materia de los árboles me confundí un poco con el concepto de hoja. Para todos los árboles una hoja es el nodo que no tiene más hijos verdad? Y en el caso de los árboles rojo-negro el nodo hoja también sería el nodo que no tiene más hijos o es el nodo negro que está vacío? (es decir, que no tiene valor pero sabemos que es negro) Si me pudieran aclarar el concepto se los agradecería ya que me empecé a confundir con lo que he encontrado en internet.

Muchas gracias!

Hola!

La respuesta puede depender del contexto en el que se esté usando. Para efectos de prueba, si es que te llegas a complicar con el tema, puedes preguntarlo.

Para que puedas comprender un poco más, aquí va una explicación:

En el caso de árboles binarios de búsqueda, se vio en clases que un nodo sin punteros descendientes, i.e. sin hijos, se conoce como hoja.

Según el libro guía en la sección 13. Red-Black Trees (Introduction_to_algorithms) , en el caso de los árboles rojo-negro, si el hijo o el padre de un nodo no existe, el puntero correspondiente contiene el valor NIL. Una manera de pensarlo es tratarlos como punteros a nodos externos del árbol, que no contienen llave ni información, y solo sirven para mostrar el fin de una rama, marcando el límite del árbol.

También, el libro indica que los árboles rojo-negro cumplen la propiedad de que cada hoja (NIL) es negra, ayudando al balance del árbol y que todos los caminos desde un nodo a sus descendientes tengan el mismo número de nodos negros. De la misma manera, en clases se indicó que las hojas vacías se consideran nodos negros.

En este sentido, el libro muestra 3 maneras de representar un árbol rojo negro. La manera a) es efectivamente mostrando cada hoja como NIL. La manera b) reemplaza todas esas hojas por un único nodo NIL. Por último, está la manera c), que es la que usamos en general para representar los árboles rojo negro. Esta manera simplemente omite las hojas y el padre de la raíz.

Espero haberte ayudado!
Cualquier duda me cuentas