estructuras de datos clase 13 –Árboles binarios de...

26
Estructuras de Datos Clase 13 – Árboles binarios de búsqueda Dr. Sergio A. Gómez http://cs.uns.edu.ar/~sag Departamento de Ciencias e Ingeniería de la Computación Universidad Nacional del Sur Bahía Blanca, Argentina

Upload: others

Post on 26-Sep-2020

4 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Estructuras de DatosClase 13 – Árboles binarios de

búsqueda

Dr. Sergio A. Gómezhttp://cs.uns.edu.ar/~sag

Departamento de Ciencias e Ingeniería de la ComputaciónUniversidad Nacional del Sur

Bahía Blanca, Argentina

Page 2: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Motivaciones• El árbol binario de búsqueda (ABB) es una

estructura de datos útil para implementar conjuntos, mapeos y diccionarios.

• En un ABB las claves en los nodos se hallan ordenadas de una manera particular.

• El tiempo de insertar, recuperar y eliminar es proporcional a la altura del ABB.

• Si el árbol tiene n claves, la altura del ABB se halla entre log2(n) y n.

Estructuras de datos - Dr. Sergio A. Gómez 2

Page 3: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Definición• Un ABB es un árbol binario tal que:

– Es vacío, o,

– Es un nodo con rótulo k e hijos tizq y tder tales:

• k > claves de tizq,

• k < claves de tder, y,

• tizq y tder son ABB.

Estructuras de datos - Dr. Sergio A. Gómez 3

20

16 64

6 18 37 78

9850

60

17

k

tizq tder

Page 4: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Inserción en un ABB• Las nuevas claves siempre se insertan como hijo de un nodo hoja.• Algoritmo insertar( k, p ) { Comienza en la raíz del ABB }

Si p es vacío entoncescrear un nodo hoja con rótulo k

Sino si k < clave(p) entonces

insertar(k, hijo izquierdo de p)sino si k > clave(p) entonces

insertar( k, hijo derecho de p )sino si k = clave(p) entonces

reemplazar rótulo de p

Nota: La operación “reemplazar rótulo de p” dependerá de si:(a) Implemento un conjunto: no hacer nada(b) Implemento un mapeo: modifico el valor de la entrada(c) Implemento un diccionario: Agrego una entrada con clave k

Estructuras de datos - Dr. Sergio A. Gómez 4

Page 5: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Ejemplos de inserciones

• Ejemplo 1: Dado un ABB vacío, realizar la siguiente secuencia de inserciones:

10, 23, 8, 90, 78, 45, 3, 7, 12, 89, 44, 100, 95, 4

• Ejemplo 2: Dado un ABB vacío, realizar la siguiente secuencia de inserciones:

2, 4, 6, 9, 10, 34, 78, 90, 100, 120

• Ejemplo 3: Dado un ABB vacío, realizar la siguiente secuencia de inserciones:

120, 100, 45, 34, 29, 26, 16, 13, 5, 2

Estructuras de datos - Dr. Sergio A. Gómez 5

Page 6: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Búsqueda de una clave k partir del nodo p Algoritmo Buscar( k, p ) // La primera vez se llama con la raíz del ABB

Si p es vacío entonces // CB: Se me terminó el árbol

return falso // k no se encuentra en el ABB

Sino si k = clave(p) entonces // CB: encontré a k

return true // k sí se encuentra en el ABB porque lo encontré

Sino si k < clave(p) entonces // k es menor a la clave de p

return Buscar( k, hijo izquierdo de p)

Sino // k > clave(p)

return Buscar( k, hijo derecho de p )

Estructuras de datos - Dr. Sergio A. Gómez 6

Si el k > clave(p), tengo que buscar a k en el hijo de derecho de p, que tambíen(conceptualmente) es un ABB porque descarté la raíz y el otro subárbol (hijo izquierdode p).

Subárboldel ABB con raíz p

Page 7: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Análisis de la complejidad temporal• Sea h = altura del ABB y sea n = cantidad de claves

del ABB.

� ℎ = � �� � ℎ = 0�� + �(ℎ − 1) � ℎ > 0con lo cual � ℎ = � ℎ .• La altura en el peor caso es ℎ = � (se da cuando se

hicieron inserciones de claves en forma ascendente o descendente)

