Julio Tentor, estoy encantado con tus video tutoriales, quisiera profundizar más sobre el tema, así que podrías recomendarme libros (mejor si son rigurosos matemáticamente) Gracias de antemano.
Estimado, los siguientes son enlaces a mi drive - biblioteca personal que comparto con mis estudiantes Enlaces a publicaciones de los investigadores:Árboles AVL - Adelson-Velsky, Gregory M and Landis, Evgenii M. 1962. An Algorithm for the Organization of Information drive.google.com/file/d/0Bxp_37sBXIrlLU10a0xrM0Z3Y0k/view?usp=sharing Árboles Rojo-Negro - Bayer, Rudolf. 1971. Symetric Binary B-Trees Data Structure and Algorithms for Random and Sequential Information Processing drive.google.com/file/d/0Bxp_37sBXIrlbEFWQ1lURUlmX2s/view?usp=sharing La version más conocida - Guibas, Leo J. and Sedgewick, Robert 1978. A Dichromatic Framework for Balanced Trees drive.google.com/file/d/0Bxp_37sBXIrlVlJfTHdpZ0Y5MlU/view?usp=sharing Árboles B - Bayer, Rudolf and McCreight, Edward M. 1972. Organization and Maintenance of Large Ordered Indexes drive.google.com/file/d/0Bxp_37sBXIrlX3BkdEdqTkNid2c/view?usp=sharing Enlaces a libros: Capítulos 6 al 9 de Morin, Pat. 2013. Open Data Structures (in C++) drive.google.com/file/d/0Bxp_37sBXIrlbFRRM3puWjRlU1k/view?usp=sharing En Java Morin, Pat. 2013. Open Data Structures (in Java) drive.google.com/file/d/0Bxp_37sBXIrlWl9zT2hVQk9BOE0/view?usp=sharing En pseudocódigo Morin, Pat. 2013. Open Data Structures (in pseudocode) drive.google.com/file/d/0Bxp_37sBXIrlOURpYkI3c1Y5N1E/view?usp=sharing Capítulo 18 de Cormen, Thomas H, et al. 2009. Introduction to Algorithms. 3rd Edition drive.google.com/file/d/0Bxp_37sBXIrlemhSd1ZtQkk5VWM/view?usp=sharing Capítulos 16 y 17 de Joyanes Aguilar, Luis, Sánchez García, Lucas and Zahonero Martínez, Ignacio. 2007. Estructura de datos en C++ drive.google.com/file/d/0Bxp_37sBXIrlSHFza3BlRWttQ3c/view?usp=sharing Capítulo 5 de Aho, Alfred V and Ullman, Jeffrey D. 1994. Foundations of Computer Science. C Edition drive.google.com/file/d/0Bxp_37sBXIrldk5XMzZmUUNuUHM/view?usp=sharing El siguiente tema que debes desarrollar y aprender es el de grafos, capítulos 22 al 26 de Cormen, Thomas H, et al. 2009. Introduction to Algorithms. 3rd Edition drive.google.com/file/d/0Bxp_37sBXIrlemhSd1ZtQkk5VWM/view?usp=sharing Espero que sirva, estoy a tu disposición.
Estamos analizando el nodo P, la subrama que nace en el nodo K tiene una altura de K + L + lo que mide subarbol C + M; en tanto la rama que nace en el nodo Q tiene Q + lo que mide E. Gráficamente se intenta mostrar que lo que mide E es uno mas que lo que mide L + lo que mide C +M; entonces cuando se extrae el nodo M se pierde el balance porque pasa de 1 a 2. Lo que vos estas observando como la más izquierda que sería el subarbol A efectivamente tiene una diferencia de 2 con el subarbol E, pero mientras existas el nodo M ese arbol está balancedado, cuando lo extraen se pierde el balance. Espero que te sirva .
+brayan madman Efectivamente, si consideramos la altura de un árbol como el número de enlaces de la rama más larga entonces tienes razón, pero también se puede considerar que es el número de nodos de la rama más larga, la cuestión es que entre una y otra definición la diferencia es uno, porque dados dos nodos solo hay un enlace. La definición matemática de altura de un árbol se encuentra en discusión justamente porque resulta “conveniente” que sean enlaces o que sean nodos para demostrar ciertas propiedades con mayor o menor dificultad. En informática no nos interesa el valor exacto de la altura, lo que nos interesa es la forma en que crece con el tiempo a medida que se agregan o quitan elementos al árbol y en realidad los árboles auto balanceados utilizan un valor relativo, es decir un valor que resulta de comparar la altura del subárbol izquierdo con el derecho de modo que en ese caso contar enlaces o contar nodos es lo mismo porque la comparación anula las diferencias que surgen de la definición matemática. Eso se comenta en el video en el que introduje el concepto de árbol binario ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-86dmqbBaWig.htmlm19s Gracias por tu comentario, ayuda a dejar las cosas más claras.
