Lección 12: Árboles y árboles binarios de búsqueda (BST)
Piensa en un árbol genealógico, o en carpetas dentro de carpetas: hay algo 'arriba' que se ramifica en elementos 'debajo'. Eso es un 'árbol': cada punto es un 'nodo'. En un 'árbol binario de búsqueda' (BST), cada nodo tiene valores más pequeños a su izquierda y más grandes a su derecha, igual que bu
Un BST es como buscar una palabra en un diccionario: abres por el medio, y si la palabra viene 'antes', saltas toda la mitad derecha de una vez. Cada comparación ahorra la mitad del trabajo, pero solo si las páginas están divididas equitativamente.
- clase (class)
- Una plantilla para una pequeña caja con campos. class TreeNode define una caja con tres campos: val (el valor) y left/right (los hijos). TreeNode(5) crea una caja así, y self simplemente significa "esta caja" (la misma idea que en la lección de listas enlazadas).
- árbol binario de búsqueda
- Un árbol binario donde, para cada nodo, todos los valores del subárbol izquierdo son más pequeños y todos los del subárbol derecho son más grandes.
- recorrido de árbol
- Visitar cada nodo de un árbol en un orden definido. Inorder (izquierda, nodo, derecha) en un BST devuelve los valores ordenados.
- árbol balanceado
- Un árbol cuya altura es de aproximadamente log n, así que la búsqueda toma O(log n). Un árbol 'estirado' (skewed) pierde esa ventaja y llega a O(n).
