Estructura de datos
Enviado por Daniela Cocio Hernández • 19 de Diciembre de 2020 • Informes • 543 Palabras (3 Páginas) • 1.258 Visitas
Árboles
Daniela Cocio Hernández
Estructura de datos
Instituto IACC
21 de diciembre
Desarrollo
- Usando los siguientes datos construya un árbol binario de búsqueda y grafíquelo utilizando la herramienta que estime conveniente e insértelo en su documento (describa paso a paso su construcción)
Nodos: 22, 15, 3, 8, 40, 45, 13, 20, 30, 1, 7, 34, 48, 53, 9, 23, 12, 51, 4, 10.
Nodo en orden creciente: 1, 3, 4, 7, 8, 9, 10, 12, 13, 15, 20, 22, 23, 30, 34, 40, 45, 48, 51, 53.
[pic 1]
Paso 1: Contabilizar la cantidad de nodos entregados.
Paso 2: Ordene los nodos de menor a mayor, considerando los nodos centrales para dejar como nodo raíz en este caso contamos con los nodos 15 y 20, teniendo en cuenta la cantidad de nodos mayores y menores, decido dejar como nodo central el nodo 15, para poder dejar el árbol de forma equilibrada.
Paso 3: Construcción del árbol del subárbol izquierdo. Aplico el mismo la misma lógica de ubicar los números centrales y considerar la construcción de tal forma que cada nodo tenga 2 descendientes, considerando las ramas izquierdas y derechas.
Paso 4: Construcción del subárbol derecho. Elijo el número 20 para iniciar el la construcción del subárbol derecho dado que es el menor de los números más altos, pero cumple el criterio de ser mayor que el nodo raíz y luego comienzo el orden de los números mayores siguiendo la lógica que los nodos menores se ubican hacia la izquierda y los nodos mayores hacia la derecha.
- Utilizando la siguiente imagen desarrolle las actividades señaladas:
[pic 2]
- Indique si representa un árbol binario o un árbol convencional. Señale 2 argumentos que justifiquen su respuesta.
El árbol representado es un árbol binario, dado que los nodos principal o raíz tiene como máximo dos subárboles, el izquierdo y el derecho; además los nodos hijo no tienen más de 2 nodos como descendientes.
- Confeccione una tabla comparativa entre ambos tipos de árboles que contenga a lo menos 2 elementos a comparar.
Árbol convencional | Árbol binario | |
Segundo nivel de nodos | Puede tener más de dos subárboles | Puede tener como máximo dos subárboles. Siempre es necesario distinguir entre el subárbol izquierdo y derecho. |
Organización de datos | Los nodos se agregan de acuerdo al orden que se van dando y al espacio que se desee que ocupe en el árbol. | De acuerdo a la inserción de nodos estos se ubicarán de tal forma que en el subárbol izquierdo irán los nodos con datos menores que el nodo raíz y por otro lado en el subárbol derecho se ubicarán nodos con valores mayores al nodo raíz. Esto se aplica en el caso de árbol binario de búsqueda. |
Operación búsqueda | Más lento en comparación de un árbol binario de búsqueda | Es más rápido dado que al saber que dato buscar y saber si este es menor o mayor a la raíz, no debe recorrer el árbol entero para encontrar el elemento deseado. |
...