Slides TD Parcial2-131-140

Vista previa del material en texto

Arbol Binario de Búsqueda
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 };
14 nodo* _raiz;
28
Arbol Binario de Búsqueda
29
ABB: buscar
1 bool buscar(int n, nodo* abb) {
2 if (abb == nullptr){
3 return false;
4 }
5 else if (n == abb->elem){
6 return true;
7 }
8 else if (n < abb->elem){
9 return buscar(n, abb->izquierdo);
10 }
11 else if (n >= abb->elem){
12 return buscar(n, abb->derecho);
13 }
14 }
¾Qué complejidad de peor caso tiene buscar?
O(h) con h altura del árbol
30
ABB: insertar
1 // devuelve nodo insertado
2 nodo* insertar(int n, nodo* abb) {
3 if (abb == nullptr) {
4 return new nodo(n);
5 } else if (n < abb->elem)
6 abb->izquierdo = insertar(n, abb->izquierdo);
7 else if (n > abb->elem)
8 abb->derecho = insertar(n, abb->derecho);
9
10 // devuelve raiz sin modificar
11 return abb;
12 } // Complejidad: O(h)
31
ABB: borrar
Si el nodo a borrar tiene un sólo hijo.
32
ABB: borrar
Si el nodo a borrar tiene dos hijos y su hijo derecho no tiene hijo
izquierdo.
33
ABB: borrar
Si el nodo a borrar tiene dos hijos y su hijo derecho sí tiene hijo izquierdo.
34
ABB: borrar
Busca recursivamente el nodo, lo borra y reconecta el arbol
1 // devuelve la nueva raiz, si cambia
2 nodo* borrar(int n, nodo* abb) {
3 if (n < abb->elem) {
4 // recursion izquierda: actualiza izquierdo
5 abb->izquierdo = borrar(n, abb->izquierdo);
6 return abb;
7 } else if (n > abb->elem) {
8 // recursion derecha: actualiza derecho
9 abb->derecho = borrar(n, abb->derecho);
10 return abb;
11 } else {
12 // calcula reemplazante y elimina nodo actual
13 nodo* nueva_raiz = quitar_raiz(abb);
14 delete abb;
15 return nueva_raiz;
16 }
17 }
35
ABB: quitar_raiz
Determina la nueva raiz para reemplazar a la actual y la devuelve
1 // calcula nodo reemplazante del abb pasado
2 nodo * quitar_raiz(nodo* abb) {
3 nodo * nueva_raiz;
4 if (abb->izquierdo == nullptr)
5 nueva_raiz = abb->derecho; // caso (a)
6 else if (abb->derecho == nullptr)
7 nueva_raiz = abb->izquierdo; // caso (b)
8 else if (abb->derecho->izquierdo == nullptr) {
9 nueva_raiz = abb->derecho; // caso (c)
10 nueva_raiz->izquierdo = abb->izquierdo;
11 } else {
12 // caso (d)
13 nueva_raiz = quitar_minimo(abb->derecho); // O(h)
14 nueva_raiz->izquierdo = abb->izquierdo;
15 nueva_raiz->derecho = abb->derecho;
16 }
17 return nueva_raiz;
18 }
36
ABB: quitar_minimo
Busca mínimo del abb, lo quita, y reconecta padre con hijo
1 // Pre: Asume que tiene hijo izquierdo
2 nodo* quitar_minimo(nodo* abb) {
3 while (abb->izquierdo->izquierdo != nullptr) //O(h)
4 abb = abb->izquierdo;
5 // saco izquierdo, reconecto padre con derecho
6 nodo* minimo = abb->izquierdo;
7 abb->izquierdo = minimo->derecho;
8 return minimo; // devuelvo el quitado
9 }
37