Tema 4
Árboles binarios, búsqueda lineal y binaria
Patrón de examen
Usa búsqueda binaria cuando el arreglo esté ordenado o cuando puedas definir una propiedad monotónica (falso...falso...verdadero...verdadero).
Explicación
Árbol binario
Estructura jerárquica donde cada nodo tiene a lo más dos hijos (izquierdo y derecho).
- Raíz: nodo inicial
- Hoja: nodo sin hijos
- Altura: distancia máxima de la raíz a una hoja
Árbol Binario de Búsqueda (BST)
Para todo nodo: izquierdo < nodo < derecho. Permite búsqueda en O(log n) si está balanceado.
En C++: set y map implementan un BST balanceado (Red-Black Tree).
set<int> s;
s.insert(x); s.erase(x); s.count(x);
map<string,int> m;
m["clave"] = valor;
Búsqueda lineal O(n)
Recorrer el arreglo hasta encontrar el elemento.
Búsqueda binaria O(log n)
Solo funciona en arreglos ordenados. Divide el espacio de búsqueda a la mitad en cada paso.
Template universal de búsqueda binaria:
int l = 0, r = n - 1, res = -1;
while (l <= r) {
int m = (l + r) / 2;
if (condicion(v[m])) { res = m; r = m - 1; }
else l = m + 1;
}