• La altura en el mejor caso es ℎ = �(���� � ) ya que las inserciones produjeron un árbol lleno que tiene � = 2ℎ + 1 − 1 nodos; de ahí, despejo ℎ =���� � + 1 − 1.

Estructuras de datos - Dr. Sergio A. Gómez 7

Page 8: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Análisis de la complejidad temporal• Otra forma de estudiar el peor caso del mejor caso del

ABB (que se da cuando el árbol está lleno y no encuentro la clave buscada):

• Sea � = cantidad de claves del ABB.

� � = � �� � � = 0�� + �((� − 1)/2) � � > 0con lo cual � � = � ���2(�) .

Estructuras de datos - Dr. Sergio A. Gómez 8

Si el árbol tiene n claves, el hijo en el que buscorecursivamente tiene (n-1)/2 claves porque descarté la raízy el otro subárbol.

ABB con n claves

Page 9: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Implementación en Java: Preliminares• Para facilitar la programación usaremos un árbol propio

donde cada hoja tiene dos hijos dummy (placeholdersegún GT)

• Estos dummies sirven para insertar nuevas claves en su lugar y representan ABB vacíos.

• Ejemplo:

Estructuras de datos - Dr. Sergio A. Gómez 9

k Nodo con clave k

Nodo dummy

Referencias:

20

16 64

6 18 37 78

9850

60

17

Page 10: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Implementación en Java: PreliminaresSupongamos que deseamos insertar el 62, para ello buscamos su ubicación:

Estructuras de datos - Dr. Sergio A. Gómez 10

20

16 64

6 18 37 78

9850

60

17

20

16 64

6 18 37 78

9850

60

17

62El rótulo dummyrojo se reemplaza con 62 y se crean dos nodos dummynuevos.

Page 11: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Implementación en Java: Preliminares

• ¿Cómo es el árbol vacío ahora?

Respuesta: El árbol vacío es un nodo dummy.

Estructuras de datos - Dr. Sergio A. Gómez 11

Page 12: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

NodoABB

Estructuras de datos - Dr. Sergio A. Gómez 12

public class NodoABB<E extends Comparable<E>> {private E rotulo;private NodoABB<E> padre, izq, der;

public NodoABB( E rotulo, NodoABB<E> padre ) {this.rotulo = rotulo;this.padre = padre;izq = der = null;

}

public E getRotulo() { return rotulo; }public NodoABB<E> getPadre() { return padre; }public NodoABB<E> getIzq() { return izq; }public NodoABB<E> getDer() { return der; }

public void setRotulo( E rotulo ) { this.rotulo = rotulo; }public void setIzq( NodoABB<E> izq ) { this.izq = izq; }public void setDer( NodoABB<E> der ) { this.der = der; }public void setPadre( NodoABB<E> padre ) { this.padre = padre; }

}

Page 13: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

ABB

Estructuras de datos - Dr. Sergio A. Gómez 13

import java.util.Comparator;

public class ABB<E extends Comparable<E>> {protected NodoABB<E> raiz;protected int size;Comparator<E> comp;

public ABB(Comparator<E> comp) { raiz = new NodoABB<E>(null,null); size = 0;this.comp = comp;

}

Page 14: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Estructuras de datos - Dr. Sergio A. Gómez 14

public boolean pertenece( E k ) { return buscar(k).getRotulo() != null;

}

private NodoABB<E> buscar( E k ) {return buscarAux( k, raiz );

}

private NodoABB<E> buscarAux( E k, NodoABB<E> nodov ) {if( nodov.getRotulo() == null ) return nodov;else {

int c = comp.compare( k, nodov.getRotulo() );if( c == 0 ) return nodov;else if( c < 0 ) return buscarAux( k, nodov.getIzq() );else return buscarAux( k, nodov.getDer() );

}}

Page 15: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Estructuras de datos - Dr. Sergio A. Gómez 15

public void insertar( E k ) {NodoABB<E> nodov = buscar( k );if( nodov.getRotulo() == null ) {

nodov.setRotulo( k );nodov.setIzq( new NodoABB<E>( null, nodov ) );nodov.setDer( new NodoABB<E>( null, nodov ) );size++;

}}

Page 16: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

16

// insertar alternativo:public void insertar2( E k ) {

insertarAux( k, raiz ); }

