Scribd
Cargar
52 vistas1 página

Examen Test

El documento describe conceptos fundamentales sobre árboles binarios, incluyendo definiciones de nodos, recorridos y propiedades como profundidad y altura. También se abordan árboles binarios de búsqueda (ABB) y su complejidad temporal, así como árboles AVL y su factor de equilibrio. Se mencionan técnicas de rotación para mantener el equilibrio en árboles AVL.

Cargado por

elena
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
52 vistas1 página

Examen Test

El documento describe conceptos fundamentales sobre árboles binarios, incluyendo definiciones de nodos, recorridos y propiedades como profundidad y altura. También se abordan árboles binarios de búsqueda (ABB) y su complejidad temporal, así como árboles AVL y su factor de equilibrio. Se mencionan técnicas de rotación para mantener el equilibrio en árboles AVL.

Cargado por

elena
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

EXAMEN TIPO TEST ÁRBOLES

5.1 Árboles binarios

- Raíz: el único nodo que no tiene padre (A)


- Nodo interno: un nodo que al menos tiene un hijo (A, B, C, F)
- Nodo hoja (Externo): nodo sin hijos (E, I, J, K, G, H, D)
- Hermanos: nodos con el mismo padre.
- Ascendientes y descendientes.
- Subárbol: árbol formado por un nodo (por ejemplo, B) y todos sus descendientes.
- El tamaño de un nodo se define como el tamaño de su subárbol
- El tamaño de un árbol se define como el número de sus nodos
- Camino: existe un camino entre los nodos X e Y, si existe una secuencia de nodos que permita
alcanzar Y desde X (siempre de forma descendente o ascendente, nunca ambas).
- La profundidad de un nodo es la longitud del camino de la raíz a dicho nodo.
- La altura de un nodo es la longitud del camino más largo desde dicho nodo a una hoja.
- La altura de un árbol se define como la altura de su raíz
- Por tanto, la altura de un árbol vacío será -1.
- El grado de un nodo es el número de hijos directos.
- El grado de un árbol es el grado mayor de todos sus nodos

Recorrido pre-order: ○ Primero, visitamos la raíz, entonces el árbol izquierdo, y finalmente, el subárbol
derecho (root, left, right). Cada subárbol es visitado recursivamente aplicando pre-order.

Recorrido post-order: ○ Primero, visitamos el subárbol izquierdo, luego el subárbol derecho, y finalmente, la
raíz. (left, right, root). Cada subárbol es visitado recursivamente aplicando pre-order.

Recorrido in-order: primero visitamos el subárbol izquierdo, la raíz y el subárbol derecho. Cada subárbol es
visitado recursivamente aplicando el recorrido in-order: (left, root, right).

Los nodos son visitados por niveles. Así, los nodos son visitados en el mismo nivel, de izquierda a derecha,
y de forma descendente.

5.2 Árboles binarios de Búsqueda (ABB)

Para todo nodo, todos los elementos de su subárbol izquierdo son menores que el elemento del nodo, y a su
vez el elemento del nodo es menor que todos los elementos del subárbol derecho.
Por tanto, la complejidad temporal de search es O(log2 (n)).
Por tanto, la complejidad temporal de los árboles no balanceados será: O(h) = O(n)

5.3 Árboles AVL

Factor de equilibrio (fe) : valor absoluto de la diferencia entre la altura del subárbol derecho y el subárbol
izquierdo. fe = |hr − hl |
Un árbol es AVL (o está equilibrado en altura), cuando todos sus nodos tienen un factor de equilibrio menor
o igual que 1.
- Rotación simple derecha
- Rotación simple izquierda
- Doble rotación izquierda derecha
- Doble rotación derecha izquierda

También podría gustarte