Diferencia entre árbol B y árbol binario
Contenido
- Cuadro comparativo
- Definición de árbol B
- Propiedades del árbol B de orden M
- Definición de árbol binario
- Técnicas transversales
- Conclusión
B-tree y Binary tree son los tipos de estructura de datos no lineal. Aunque los términos parecen ser similares, pero son diferentes en todos los aspectos. Se utiliza un árbol binario cuando los registros o datos se almacenan en la RAM en lugar del disco, ya que la velocidad de acceso de la RAM es mucho mayor que la del disco. Por otro lado, el árbol B se usa cuando los datos se almacenan en el disco, reduce el tiempo de acceso al reducir la altura del árbol y aumentar las ramas en el nodo.
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 esa restricción. Un árbol binario puede tener un máximo de 2 subárboles o nodos, mientras que en el árbol B puede tener M no de subárboles o nodos donde M es el orden del árbol B.
- Cuadro comparativo
- Definición
- Diferencias clave
- Conclusión
Cuadro comparativo
| Bases para la comparación | Árbol B | Árbol binario |
|---|---|---|
| Restricción esencial | Un nodo puede tener un máximo de M número 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 RAM. |
| Altura del árbol | Iniciar sesiónMETRO N (donde m es el orden del árbol M-way) | Iniciar sesión2 norte |
| Solicitud | Estructura de datos de indexación de código en muchos DBMS. | Optimización de código, codificación Huffman, etc. |
Definición de árbol B
Un árbol B es el árbol M-way balanceado y también conocido como árbol de clasificación equilibrado. Es similar al árbol de búsqueda binario donde los nodos se organizan en función del 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 ser lo más mínima posible.
- Por encima de 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 dejar nodos.
Propiedades del árbol B de orden M
- Cada nodo puede tener un número M máximo de hijos y un 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 hijos con claves M-1 máximas.
- La disposición de las teclas está en un orden específico dentro de los nodos. Todas las claves en el subárbol presente en la izquierda de la clave son predecesoras 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 medio se inserta en el nodo primario.
- 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 puede tener un nodo es 2 y también podría haber un nodo de cero o un grado.
Hay ciertas variantes de un árbol binario, como un árbol estrictamente binario, un árbol binario completo, un á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 llama árbol binario completo cuando cumple la condición de tener 2 yo nodos en cada nivel donde i es el nivel.
- El binario roscado es un árbol binario que consta de 0 no de nodos o 2 número de nodos.
Técnicas transversales
El recorrido del árbol es una de las operaciones más frecuentes que se realiza en la estructura de datos del árbol en la que cada nodo visitó exactamente una vez de manera sistemática.
- Inorden: en este recorrido del árbol, el subárbol izquierdo se visita de forma recursiva, luego se visita el nodo raíz y en el último subárbol derecho se visita.
- Precursor: en este recorrido del árbol, se visita el nodo raíz en el primer subárbol izquierdo y luego en el subárbol derecho.
- Postorder: esta técnica visita el subárbol izquierdo, luego el subárbol derecho y, por último, el nodo raíz.
- 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 la memoria rápida como la RAM.
- Otra área de aplicación para B-tree 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, codificación de huffman, etc.
- La altura máxima de un árbol B es logMETRON (M es el orden del árbol). Por el contrario, la altura máxima del árbol binario es log2N (N es el número de nodos y la base es 2 porque es para binario).
Conclusión
El árbol B se utiliza 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 usa cuando los registros se almacenan en la RAM (pequeña y rápida) y el árbol B se usa cuando los registros se almacenan en el disco (grande y lento). Por lo tanto, el uso del árbol B en lugar del árbol binario reduce significativamente el tiempo de acceso debido al alto factor de ramificación y la altura reducida del árbol.