private void insertarAux( E k, NodoABB<E> nodov ) {if( nodov.getRotulo() == null ) {

nodov.setRotulo( k ); size++;nodov.setIzq( new NodoABB<E>( null, nodov ) );nodov.setDer( new NodoABB<E>( null, nodov ) );

} else {int c = comp.compare( k, nodov.getRotulo() );if( c == 0 ) { /* hacer nada */ }else if( c < 0 ) insertarAux( k, nodov.getIzq() );else insertarAux( k, nodov.getDer() );

}}

Page 17: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

17

Nota: El listado inorder de un ABB retorna las claves insertadas ordenadas en forma ascendente.

public String toString() {return inorder( raiz );

}

private String inorder( NodoABB<E> nodov ) {if( nodov.getRotulo() != null ) {

return "(" + inorder( nodov.getIzq()) + nodov.getRotulo() + inorder( nodov.getDer() ) + ")";

} else return "";}

Page 18: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

18

public class TestABB {private static void insertar_imprimir( ABB<Integer> t, int x ) {

t.insertar( x ); System.out.println( "t.insertar("+ x + "): " + t ); }

public static void main( String [] args ) {ABB<Integer> t = new ABB<Integer>( new DefaultComparator<Integer>() );insertar_imprimir( t, 20 ); insertar_imprimir( t, 16 ); insertar_imprimir( t, 64 ); insertar_imprimir( t, 6 ); insertar_imprimir( t, 100 ); insertar_imprimir( t, 3 ); System.out.println( "Pertenece(18): " +

t.pertenece(18) );System.out.println( "Pertenece(100): " +

t.pertenece(100) );t.insertar2( 999 );System.out.println( "t.insertar2("+ 999 + "): " + t );t.insertar2( 4 );System.out.println( "t.insertar2("+ 4 + "): " + t );}}

>java TestABBt.insertar(20): (20)t.insertar(16): ((16)20)t.insertar(64): ((16)20(64))t.insertar(6): (((6)16)20(64))t.insertar(100): (((6)16)20(64(100)))t.insertar(3): ((((3)6)16)20(64(100)))Pertenece(18): falsePertenece(100): truet.insertar2(999): ((((3)6)16)20(64(100(999))))t.insertar2(4): ((((3(4))6)16)20(64(100(999))))

Page 19: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Eliminación

• Paso 1: Buscar el nodo p con la clave k a eliminar

• Paso 2: Cuatro casos:– P es una hoja: Eliminarlo

– P tiene sólo hijo izquierdo: hacer el bypass del padre de p con el hijo izquierdo de p

– P tiene sólo hijo derecho: hacer el bypass del padre de p con el hijo derecho de p

– P tiene dos hijos: Reemplazar el rótulo de p con el de su sucesor inorder y eliminar el sucesor inorder de p.

– Teliminar(h) = O(h)

Resolución de Problemas y Algoritmos - Dr. Sergio A. Gómez 19

Page 20: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Estructuras de datos - Dr. Sergio A. Gómez 20

// retorna null si no pudo eliminar a k, retorna k si la pudo eliminarpublic E eliminar( E k ) {

NodoABB<E> p = buscar( k );if( p.getRotulo() != null ) {

E eliminado = p.getRotulo();eliminarAux( p );size--;return eliminado;

} else return null;}

Page 21: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

21

private boolean isExternal( NodoABB<E> p ) { return p.getIzq().getRotulo() == null &&

p.getDer().getRotulo() == null; }

private boolean soloTieneHijoIzquierdo( NodoABB<E> p ) {return p.getIzq().getRotulo() != null &&

p.getDer().getRotulo() == null;}

private boolean soloTieneHijoDerecho( NodoABB<E> p ) {return p.getDer().getRotulo() != null &&

p.getIzq().getRotulo() == null;}

Page 22: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

22

