¿Por qué estudiamos árboles binarios específicamente? Como en un árbol de búsqueda m-way general no se le da tanta importancia como árboles binarios en los libros de texto de DataStructure.¿Por qué son importantes los árboles binarios?
¿El uso de un árbol binario excede los árboles de m-way?
Los árboles binarios son la forma más simple de árboles multidireccionales por lo que son más fáciles de estudiar en ese sentido.
vías múltiples árboles tienen nodos que consisten en N llaves y N+1 punteros, a lo largo de las líneas de:
|
+-----+-----+-----+-----+
| k00 | k01 | k02 | k03 |
+-----+-----+-----+-----+
/ | | | \
p00 p01 p02 p03 p04
Para averiguar qué puntero a seguir en una búsqueda, se compara la clave que está buscando por contra las claves en el nodo. Ese ejemplo anterior es un árbol multidireccional de orden 2 (estoy definiendo el orden n como tener claves 2n y 2n+1 punteros).
Cuando "degenerado" a esta estructura tiene el nodo más pequeño posible, que terminan con una llave y dos punteros, el clásico árbol binario:
|
+-----+
| k00 |
+-----+
/ \
p00 p01
Cuando fui a la universidad (y voy a admitir libremente que fue hace un tiempo), estudiamos árboles binarios primero, simplemente porque los algoritmos eran elegantes. La búsqueda fue un nodo de comparación simple y selecciona uno de dos subárboles. La inserción y la eliminación también fueron relativamente fáciles.
A continuación, pasó a árboles binarios equilibrados, donde la búsqueda es exactamente el mismo, pero la inserción y deleción eran un poco más complicado, que implica 'rotación' de sub-árboles a través de la raíz sub-árbol donde sea necesario para mantenerla equilibrado.
Esto fue seguido por árboles multidireccionales no balanceados para obtener el concepto de búsqueda dentro de un nodo una vez que se ha encontrado el nodo correcto, finalmente árboles equilibrados de múltiples vías que eran básicamente los mismos que los árboles binarios pero con la misma complejidad añadida de una búsqueda secuencial, así como la inserción o eliminación dentro del nodo y la combinación y escupido de nodos.
En cada uno de esos pasos simplemente agregaste un poco más de complejidad a los algoritmos. No recuerdo que muchas personas tengan problemas con esa progresión, así que tal vez todos los libros de texto que mencionas están en el nivel inicial.
Nunca he encontrado realmente que los árboles de varias vías sean más útiles que los árboles binarios, excepto en una situación muy específica. Es cuando estás leyendo nodos del árbol desde un disco lento como el disco y has optimizado para tamaños de sector/clúster/bloque.
Desarrollamos una implementación de árbol multidireccional bajo OS/2 (que muestra mi edad aquí) que gritaba, asegurando que los nodos fueran idénticos en tamaño a los bloques de disco subyacentes. A pesar de que esto podría dar como resultado un espacio desperdiciado, las mejoras de velocidad valieron la pena.
Para las cosas en la memoria, los árboles binarios tienen todas las ventajas de varias vías sin ninguna complicación adicional (tener que combinar la búsqueda secuencial de un nodo con la selección de subárbol).
Los árboles binarios se reducen a "¿Deberíamos movernos hacia la izquierda o hacia la derecha?", Las formas múltiples son "¿Dónde está la clave en este nodo para que podamos elegir el subárbol?".
Los árboles binarios son un concepto simple, son fáciles de entender, fáciles de implementar y funcionan bien y rápido. Supongo que esto es suficiente para enseñarlos y/o usarlos.
Por ejemplo, los árboles binarios se utilizan para la clasificación de montón (Binary Heap). De esta forma se obtienen datos de clasificación muy rápidos para que el artículo más grande (o el más bajo) siempre esté en la parte delantera. Esto se usa, por ejemplo, en IA (algoritmo A *).
Una ventaja de los árboles binarios sobre los árboles 'n-arios' es que atravesarlos a menudo se reduce a un simple problema de decisión de sí/no, como en binary space partitioning.
No voy a ser demasiado techi aquí ... porque la pregunta es por qué Binary Tree tiene tanta importancia en DataStructure. Binary Tree ,, significa árbol basado en T/F, Sí/No, etc. Significa decir la combinación de Duo. Prácticamente enfrentamos la situación en la que tenemos que decidir si o no ... Verdadero o Falso. El árbol binario representa tal situación. Los softwares en los que trabajamos, son las soluciones que usarán las estructuras de datos usadas internamente para resolver los escenarios de la vida real. Es por eso que el árbol binario entra en escena y se usa comúnmente, e incluso es importante. El resto de los árboles son refinamientos adicionales o las complejidades añadidas para unirlos con las situaciones típicas. Para iniciar el árbol binario siempre es importante.
Muy extraña respuesta ... – Paul
De hecho, pero creo que es una barrera del idioma en este caso. – danieltalsky
Porque las estructuras de datos de árbol a menudo se utilizan para organizar elementos ordenados, por ejemplo: a> b> c. Si sus artículos que están insertados en los árboles están ordenados, todo lo que necesita son dos ramas en cada nodo para dividir los elementos que son más grandes en el subárbol izquierdo, y los elementos que son más pequeños en el subárbol derecho.
Es por eso que los árboles binarios son mucho más frecuentes que los árboles m-arios. ¡No tiene nada que ver con la facilidad de tomar una decisión de sí/no frente a una decisión mínima!
U puede usar B + tree para conservar el orden, por lo que podemos decir ... Binary ni siquiera se usa para pedidos :) http://en.wikipedia.org/wiki/B%2B_tree – Sumeet
Agregando a todas las respuestas anteriores, un árbol de cualquier arity puede ser representado por un árbol binario (donde el enlace izquierdo va al primer hijo del nodo, y el enlace derecho va al siguiente "hermano").
A B-Tree es una especie de árbol en forma de m. Supongo que querías decir árbol binario, ¿verdad? – Thomas
@Thomas: ouch, siempre pensé que "B-tree" era un atajo para "Binary-tree" ;; una vez más, aprendí algo respondiendo una pregunta en SO ;; Gracias ! –