Slides TD Parcial2-141-150

Vista previa del material en texto

ABB degenerado
1 nodo* abb = nullptr;
2 abb = insertar(1,abb);
3 abb = insertar(2,abb);
4 abb = insertar(3,abb);
5 abb = insertar(4,abb);
6 abb = insertar(5,abb);
½Se convirtió en una lista! buscar: complejidad O(h) = O(n)
Si fuera completo... ½O(h) = O(log n)!
Pero no es razonable requerir que sea completo.
38
AVL: ABB balanceado
1 struct nodo {
2 int elem;
3 nodo* izquierdo = nullptr;
4 nodo* derecho = nullptr;
5
6 /////////////////////////////////////////////////
7 // Rep:
8 // - no hay ciclos en la cadena de punteros
9 // - cada nodo tiene un único "padre"
10 // - Para todo nodo n del arbol:
11 // * n.elem > todo elemento de n.izquierdo
12 // * n.elem < todo elemnto de n.derecho
13 // - |altura(n.izquierdo) - altura(n.derecho)| <= 1
14 };
Asegura que la altura total es O(log n).
La diferencia de alturas se preserva rebalancenado el arbol al insertar
y borrar
39
AVL: factor de balanceo
40
AVL: desbalanceo
41
AVL: rebalanceado
42
Arboles balanceados en la C++ std
En C++ std, std::set y std::map están implementados sobre
árboles balanceados.
Es decir, sus complejidades de búsqueda/inserción/borrado son O(h)
= O(log n) garantizadas.
El árbol usado en C++ es un red-black tree, que es una variante de
arbol balanceado que asegura que desde ningún nodo ningún camino
a las hojas es más del doble de largo que otro.
La bibliografía de la materia (Cormen) hace hincapié en red-black
tree. Explicamos AVL por ser más intuitiva la idea.
43
Motivación
Quisiéramos tener un Conjunto/Diccionario que nos provea
▶ Inserción
▶ Búsqueda
▶ Eliminación
...en O(1) (o casi). ¾Es esto posible?
Idea: Almacenar elementos en una tabla (vector) para tener acceso a
cada elemento en O(1).
Problema: ¾cómo ubicar la posición asociada a cada elemento?
3
Tabla: direccionamiento directo
Escenario más sencillo: mis claves son enteros que pertenecen a un
conjunto 0, 1, . . . ,m − 1 donde m es un valor no demasiado grande.
Solución: creo un vector de m posiciones. Mis operaciones de
buscar/de�nir/borrar se reducen a acceder a la posición i para
manipular la clave i .
Problemas:
▶ Sólo funciona para claves enteras.
▶ Si la cantidad N a almacenar es mucho menor que m, se
desperdicia mucho espacio.
4
Tabla: direccionamiento directo
▶ Ejemplo: diccionario con claves de tipo int y valores de tipo string
▶ Estructura de representación: vector<string> tabla
5
Direccionamiento directo � problemas
▶ Si el universo de posibles valores U es demasiado grande,
almacenar una tabla de tamaño |U| puede ser impracticable,
▶ El conjunto K de valores que realmente se van a almacenar
puede ser mucho más chico que U, y la mayor parte del espacio
de la tabla estaría desperdiciado.
Idea:
▶ Una tabla de tamaño |K| o, al menos, O(|K|), y
▶ una función h : U → 0 . . . |tabla| − 1.
▶ tabla[h(c)] = v; almacena en la clave c el valor v.
6