PDF de programación - Algoritmos y Estructuras de Datos - Árboles Generales y Árboles Binarios

Algoritmos y Estructuras de Datos

Árboles Generales y Árboles Binarios

Guillermo Román Díez

groman@fi.upm.es

Universidad Politécnica de Madrid

Curso 2015-2016

Guillermo Román, UPM

AED: Introducción

1/22

Árboles generales

El objetivo de los árboles es organizar los datos de forma
jerárquica

Se suelen utilizar en las implementaciones de otros TADs
(colas con prioridad, maps ordenados, . . . )

Árbol General
“ Un árbol general es o bien vacío o bien tiene dos componentes: (1) un
nodo raíz que contiene un elemento, y (2) un conjunto de cero o más
(sub)árboles hijos.”

Un árbol está formado por nodos

Un nodo tiene un elemento y un conjunto de nodos que son la
raíz de los subárboles hijos

Guillermo Román, UPM

AED: Introducción

2/22

Terminología

Raíz (”root”): nodo sin padre
Nodo interno (”internal node”): nodo con al menos un hijo
Nodo externo (”external node”): nodo sin hijos
Nodo hoja (”leaf node”): sinónimo de nodo externo,
usaremos estos dos nombres indistintamente
Subárbol (”subtree”): árbol formado por el nodo considerado
como raíz junto con todos sus descendientes
Ancestro de un nodo: un nodo ’w’ es ancestro de ’v’ si y sólo
si ’w’ es ’v’ o ’w’ es el padre de ’v’ o ’w’ es ancestro del padre
de ’v’
Descendiente de un nodo (la inversa de ancestro): ’v’ es
descendiente de ’w’ si y sólo si ’w’ es ancestro de ’v’

Guillermo Román, UPM

AED: Introducción

3/22

Terminología

Hermano (”sibling”) de un nodo: nodo con el mismo padre
Arista (”edge”) de un árbol: par de nodos en relación
padre-hijo o hijo-padre
Grado (”degree”) de un nodo: el número de hijos del nodo
Grado (”degree”) de un árbol: el máximo de los grados de
todos los nodos
Camino (”path”) de un árbol: secuencia de nodos tal que
cada nodo consecutivo forma una arista. La longitud del
camino es el número de aristas
Árbol ordenado (”ordered tree”): existe un orden lineal
(total) definido para los hijos de cada nodo: primer hijo,
segundo hijo, etc. . .

Guillermo Román, UPM

AED: Introducción

4/22

Terminología

La profundidad de un nodo (”depth”) es la longitud del
camino que va desde ese nodo hasta la raíz (o viceversa)
La altura de un nodo (”height”) es la longitud del mayor de
todos los caminos que van desde el nodo hasta una hoja
Altura de un árbol no vacío: la altura de la raíz
Nivel (’level’): conjunto de nodos con la misma profundidad.
Así, tenemos desde el nivel 0 hasta el nivel ’h’ donde ’h’ es la
altura del árbol

Guillermo Román, UPM

AED: Introducción

5/22

Interfaz Tree

public i n t e r f a c e Tree <E > {

public int size () ;

public boolean isEmpty () ;

public Iterator <E > i ter ato r () ;

public Iterable < Position <E > > p o s i t i o n s () ;

public E replace ( Position <E > v , E e )

throws I n v a l i d P o s i t i o n E x c e p t i o n ;

public Position <E > root () throws E m p t y T r e e E x c e p t i o n ;
...

}

Guillermo Román, UPM

AED: Introducción

6/22

Interfaz Tree<E>

