Conceptos Básicos:
Raíz: Aquel elemento que no tiene antecesor.
Rama: Arista que está entre dos nodos.
Antecesor: Un nodo tiene como antecesor los nodos que están hacia arriba conectados por una rama.
-Sucesor: Mismo que antecesor pero hacia abajo. Un nodo x es sucesor de y si por alguna de las ramas de y puedo llegar a x
Grado: Número de descendientes que tiene un nodo (escogiendo la rama más larga).(directos)
Hoja: Nodo que no tiene descendientes. Es de grado 0
Nodo Interno: Aquel que al menos tiene un descendiente.
Nivel: Cuántos pisos tiene el árbol. (Número de ramas que hay que recorrer dese la raíz a un nodo cualquiera
Altura: Cuántos nodos hay entre el último nodo y la raíz.
-Anchura: Nivel que tenga más hijos (la raíz es piso 0). El máximo número de nivel que tiene un árbol
Type def ARBOL = Record
clave if= dato;
*izquierda, *c; *der=árbol;
end record;
Árboles ABB: Solo tienen 2 hijos máximo.
- Todas las claves del lado izquierdo son menores que las claves del subárbol derecho.
Crear (rec= ARBOL)
nuevo.clave = elemento;
nuevo.izq = nuevo.der = NULL;
Reglas para Borrar en ABB
1. Si el nodo que quiero borrar no tiene hijos, se borra sin problema.
2. Si tiene un descendiente, sustituyo al nodo que quiero borrar por su hijo.
3. Si el nodo tiene 2 descendientes:
3.1 Buscamos el menor de los mayores (buscas del lado derecho el número menor y ese va a sustituir al nodo que estamos borrando).
3.2 Buscamos el mayor de los menores (buscar del lado izquierdo el mayor y ese lo sustituyes por el que quiero borrar).
--------------Búsqueda (rec: ARBOL)
If rec == null then
return (F);
Else
If rec.clave < elemento que busco then
Búsqueda (rec -> derecha);
Else
If rec.clave > elemento que busco then
Búsqueda (rec -> izquierda);
Else
return (true)
----------------------Insertar (rec= ARBOL)
If rec == null then
rec = nuevo;
Else
If rec -> clave == nuevo.clave then
Insertar (rec -> derecha);
Else
If rec.clave > nuevo.clave then
Insertar (rec -> izquierda);
En la secuencia 100,50,150,120,140,40,30,145 la altura del arbol es igual a:
-4
3
Ninguna de las anteriores
4 ✔
La siguiente función
void recorrer (*rec: arbol)
If Rec= NULL then
Return (); else
recorrer (rec.izq);
recorrer (rec.der);
visito 0; } }
recorre el árbol en Postorder ✔
ninguna de las nteriores
recorre el árbol en Inorder
recorre el árbol en Preorder
Los arboles son estructuras:
Tienen estructuras denominadas
subarboles
Ninguna de las anteriores
Son recursivos
Que pueden tener múltiples enlaces
Todas las anteriores ✔
Otro:
Cuales de las siguientes secuencias representa un árbol AVL:
Todas las anteriores
Ninguna de las anteriores
15,40,2,0,3,50,30,20,4 ✔
100,50,150,120,140,40,30,145
15,40,2,0,3,50,30,20,4 ✔
Al numero de descendientes que tiene un nodo en una
estructura árbol se denomina : Anchura /// Raiz //Sucesor
Grado ✔
Hoja
Dada la siguiente secuencia 15,40,2,0,3,50,30,20,4 del ABB después del recorrido en inorder se obtiene la siguiente secuencia de salida:
ninguna de las anteriores
0,2,3,4,15,20,30,40,50 ✔
15,2,0,3,4,40,30,20,50
0,4,3,2,20,30,50,40,15
En la siguiente secuencia 15,40,2,0,3,50,30,20,4 al eliminar la raíz dos veces de manera consecutiva, utilizando el algoritmo del menor de los mayores se obtiene
raíz =nodo 30 y árbol AVL ✔
Raiz = nodo 30 árbol no AVL
Raiz = nodo 40 arbol AVL
Ninguna de las anteriores
Raiz =nodo 20 y arbol AVL
En la secuencia 100,50,150,120,140,40,30,145 el factor de equilibrio:
En el nodo 120 es igual a 2 y en el nodo 150 es -3 ✔
En el nodo 120 es igual a 2 y en el nodo 150 es 3
En el nodo 100 es igual a 2 y en el nodo 40 es -1
Ninguna de las anteriores
Dada la secuencia M,E,J, K, L,C, P,N,S,R,U,T,O,B,H, I, A,
después de eliminar el nodo P utilizando el algoritmo
de borrado "el menor de los mayores", el árbol AVL se
obtiene. Favor anexar el arbol resultante en el archivo
anexo a este examen
Inmediatamente despues del borrado
Despues de aplicar caso l, caso ll y caso IV
Despues de aplicar un caso ll y caso 1
Despues de aplicar un caso l y caso IV ✔
Son aquellos donde sus claves que están a la derecha
son mayores a las claves que se encuentran a su
izquierda y su altura entre subarboles en cada nodo No
difiere de 1
Arboles Binarios de Búsqueda
todas las anteriores
Arboles equilibrados ✔
Factor de equilibrio
Cuando se calcula la diferencia de alturas entre el
subárbol derecho menos la del subárbol izquierdo, en
cada nodo del árbol, corresponde a:
todas las anteriores
Arboles equilibrados
Factor de equilibrio ✔
Arboles Binarios de BusquedA