Árboles, árboles rojos y negros

"¡Hola, amigo!"

"¡Hola, Rishi!"

"Encontré mis viejas notas allí y preparé material interesante para ti. Creo que te interesará escucharlo".

"Escuchémoslo. Siempre encuentras algo interesante que luego resulta ser muy útil".

"Está bien. Hoy quiero hablarles sobre árboles , así que comenzaré con gráficos ".

" Un gráfico es un sistema de puntos y líneas que los conectan. Los puntos se denominan vértices del gráfico y las líneas se denominan aristas del gráfico. Por ejemplo:"

"Un gráfico es muy conveniente para usar como modelo matemático para varios procesos y tareas del mundo real. Se han inventado muchas tareas y algoritmos diferentes para los gráficos, por lo que se usan con bastante frecuencia".

"Por ejemplo, supongamos que los vértices son ciudades y los bordes son caminos. Entonces, buscar el camino más corto entre ciudades se convierte en: «dada una gráfica, encuentra el camino más corto entre dos vértices». "

"Pero el camino de A a B no siempre es el mismo que el camino de B a A. Entonces, a veces se prefiere tener dos líneas diferentes. Para hacer esto, las líneas (bordes del gráfico) se reemplazan con flechas. En En otras palabras, el gráfico puede tener dos flechas: una de A a B y otra de B a A".

"Si el gráfico usa flechas, entonces se llama gráfico dirigido ; si solo tiene líneas, entonces se llama gráfico no dirigido ".

"Cada vértice puede tener su propio número de aristas. Un vértice también puede no tener ninguna arista. Por el contrario, un vértice puede estar conectado por aristas con todos los demás vértices.  Si cada par de vértices en un gráfico está conectado por una arista, entonces se llama un gráfico completo " .

"Si puede usar los bordes para llegar a todos los vértices de un gráfico, entonces se llama un gráfico conectado . Un gráfico que tiene tres vértices separados y no tiene bordes sigue siendo un gráfico, pero lo llamamos un gráfico desconectado ".

"Para formar un gráfico conectado a partir de N vértices, necesitas al menos N-1 aristas. Este tipo de gráfico se llama árbol".

"Además, generalmente se elige un vértice para que sea la raíz del árbol , y el resto se declaran ramas. Las ramas de los árboles que no tienen sus propias ramas se llaman hojas . Por ejemplo:"

"Si cada elemento del árbol tiene dos hijos, entonces se llama árbol binario . En otras palabras, puede haber 0 o 2 ramas. Puedes ver un árbol binario en la parte superior derecha".

" Se dice que un árbol es un árbol binario completo cuando cada rama tiene 2 hijos, y todas las hojas (vértices sin hijos) están en la misma fila".

"Por ejemplo:"

"¿Por qué se necesitan estos árboles?"

"Oh, los árboles se usan en muchos lugares. En general, los árboles binarios son datos estructurados ordenados".

"¿Qué es eso?"

"Sí, es muy simple. Almacenamos un cierto valor en cada vértice. Y cada elemento sigue una regla: el valor almacenado en el hijo derecho debe ser mayor que el valor almacenado en el vértice, y el valor almacenado en el hijo izquierdo debe ser menor que el valor almacenado en el vértice.  Esta ordenación permite encontrar rápidamente los elementos del árbol que necesita".

"¿Puedes aclarar lo que eso significa?"

"Los elementos del árbol generalmente se ordenan sumando. Supongamos que tenemos 7 elementos: 13, 5, 4, 16, 8, 11, 10"

"Así es como se agregan los elementos al árbol".

"Si buscamos el número 7 en este árbol, así será la búsqueda"

"0) Comience en la raíz".

"1a) ¿7 es igual a 13? No"

"1b) ¿Es 7 mayor que 13? No, entonces nos movemos al subárbol izquierdo".

"2a) ¿7 es igual a 5? No".

"2b) ¿Es 7 mayor que 5? Sí, entonces nos movemos al subárbol derecho".

"3a) ¿7 es igual a 8? No"

"3b) ¿Es 7 mayor que 8? No, entonces nos movemos al subárbol izquierdo".

"4a) No hay subárbol izquierdo, lo que significa que el número 7 no está en el árbol".

"Ah. En otras palabras, solo necesitamos verificar los vértices en el camino desde la raíz hasta la posible ubicación del número deseado. Sí, eso es realmente rápido".

"Además, si el árbol está equilibrado, solo necesitará pasar por unos 20 vértices para buscar un millón de elementos".

"Estoy de acuerdo, no son muchos".

"¿Qué quieres decir con árbol equilibrado?"

"Un árbol que no esté distorsionado, es decir, que no tenga ramas largas. Por ejemplo, si los elementos ya estuvieran ordenados cuando construimos el árbol, habríamos hecho un árbol muy largo que consistía en una sola rama " .

"Hmm. Tienes razón. Entonces, ¿qué hacemos?"

"Como probablemente ya hayas adivinado, el árbol más eficiente tiene ramas que tienen aproximadamente la misma longitud. Luego, cada comparación descarta la mayor parte del subárbol restante".

"Entonces, ¿necesitamos reconstruir el árbol?"

"Sí. Tiene que estar «equilibrado», para que se acerque lo más posible a un árbol binario completo".

"Para resolver este problema, se inventaron los árboles autoequilibrados.  Si el árbol se distorsiona después de agregar un elemento, entonces reordena los elementos ligeramente para que todo esté bien.  Aquí hay un ejemplo de equilibrio:"

"Algunos de estos árboles se conocen como árboles rojo -negros ".

"¿Por qué se llaman rojo-negro?"

"Su inventor dibujó todos los vértices usando dos colores. Un color era rojo y el otro era negro. Los diferentes vértices obedecen reglas diferentes. Esto forma la base completa para el procedimiento de balanceo".

"Por ejemplo:"

"Entonces, ¿cuáles son estas reglas?"

"1) Un vértice rojo no puede ser hijo de un vértice rojo".

"2) La profundidad negra de cada hoja es la misma (la profundidad negra se refiere a la cantidad de vértices negros en el camino desde la raíz)".

"3) La raíz del árbol es negra".

"No explicaré cómo funciona esto, probablemente tu cabeza ya esté explotando".

"Sí. Mi procesador está emitiendo un poco de humo".

"Aquí hay un enlace para ti. Si quieres, puedes leer más sobre esto aquí".

Enlace a material adicional

"Y ahora, ve a tomar un descanso".