public i n t e r f a c e Tree <E > {

...
public Position <E > parent ( Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n ,

B o u n d a r y V i o l a t i o n E x c e p t i o n ;

public Iterable < Position <E > > c hil dre n ( Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n ;

public boolean i s I n t e r n a l ( Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n ;

public boolean i s E x t e r n a l ( Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n ;

public boolean isRoot ( Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n ;

}

Guillermo Román, UPM

AED: Introducción

7/22

Interfaz Tree<E>

Tree<E> es un interfaz pensado para trabajar directamente
con posiciones
Los métodos trabajan con posiciones y no con árboles (no son
recursivos)
Tenemos dos métodos que devuelven un Iterable

children devuelve un Iterable para recorrer los hijos de un
nodo
positions() devuelve un Iterable que es un snapshot de
los nodos del árbol

El interfaz sólo se dispone de métodos observadores
Sólo está pensado para hacer recorridos de árboles
Los métodos modificadores se definirán en las clases que
implementan el interfaz

Pregunta

¿qué os parece esto?

Guillermo Román, UPM

AED: Introducción

8/22

Ejemplos recorrido

Ejemplo

Método que indica si un nodo es ancestro de otro

boolean a nce str o ( Tree <E > t ,

Position <E > w ,
Position <E > v )

return w == v || ! t . isRoot ( v ) &&

( w == t . parent ( v ) || anc est ro (t ,w , t . parent ( v ) ) ) ;

throws I n v a l i d P o s i t i o n E x c e p t i o n {

}

Guillermo Román, UPM

AED: Introducción

9/22

Ejemplos recorrido

Ejemplo

Método que indica si un nodo es hermano de otro

boolean i s S i b l i n g ( Tree <E > t ,

Position <E > w ,
Position <E > v )

if ( w == v || t . isRoot ( w ) || t . isRoot ( v ) )

throws I n v a l i d P o s i t i o n E x c e p t i o n {

return false ;

else

return t . parent ( w ) == t . parent ( v ) ;

}

Guillermo Román, UPM

AED: Introducción

10/22

Ejemplos recorrido

Ejemplo

Método que indica si un nodo es hermano de otro (algo retorcido)

boolean i s S i b l i n g ( Tree <E > t , Position <E > w ,

Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n {

if ( w == v || t . isRoot ( w ) || t . isRoot ( v ) )

return false ;

else {

Iterator < Position <E > > it = t . parent ( w ) . c hil dre n () .

it era tor () ;

boolean found = false ;
while ( it . hasNext () && !( found = it . next () == v ) )

;

return found ;

}

}

Guillermo Román, UPM

AED: Introducción

11/22

Ejemplos recorrido

Ejemplo

Método que calcula la profundidad de un nodo de un árbol dado
(iterativo)

int depth ( Tree <E > tree , Position <E > v )

int c ;
for ( c = 0; ! tree . isRoot ( v ) ; c ++ , v = tree . parent ( v ) )

throws I n v a l i d P o s i t i o n E x c e p t i o n {

;

return c ;

}

Guillermo Román, UPM

AED: Introducción

12/22

Ejemplos recorrido

Ejemplo

Método que calcula la profundidad de un nodo de un árbol dado
(recursivo)

int depth ( Tree <E > tree , Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n {

if ( tree . isRoot ( v ) )

return 0;

else

return 1 + depth ( tree , tree . parent ( v ) ) ;

}

Guillermo Román, UPM

AED: Introducción

13/22

Ejemplos recorrido

Ejemplo

Método que recorre un árbol en pre-orden

String t o S t r i n g P r e o r d e r ( Tree <E > tree , Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n {

String s = v . element () . t oSt rin g () ;

for ( Position <E > w : tree . chi ldr en ( v ) ) {
s += ” , ” + t o S t r i n g P r e o r d e r ( tree , w ) ;

}
return s ;

}

Guillermo Román, UPM

AED: Introducción

14/22

Ejemplos recorrido

Ejemplo

Método que recorre un árbol en post-orden

String t o S t r i n g P o s t o r d e r ( Tree <E > tree , Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n {

String s = ””;
for ( Position <E > w : tree . chi ldr en ( v ) ) {
s += t o S t r i n g P o s t o r d e r ( tree , w ) + ” ”;

}

s += v . element () ;
return s ;

}

Guillermo Román, UPM

AED: Introducción

15/22

Árboles Binarios

Es un tipo especial de árbol en el que todo nodo tiene como
mucho 2 hijos

Es un árbol ordinario con grado 2

Árbol Binario
“Un árbol binario es o bien vacío o bien consiste en (1) un nodo raíz, (2)
un (sub)árbol izquierdo, y (3) un (sub)árbol derecho.”

Podemos hablar de varios tipos:

Arbol binario propio (proper binary tree): todo nodo interno
tiene 2 hijos
Arbol binario impropio (improper binary tree): árbol binario
que no es propio

Guillermo Román, UPM

AED: Introducción

16/22

Árboles Binarios

Árbol binario perfecto
“es un árbol binario propio con el máximo número de nodos: 2h+1 − 1”

h
= 0
2^{ h +1} -1 = 1

h
= 1
2^{ h +1} -1 = 3

h
= 2
2^{ h +1} -1 = 7

o

o

/ \

o

o

o

/ \

o

o

/ \ / \

o

oo

o

Guillermo Román, UPM

AED: Introducción

17/22

Árboles Binarios

Árbol binario equilibrado

“Un árbol en el que para todo nodo, el valor absoluto de la diferencia de
altura entre los dos subárboles hijos es como máximo 1.”

Es decir, un árbol en el que para todo nodo con altura h, o
bien sus dos hijos tienen la misma altura, h − 1, o un hijo
tiene altura h − 1 y el otro h − 2
Todo subárbol de un árbol equilibrado es también equilibrado

Guillermo Román, UPM

AED: Introducción

18/22

Árboles Binarios

public i n t e r f a c e BinaryTree <E > extends Tree <E > {

public Position <E > left ( Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n ,

B o u n d a r y V i o l a t i o n E x c e p t i o n ;

public Position <E > right ( Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n ,

B o u n d a r y V i o l a t i o n E x c e p t i o n ;

public boolean hasLeft ( Position <E > v ) throws

I n v a l i d P o s i t i o n E x c e p t i o n ;

public boolean h asR igh t ( Position <E > v ) throws

I n v a l i d P o s i t i o n E x c e p t i o n ;

}

Guillermo Román, UPM

AED: Introducción

19/22

Ejemplos recorrido

Ejemplo

Método que devuelve la altura de un árbol binario

int height ( BinaryTree <E > tree , Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n {

if ( tree . i s E x t e r n a l ( v ) ) return 0;

int hi = 0 , hd = 0;

if ( tree . hasLeft ( v ) )

hi = height ( tree , tree . left ( v ) ) ;

if ( tree . h asR igh t ( v ) )

hd = height ( tree , tree . right ( v ) ) ;

return 1 + Math . max ( hi , hd ) ;

}

Guillermo Román, UPM

AED: Introducción

20/22

Ejemplos recorrido

Ejemplo

Recorrido de un árbol binario en pre-orden y en post-orden

void p reo rde r ( BinaryTree <E > tree , Position <E > v )

throws I n v a l i d P o s i t i o n E x c e p t i o n {

/* visit v . element () */
if ( t . hasLeft ( v ) )
if ( t . h asR igh t ( v ) ) p reo rde r ( tree , tr