Slides TD Parcial2-111-120

Vista previa del material en texto

Arbol Binario Completo
Un árbol binario está completo si todos los niveles del árbol tienen la
máxima cantidad de nodos posible.
Para un árbol binario completo, si la altura es h tenemos que:
▶ tiene 2h hojas,
▶ tiene 2h+1 − 1 nodos
7
Arbol Binario � buscar
1 bool buscar(int n, nodo* arbol) {
2 if (arbol == nullptr){
3 return false;
4 }
5 else if (n == arbol->elem){
6 return true;
7 }
8 else {
9 return buscar(n,arbol->izquierdo) or
10 buscar(n,arbol->derecho);
11 }
12 }
¾Cuántas veces se accede a cada nodo en peor caso?
Una vez a cada nodo.
¾Qué complejidad de peor caso tiene buscar?
O(n) con n cantidad total de nodos
8
Arbol Binario � inorder
Inorder recorre todos los nodos del árbol de la siguiente manera:
1. Primero recorrer el subarbol izquierdo,
2. Luego visitar la raíz,
3. Luego recorrer el subarbol derecho.
Inorder: 1, 7, 4, 2, 1, 0, 5, -2
9
Arbol Binario � inorder
1 void inorder_imprimir(nodo* arbol) {
2 if (arbol == nullptr)
3 return;
4
5 inorder(arbol->izquierdo);
6 cout << arbol->elem << endl;
7 inorder(arbol->derecho);
8 }
10
Arbol Binario � preorder
Preorder recorre todos los nodos del árbol de la siguiente manera:
1. Primero visitar la raíz,
2. Luego recorrer el subarbol izquierdo,
3. Luego recorrer el subarbol derecho.
1 void preorder_imprimir(nodo* arbol) {
2 if (arbol == nullptr)
3 return;
4
5 cout << arbol->elem << endl;
6 preorder(arbol->izquierdo);
7 preorder(arbol->derecho);
8 }
11
Motivación para Heap
Queremos una estructura donde acceder al máximo elemento sea
muy e�ciente, pero no queremos pagar el costo de mantenerla
completamente ordenada.
Nos gustaría:
▶ Acceder al máximo en O(1)
▶ Quitar el máximo en O(log n)
▶ Agregar nuevo elemento en O(log n)
▶ Buscar otros elementos: no es prioritario, O(n).
Idea: almacenarlos de manera conveniente en un arbol binario.
▶ En la raíz almacenamos el máximo
▶ Mantenemos la altura cercana a log n
12
Arbol binario: Max Heap
Un árbol binario max-heap cumple las siguientes condiciones:
▶ Todos los nodos del árbol tienen un elemento mayor o igual al de sus
descendientes,
▶ Es izquierdista: todos los niveles están completos salvo el último,
que se rellena de izquierda a derecha.
Notar que, como el árbol es izquierdista, su áltura es log n.
13
Max Heap: Inserción (1)
Para insertar un elemento nuevo:
1. lo colocamos en la primera hoja libre,
2. lo vamos subiendo de nivel mientras sea mayor que su padre.
(para mantener el invariante)
14
Max Heap: Inserción (2)
Para insertar un elemento nuevo:
1. lo colocamos en la primera hoja libre,
2. lo vamos subiendo de nivel mientras sea mayor que su padre.
(para mantener el invariante)
15
Max Heap: Inserción (3)
Para insertar un elemento nuevo:
1. lo colocamos en la primera hoja libre,
2. lo vamos subiendo de nivel mientras sea mayor que su padre.
(para mantener el invariante)
16