¿Es correcto no entender completamente los árboles RB? [cerrado]

15

¡Así que acabo de aprender los árboles rojos y negros en Cormen y wow! Normalmente, me gusta entender todos los algoritmos y estructuras de datos hasta el punto en que puedo reconstruirlos desde cero sin tener que hacer trampa mirando el pseudo código. Realmente me gustan los algoritmos, así que disfruto aprendiendo cómo funcionan y por lo general voy línea por línea e intento algunos casos mirando el código y comprobando si lo que está sucediendo es lo que entendí que debería suceder.

El solo hecho de entender lo que está pasando me tomó MUCHO tiempo para los árboles RB. Incluso con las explicaciones del libro, todavía me resultaba difícil entender el código. Sin mencionar que no pude entender cómo y por qué funcionan las rotaciones. No me parece nada intuitivo. Quiero decir, ¿los tres (seis en realidad) casos diferentes para la inserción y luego los 4 casos para la eliminación? ¿Es posible entender esto? Es imposible para mí reconstruir este código sin hacer trampa. Hasta el árbol binario podría implementar las cosas fuera de mi cabeza, con algunos ajustes siempre funcionaría, pero los árboles RB ni siquiera voy a intentarlo. Quiero decir, incluso el profesor se confundió a veces, así que supongo que no es tan fácil, pero al mismo tiempo, ¿no deberíamos tener que entender todo lo que está sucediendo o al menos por qué? El libro no explica realmente cómo a alguien se le ocurrió la idea de las rotaciones. ¿Cómo notó alguien que con 2 rotaciones podría resolver cualquier problema de inserción? ¡Eso es increíble!

Mi pregunta es, ¿realmente tengo que entender al 100% los árboles RB? Me siento un poco mal saltando cosas sin entenderlo completamente. Gracias de antemano chicos! (PD: no hay ninguna etiqueta para RB-tree, en realidad ni siquiera para tree, solo binary-tree, así que solo puse algoritmos)

    
pregunta Bernardo Pires 29.05.2011 - 22:48

6 respuestas

13

Pareces comparar la idea de "entender" con "poder escribir el código sin mirar el libro". Estas son dos cosas diferentes. Si puede ver cómo la rotación de los nodos del árbol reorganiza el árbol para mantener el equilibrio, entonces lo entiende. Ser capaz de recordar inmediatamente todos los casos para los que se aplican rotaciones no es el punto.

Yo mismo, probablemente podría averiguar las rotaciones si tuviera lápiz / papel / varias horas para jugar con él. Pero ciertamente no podría simplemente escribirlo sin pensarlo. Si realmente tuviera que escribir ese algoritmo, lo buscaría para asegurarme de que estaba obteniendo todos los detalles correctamente. Por supuesto, en casi cualquier situación usaría un código ya escrito.

Cuando todo esto se usa es cuando te encuentras con una situación que no se ajusta a ninguno de los algoritmos. Nunca necesitarás escribir tu propia implementación de árbol. Pero podría encontrarse a sí mismo, por ejemplo, necesitando aplanar una herencia de listas doblemente vinculadas. En ese caso, haber entendido la idea básica detrás de la rotación puede ser muy útil.

    
respondido por el Winston Ewert 29.05.2011 - 23:51
4

Si está familiarizado con la programación funcional, es posible que este enfoque le resulte mejor (Okasaki 1999):

enlace

Si no, al menos no se desanime con la oración inicial:

  

Todo el mundo aprende sobre árboles de búsqueda binarios equilibrados en sus   Clases introductorias de ciencias de la computación, pero incluso el corpulento   temblar ante la idea de realmente implementar tal bestia.

    
respondido por el Ryan Culpepper 30.05.2011 - 00:13
3

No es necesario que entiendas las rotaciones en detalle. Usted debería comprender la relación entre los árboles RB y los árboles 2-3-4 (consulte Sedgewick). Todas esas rotaciones locas tienen mucho más sentido cuando se las ve como árboles 2-3-4. Si su profesor no ha enseñado árboles RB como detalle de implementación para 2-3-4 árboles, probablemente debería leer algo sobre 2-3-4 árboles. (El tratamiento de Sedgewick es bastante bueno; Wikipedia no lo tiene).

Más en general, comprender los detalles de implementación de por qué funciona un algoritmo es solo a veces útil. Entender la lógica de por qué funciona el algoritmo es casi siempre útil. Por lo general, no es necesario ser capaz de crear el algoritmo, aunque cuanto más algoritmos entienda, más posibilidades tendrá.

    
respondido por el Rex Kerr 30.05.2011 - 08:40
1

Si necesita "RB Trees By Heart" para su examen la próxima semana, deberá morder la bala y aprenderlos. En ese caso, debes reconsiderar tus métodos de aprendizaje. Tal vez tratar de explicar los árboles RB a un compañero de clase te ayudará más que otra noche de escritura de código solitaria.

Si los árboles RB son una base para su próximo curso después de las vacaciones, sáltelos ahora (sin malos sentimientos) y concéntrese en el curso de este semestre. Pero mantén tus ojos bien abiertos para ver los temas que podrían prepararte para un segundo intento en RB Trees.

Si honestamente sientes que nunca los necesitarás realmente (ver el comentario de Anna Lear), dales un beso de despedida sin arrepentimiento, nadie sabe más que una gota en el mar de conocimiento (es una lástima que los maestros a menudo piensen en su caída). es lo más importante).

    
respondido por el Ekkehard.Horner 29.05.2011 - 23:52
1

La clave del éxito de la programación es nunca rendirse :

Hoy sus árboles RB mañana será algo más. La lección más importante es no darse por vencido .

Para mí, esa es una de las esencia central de la programación, no renunciar a ...

Le sugeriría que siga intentando , y cuando falle HÁGALO DE NUEVO .

  

"Hasta que llegue, hasta que haga clic, hasta que   se ejecuta. "

Porque una vez que vences las montañas, el cielo se vuelve claro. Tu mente cambia de entendimiento, estás temporalmente elevado (hasta la próxima montaña) . Esta elevación temporal vale más que todo el dinero del mundo.

    
respondido por el Darknight 30.05.2011 - 00:10
0

La mejor manera de entenderlo es probarlo :

  • Hay 3 o 6 rotaciones. Tome un pedazo de papel y escríbalos uno por uno.
  • Una vez que lo obtengas, ve e implementa un Árbol Negro Rojo. Está bien si tienes que buscar algunas cosas.

Es como lo hicimos en la universidad. Y para el examen, tenemos que explicar cómo funcionó una parte.

    
respondido por el Carra 30.05.2011 - 11:26

Lea otras preguntas en las etiquetas