private void eliminarAux( NodoABB<E> p ) {if( isExternal(p) ) { // p es hoja: Convertir el nodo en un dummy y soltar sus hijos dummy.

p.setRotulo( null ); p.setIzq( null ); p.setDer( null );} else { // p no es hoja

if( soloTieneHijoIzquierdo(p) ) {// Enganchar al padre de p con el hijo izquierdo de pif( p.getPadre().getIzq() == p ) // p es el hijo izquierdo de su padre

p.getPadre().setIzq( p.getIzq() ); // el hijo izq del padre de p es ahora el hijo de pelse // p es el hijo derecho de su padre

p.getPadre().setDer( p.getIzq() ); // el hijo derecho del padre de p es el hijo de pp.getIzq().setPadre( p.getPadre() ); // Ahora el padre del hijo izq de p es su abuelo

} else if( soloTieneHijoDerecho(p) ) {// Enganchar al padre de p con el hijo derecho de pif( p.getPadre().getIzq() == p ) // p es hijo izquierdo de su padre

p.getPadre().setIzq( p.getDer() ); // el hijo izq del padre de p es el hijo de pelse

p.getPadre().setDer( p.getDer() ); // el hijo derecho del padre de p es el hijo de pp.getDer().setPadre( p.getPadre() ); // Ahora el padre del hijo der. de p es su abuelo

} else { // p tiene dos hijos: seteo como rótulo de p al rótulo del sucesor inorder de p.p.setRotulo( eliminarMinimo( p.getDer() ) );

}}

Page 23: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

23

// Elimina el nodo con rótulo mínimo del subárbol que tiene como raíz a p// El mínimo rótulo del subárbol que tiene como raíz a p es el rótulo del primer nodo que // encuentro yendo a la izquierda que no tiene hijo izquierdo private E eliminarMinimo( NodoABB<E> p ) {

if( p.getIzq().getRotulo() == null ) { // El hijo izquierdo de p es un dummyE aRetornar = p.getRotulo(); // salvo el rótulo a devolverif( p.getDer().getRotulo() == null ) { // p es hoja (pues sus hijos son dummy)

p.setRotulo( null ); // Convierto a p en dummy haciendo nulo su rótulop.setIzq( null ); // y desenganchando sus dos hijos dummyp.setDer( null );

} else { // p solo tiene hijo derecho (xq no tiene izquierdo)// Engancho al padre de p con el hijo derecho de p.// Seguro tiene que ser el hijo derecho de su padre.p.getPadre().setDer( p.getDer() );p.getDer().setPadre( p.getPadre() );

}return aRetornar;

} else { // Si p tiene hijo izquierdo, entonces p.getRotulo() no es el mínimo.// El mínimo tiene que estar en el subárbol izquierdoreturn eliminarMinimo( p.getIzq() );

}}

Page 24: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Variaciones• Implementación de Map<K,V> con ABB, dos soluciones:

(a) El árbol se parametriza con E y E se instancia con entradas de K y V.

(b) El árbol y el nodo se pueden parametrizar con K y V.

• Implementación de diccionario con ABB:Los nodos tienen una clave y una lista de entradas con la esa clave.

TfindAll(n) = O(h + s)

Tfind(n) = O(h) donde:

n = cantidad de entradas,

h = altura del ABB y

s = largo lista de entradas con una misma clave.

Estructuras de datos - Dr. Sergio A. Gómez 24

Page 25: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Optimizaciones a la tabla de hash abierto

Teníamos n entradas insertadas en un arreglo de m buckets donde cada bucket es una lista de entradas colisionadas. Enlugar de estructurar los buckets como una lista, se puedenestructurar como ABBs.

Entonces:

Estructuras de datos - Dr. Sergio A. Gómez 25

………

Arreglo de buckets

¡El bucket i-ésimo ahora es un ABB y no unalista!

Nota: Ahora si por algún motivo perdí la distribución uniforme de claves tengo mejores chances de que los buckets grandes no se conviertan en listas muy largas.Sin embargo, el peor escenario, aunque altamente improbable, es que todas la entradas terminen en un mismo bucket y encima vengan en orden ascendente, con lo cual el ABB va a ser una lista.Más adelante, veremos cómo resolver esto con “árboles´de búsqueda balanceados”

0

1…

m-1m

Page 26: Estructuras de Datos Clase 13 –Árboles binarios de búsquedamlg/ed/downloads/Teorias/uns-ed-2019-clase-13... · estructura de datos útil para implementar conjuntos, mapeos y diccionarios

Bibliografía

• Capítulo 10 de M. Goodrich & R. Tamassia, Data Structures and Algorithms in Java. FourthEdition, John Wiley & Sons, 2006.

Estructuras de datos - Dr. Sergio A. Gómez 26