🌳 PÍLDORA TAI — ÁRBOLES Y BÚSQUEDA (COMPLETO EXAMEN)

---

⚙️ 1. CONCEPTO CLAVE

Un árbol es una estructura de datos jerárquica:

• Nodo raíz (root)
• Nodos hijos / padre
• Hojas (sin hijos)
• Subárboles

👉 Sin ciclos y conectado

---

📏 2. TERMINOLOGÍA (MUY PREGUNTABLE)

• Grado de un nodo → nº de hijos
• Altura → longitud del camino más largo desde la raíz a una hoja
• Profundidad → distancia desde la raíz a un nodo
• Nivel → profundidad + 1 (según definición)
• Árbol binario → máximo 2 hijos por nodo

---

🌲 3. TIPOS DE ÁRBOLES BINARIOS

🔹 Árbol binario completo

• Todos los niveles llenos excepto quizá el último
• Último nivel → de izquierda a derecha

🔹 Árbol binario perfecto

• Todos los niveles completamente llenos
• Nº nodos = 2ⁿ - 1

🔹 Árbol binario lleno (full)

• Cada nodo tiene 0 o 2 hijos

🔹 Árbol degenerado

• Parece una lista (todos hacia un lado)

---

🔍 4. ÁRBOLES DE BÚSQUEDA (BST)

👉 Propiedad clave:

• Izquierda < nodo < derecha

✔️ Operaciones

• Búsqueda → O(log n) (si balanceado)
• Inserción
• Eliminación:
  • Hoja → borrar
  • 1 hijo → sustituir
  • 2 hijos → usar sucesor inorden

---

🔄 5. RECORRIDOS (CLÁSICO TAI)

🔹 Inorden (LNR)

• Izquierda → Nodo → Derecha
  👉 Devuelve ordenado en BST

🔹 Preorden (NLR)

• Nodo → Izquierda → Derecha

🔹 Postorden (LRN)

• Izquierda → Derecha → Nodo

🔹 Por niveles (BFS)

• Nivel a nivel (cola)

---

⚖️ 6. ÁRBOLES BALANCEADOS

👉 Mantienen altura ≈ log(n)

🔸 AVL

• Diferencia de alturas ≤ 1
• Rotaciones (LL, RR, LR, RL)

🔸 Red-Black

• Más flexible que AVL
• Usado en librerías (Java TreeMap, etc.)

---

📦 7. ÁRBOLES MULTIVÍA (MUY EXAMEN)

🔹 B-Tree

• Varios hijos por nodo
• Usado en bases de datos

🔹 B+ Tree

• Datos en hojas
• Mejor para acceso secuencial

---

🔢 8. COMPLEJIDAD (TRAMPA CLAVE)

Operación	BST balanceado	BST degenerado
Buscar	O(log n)	O(n)
Insertar	O(log n)	O(n)
Borrar	O(log n)	O(n)

---

⚠️ TRAMPAS TÍPICAS TAI

• ❌ BST siempre O(log n) → FALSO (solo si balanceado)
• ❌ Inorden sirve para cualquier árbol → SOLO BST ordena
• ❌ Completo = perfecto → NO
• ❌ B-Tree = binario → NO (multivía)

---

📌 REGLAS DE ORO

• BST → orden por propiedad izquierda < nodo < derecha
• Inorden → lista ordenada
• Balanceado → log(n)
• B-Tree → bases de datos

---

🧠 MINI TEST TAI

¿Qué recorrido devuelve los valores ordenados en un BST?
a) Preorden ❌
b) Postorden ❌
c) Inorden ✅
d) BFS ❌

---

¿Qué ocurre si un BST no está balanceado?
a) Mejora rendimiento ❌
b) Se convierte en heap ❌
c) Puede degradarse a O(n) ✅
d) No afecta ❌

---

¿Qué estructura se usa en índices de BBDD?
a) AVL ❌
b) B-Tree / B+ Tree ✅
c) Lista enlazada ❌
d) Hash simple ❌

---

¿Qué árbol tiene todos los niveles llenos?
a) Completo ❌
b) Perfecto ✅
c) Degenerado ❌
d) AVL ❌

---