Otra diferencia entre el árbol B y el árbol binario es que el árbol B debe tener todos sus nodos secundarios en el mismo nivel, mientras que el árbol binario no tiene tal restricción. Un árbol binario puede tener un máximo de 2 subárboles o nodos, mientras que en B-tree puede tener M no de subárboles o nodos donde M es el orden del B-tree.
Gráfica comparativa
| Bases para la comparación | Árbol B | Árbol binario |
|---|---|---|
| Restricción esencial | Un nodo puede tener un número M máximo de nodos secundarios (donde M es el orden del árbol). | Un nodo puede tener un máximo de 2 subárboles. |
| Usado | Se utiliza cuando los datos se almacenan en el disco. | Se utiliza cuando los registros y los datos se almacenan en la memoria RAM. |
| Altura del arbol | log M N (donde m es el orden del árbol M-way) | log 2 N |
| Solicitud | Código de indexación de la estructura de datos en muchos DBMS. | Optimización de código, codificación Huffman, etc. |
Definición de árbol B
Un árbol B es el árbol de forma M equilibrado y también conocido como el árbol de clasificación equilibrado. Es similar al árbol de búsqueda binario donde los nodos se organizan en base al recorrido transversal. La complejidad espacial del árbol B es O (n). La complejidad del tiempo de inserción y eliminación es O (log n).
Hay ciertas condiciones que deben ser ciertas para un árbol B:
- La altura del árbol debe quedar lo mínimo posible.
- Sobre las hojas del árbol, no debe haber subárboles vacíos.
- Las hojas del árbol deben venir al mismo nivel.
- Todos los nodos deben tener el menor número de hijos, excepto los nodos que dejan.
Propiedades del árbol B de orden M
- Cada nodo puede tener el número M máximo de hijos y el número M / 2 mínimo de hijos o cualquier número desde 2 hasta el máximo.
- Cada nodo tiene una clave menos que los niños con claves M-1 máximas.
- La disposición de las claves está en algún orden específico dentro de los nodos. Todas las claves en el subárbol presente a la izquierda de la clave son antecesoras de la clave, y las presentes en la derecha de la clave se denominan sucesores.
- En el momento de la inserción de un nodo completo, el árbol se divide en dos partes, y la clave con el valor de la mediana se inserta en el nodo principal.
- La operación de fusión tiene lugar cuando se eliminan los nodos.
Definición de árbol binario
Un árbol binario es una estructura de árbol que puede tener como máximo dos punteros para sus nodos secundarios. Significa que el grado más alto que un nodo puede tener es 2 y podría haber un nodo de cero o de un grado también.
Existen ciertas variantes de un árbol binario, como el árbol estrictamente binario, el árbol binario completo, el árbol binario extendido, etc.
- El árbol estrictamente binario es un árbol donde cada nodo no terminal debe tener subárbol izquierdo y subárbol derecho.
- Un árbol se denomina árbol binario completo cuando cumple la condición de tener 2 nodos en cada nivel donde i es el nivel.
- Binario con hilos es un árbol binario que consta de 0 no de nodos o 2 de nodos.
Técnicas de travesía
El recorrido del árbol es una de las operaciones más frecuentes realizadas en la estructura de datos de árbol en la que cada nodo visitó exactamente una vez de manera sistemática.
- Inorder: en este recorrido de árbol, se visita el subárbol izquierdo de forma recursiva, luego se visita el nodo raíz y en el último subárbol derecho se visita.
- Preorer: en este recorrido de árbol, el nodo raíz se visita en el primer subárbol izquierdo y en el último subárbol derecho.
- Orden posterior: esta técnica visita el subárbol izquierdo y luego el subárbol derecho y en el último nodo raíz.
Diferencias clave entre árbol B y árbol binario
- En el árbol B, el número máximo de nodos secundarios que puede tener un nodo no terminal es M, donde M es el orden del árbol B. Por otro lado, un árbol binario puede tener como máximo dos subárboles o nodos secundarios.
- El árbol B se usa cuando los datos se almacenan en el disco, mientras que el árbol binario se usa cuando los datos se almacenan en una memoria rápida como RAM.
- Otra área de aplicación para el árbol B es la estructura de datos de indexación de código en DBMS, en contraste, el árbol binario se emplea en la optimización de código, la codificación de Huffman, etc.
- La altura máxima de un árbol B es el registro M N (M es el orden del árbol). En contra, la altura máxima del árbol binario es log 2 N (N es el número de nodos y la base es 2 porque es para binario).
Conclusión
El árbol B se usa sobre el árbol de búsqueda binario y binario, la razón principal detrás de esto es la jerarquía de memoria donde la CPU está conectada a la caché con los canales de alto ancho de banda, mientras que la CPU está conectada al disco a través del canal de bajo ancho de banda. Un árbol binario se utiliza cuando los registros se almacenan en la RAM (pequeño y rápido) y el árbol B se usa cuando los registros se almacenan en el disco (grande y lento). Por lo tanto, el uso de árbol B en lugar de árbol binario reduce significativamente el tiempo de acceso debido al alto factor de ramificación y la altura reducida del árbol.
