Estructura de datos y bases de algoritmos

a) Definir nivel, altura, subárbol y ancestros en un Arbol Binario.

Nivel: Es el grado de profundidad en que se encuentra un nodo determinado. El nivel del nodo raiz

es cero y de allí en más aumenta en uno por escalón de profundidad.

Altura: Es el nivel correspondiente al nodo o nodos que hayan alcanzado el máyor nivel de

profundidad.

Subárbol: Es cada uno de los subconjuntos de nodos disjuntos que depende de un nodo raiz

determinado.

Ancestros: Es el conjunto de nodos que forman parte del camino desde un nodo dado hasta la raiz

de árbol.

a) Definir Arbol Binario en forma recursiva.

Un árbol binario es una estructura de datos homogénea que:

• O bien es el conjunto vacío, en cuyo caso se denomina árbol vacío.

• O bien no lo es, en cuyo caso existe un primer elemento llamado raíz y el resto de los

elementos se distribuyen en dos conjuntos disjuntos, cada uno de los cuales es un árbol por

sí mismo (subárboles izquierdo y derecho).

Indique cuales son las reglas que rigen a un Arbol B.

Cada nodo es una página de elementos. Todas las páginas contendrán como mínimo “N” elementos. Árbol de orden N. La página raíz del árbol B está exceptuada del punto anterior. Todas las páginas contendrán como máximo “2N” elementos. Toda página, o es hoja o tiene M+1 descendientes. Siendo M la cantidad de elementos presentes en la página (entre N y 2N).

1. Explique la estructura de árbol y por qué se puede definir en forma recursiva.

Trabaja como un conjunto ordenado de elementos que se disponen en forma jerárquica. Es una

estructura que crece en profundidad.

Existe un primer elemento del cual dependen todos los demás y que a su vez él no depende de

ninguno, el resto son hijos del primer elemento o descendientes de estos.

Un árbol es una estructura que: O bien es el conjunto vacío, en cuyo caso se denomina árbol vacío, siendo esta la condición de corte de la recursividad. O bien no lo es, en cuyo caso existe un primer elemento llamado raíz y el resto de los elementos se distribuyen en conjuntos disjuntos, cada uno de los cuales es un árbol por sí mismo (subárbol). El subarbol es la misma estructura del arbol mayor pero instanciado más simple ya que representa un subconjunto. Constituye la Solución General del problema planteado en forma recursiva.

Defina nodo-página de Arbol B. Indique las reglas que se aplican para dicho tipo de árbol.

Para que un árbol sea árbol B deberá cumplir con:

Cada nodo es una página de elementos. Todas las páginas contendrán como mínimo “N” elementos. Árbol de orden N. La página raíz del árbol B está exceptuada del punto anterior. Todas las páginas contendrán como máximo “2N” elementos. Toda página, o es hoja o tiene M+1 descendientes. Siendo M la cantidad de elementos presentes en la página (entre N y 2N).

Defina Arbol AVL. Cuál es el objetivo de esta variante de árbol ABO?

• Un árbol AVL es un árbol de binario ordenado (ABO) donde para cada nodo se cumple que la

altura de los subárboles derecho e izquierdo difieren a lo más en 1. (La altura de un árbol

vacío se define como -1)

• FE (Factor de equilibrio) = h(si) – h(sd) El objetivo es mantenerlo balanceado con el fin de que todas las operaciones sean de O(log n)

37) Explique las reglas que permiten crear, hacer crecer y decrecer un árbol B. Luego de explicado, realice un caso que muestre su comportamiento.

33) Indique cuál es la ventaja del Árbol B+ sobre el B y cuál es el costo adicional de mantener un árbol B+.

b) Dado el conjunto A={4,9,23,3,64,7,6,1,31,14,2,12,33}. Dibuje el árbol que resulta de insertar el

conjunto con criterio de menores a izquierda y escriba las tres secuencias de travesía (Pre, In y

Posorder).

                                  4

                              3                           9

                                      1                        7            23

                                2                          6            14       64

                                  12                                     31

                                                                           33

PRE=4,3,1,2,9,7,6,23,14,12,64,31,33

IN=1,2,3,4,6,7,9,12,14,23,31,33,64

POS=2,1,3,6,7,12,14,33,31,64,23,9,4

Dado el conjunto A={4,9,23,3,7,6,1,14,2,12}. Dibuje el árbol que resulta de insertar en

conjunto con criterio de menores a izquierda y escriba las tres secuencias de travesía

(Pre, In y Posorder).

Menores a Izquierda

                                        4

                                3                9

                        1                      7                23

                                2            6            14

                                                   12

PREORDER={4,3,1,2,9,7,6,23,14,12}

INORDER={1,2,3,4,6,7,9,12,14,23}

POSORDER={2,1,3,6,7,12,14,23,9,4}

Dado el conjunto A={32,12,65,76,89,21,02,05,36,66,23,20,38,45,78,24} dibujar el arbol B

de orden N=2 correspondiente.

               12                 ,         23 ,                         36                 65

02 , 05                  20 , 21                              24 , 32                            38 , 45                     66 , 76 , 78 , 89

...