Árboles Binarios PDF

Preview

Summary

Download Árboles Binarios PDF

Description

Árboles Binarios  Árbol donde el número de hijos está limitado a 2  Hijo izquierdo e hijo derecho  Definición Recursiva  Un árbol binario es  Vacío  Una raíz, un hijo izquierdo y otro derecho  Los hijos pueden ser a su vez árboles vacíos

Uso de Árboles Binarios  Árboles de expresiones  Las hojas son operandos, el resto son operadores  (a+b)*(c-d)

* -

+

a

b

c

d

Uso de árboles binarios  Árbol de codificación de Huffman  Compresión de datos  Cada símbolo del alfabeto se guarda en una hoja  Código se obtiene siguiendo el camino desde la raíz al símbolo  Arista izquierda es un 0  Arista derecha es un 1

a d b

a=0 b=100 c=101 d=10

c

Operaciones en Árboles  Operaciones de ABM  Añadir un nodo  Buscar un nodo  Eliminar un nodo  Recorrido del árbol de manera ordenada  PreOrden  InOrden (Simétrico)  PostOrden  Por niveles

Recorrido PreOrden  Visitar el nodo  Recorrer el subarbol izquierdo  Recorrer el subarbol derecho

Ej: F, B, A, D, C, E, G, I, H

Recorrido PreOrden: implementación //En Clase ArbolBinario void preorder(){ this.raiz.preorder(); }

//En Clase Nodo void preorder(){ System.out.println(this.value); if (this.left != null) this.left.preorder(); if (this.right != null) this.right.preorder(); }

Recorrido Simétrico  Recorrer el subarbol izquierdo  Visitar el nodo  Recorrer el subarbol derecho Ej: A, B, C, D, E, F, G, H, I void inorder(){ if (this.left != null) this.left.inorder(); System.out.println(this.value); if (this.right != null) this.right.inorder(); }

Recorrido PostOrden  Recorrer el subarbol izquierdo  Recorrer el subarbol derecho  Visitar el nodo

Ej: A, C, E, D, B, H, I, G, F void postorder(){ if (this.left != null) this.left.postorder() if (this.right != null) this.right.postorder() System.out.println(this.value) }

Recorrido Por Niveles  Visitar todos los nodos de un nivel  Ir al siguiente nivel

Ej: F, B, G, A, D, I, C, E, H

Que estructura de datos podemos usar para implementar un recorrido por niveles?

Una cola

Recorrido por niveles: implementacion //En Clase ArbolBinario void porniveles( ){ Cola q = new Cola( ); q.insertar( this.raiz ); while ( !q.empty( ) ){ Node node = q.quitarPrimero( ); System.out.println( node.value ); if( node.left != null ) q.insertar( node.left ); if( node.right != null ) q.insertar( node.right ); } }

Recorrido por niveles: Ejemplo F

B G A D

I

C E H

Árboles Binarios de Búsqueda  Permiten realizar búsquedas en tiempo logarítmico

 Para cada nodo  Los nodos con clave menor están en el subárbol izquierdo  Los nodos con clave mayor están en el subárbol derecho  No permite elementos duplicados  Qué recorrido del árbol muestra los elementos ordenados?

Un recorrido simétrico Búsqueda  Comenzar en la raíz  Seguir en hijo izquierdo o derecho dependiendo de las comparaciones  Seguir hasta llegar al elemento (búsqueda exitosa)  O hasta llegar a null (búsqueda sin éxito)  La búsqueda tiene costo logarítmico en promedio  Como se realiza la búsqueda del mínimo/máximo elemento?  Ir siempre a la izquierda/derecha  Costo es logarítmico en promedio  Cual es el costo en el caso peor?  O(N)

Inserción  Insertar un elemento es trivial  Hacemos una búsqueda no exitosa  En el lugar donde encontramos el null, insertamos el elemento  Tiene costo logarítmico en promedio  Ejemplo: inserción del elemento 6

7 2 1

9 1 2

5 3

Eliminación

6

1 0

1 5

 La eliminación es la operación más complicada  Los nodos interiores mantienen el árbol conectado  Hay varios casos  El nodo a eliminar es una hoja  Se elimina sin más  El nodo tiene sólo un hijo  El padre del nodo apunta al hijo  La raíz es un caso especial, ya que no tiene hijos  El nodo tiene dos hijos  Remplazamos el nodo con el menor elemento de su subárbol derecho...