Primitivas

• void* find (char* key)
  • Amortizado: O(log (n))
  • Peor: O(n)
• insert (char* key, void* value)
  • Amortizado: O(log (n))
  • Peor: O(n)

Arboles binarios de búsqueda

Prop: el árbol izq es menor y el árbol derecho es mayor

→ No puede haber repetidos

Ejemplo:

• Está + o - balanceado → por eso cuesta log n el find

Arbol Degenerado (lineal?)

Me cuesta O(n) el find

AVL o black-red tree: implementación de árboles balanceados

Metadatos

Del árbol

• nodo* raiz
• size_t cant

Nodo

• key
• hijo_izq