Arboles

9.

´ Arboles

Una estructura de datos con una relaci´n es una ´rbol si y s´lo: o a o La relaci´n es conexa, es decir, existe una composici´n de relaciones entre cualquier par de o o nodos en el ´rbol. a No admite ciclos. Definici´n: Un ´rbol T es un conjunto finito de uno o m´s nodos tal que: (i) hay un nodo especialo a a mente llamado ra´ R; (ii) los dem´s nodos est´n particionados en n ≥ 0conjuntos desconectados ız a a T1 . . . Tn , donde cada uno de estos conjuntos es un ´rbol, as´ llamados sub´rboles de la ra´ As´ a ı a ız. ı: T Ti ∩ Tn = ∅ Padre: El nodo inmediatamente antecesor Hijos: nodos inmediatamente sucesor Grado: n´mero de hijos de un nodo u Nivel: distancia a la ra´ de un nodo ız Profundidad: nivel m´ximo de un ´rbol a a Bosque: ´rboles desconectados a Formas devisualizar un ´rbol son: a Gr´fico: a
A B C D

= {R} ∪ T1 . . . ∪ Tn

(2)

E K L

F

G

H M

I

J

Listas: (A(B(E(K,L),F),C(G),D(H(M),I,J))) 50

Data

0

A

1

1 0 C 0 G

1

0 D 1

0

0

0

B

1

0

F

0

0

H

0

M 0

0

E

0

K

0

L

0 0 I 0 J 0

La representaci´n es esencialmente por listas encadenadas o Teoremas: El ´rbol esconexo pero al eliminar un arco, se convierte en no conexo a El ´rbol no tiene ciclos y es conexo, arcos = nodos − 1 a Al agregar un arco a un ´rbol se crea un ciclo. a

10.

´ Arbol Binario

Definici´n: Un ´rbol binario es un n´mero finito de nodos que es vac´ o consiste de una ra´ con o a u ıo ız dos ´rboles binarios desconectados llamados sub´rbol izquierdo y derecho. Se llaman los nodos que aa no tienen hijos, nodos hojas o terminales. Nodos con uno o dos hijos son llamados nodos internos.

51

structureBTREE(ITEM) declare N EW () → btree M AKEBT REE(btree, item, btree) → btree LCHILD(btree) → btree RCHILD(btree) → btree DAT A(btree) → item IS IN (btree, item) → boolean IS EM P T Y (btree) → boolean for all bt1 , bt2 ∈ BT REE, i, i1 , i2 ∈ item let DAT A(N EW ()) ::= error DATA(M AKEBT REE(bt1 , i, bt2 )) ::= i IS EM P T Y (N EW ()) ::= true IS EM P T Y (M AKEBT REE(bt1 , i, bt2 )) ::= f alse IS IN (N EW (), i) ::= f alse IS IN (M AKEBT REE(bt1 , i1 , bt2 ), i2 ) ::= if i1 = i2 then true else IS IN (bt1 , i2 ) ∨ IS IN (bt2 , i2 ) LCHILD(N EW ()) ::= N EW () LCHILD(M AKEBT REE(bt1 , i, bt2 )) ::= bt1 RCHILD(N EW ()) ::= N EW () RCHILD(M AKEBT REE(bt1 , i, bt2 )) ::= bt2Lema: El m´ximo n´mero de nodos en un nivel i de un ´rbol binario es 2i , i ≥ 0; y el m´ximo a u a a k+1 − 1, k ≥ 0. n´mero de nodos en un ´rbol binario de profundidad k es 2 u a Prueba Por inducci´n o Base inducci´n: La ra´ es el unico nodo en el nivel 0. Por lo tanto, el m´ximo n´mero de nodos o ız ´ a u en el nivel i = 0 es 20 = 2i . Hip´tesis de inducci´n: Para todo j, 0 ≤ j ≤ i, el m´ximon´mero de nodos en el nivel j es 2j . o o a u Paso de inducci´n: El m´ximo n´mero de nodos en el nivel i − 1 es 2i−1 , por la hip´tesis de o a u o inducci´n. Debido a que cada nodo del ´rbol tiene como m´ximo grado 2, el n´mero de nodos o a a u m´ximos en el nivel i es 2 veces el m´ximo n´mero de nodos en el nivel i − 1 o 2i . El m´ximo a a u a n´mero de nodos n en un ´rbol binario de profundidad k esla sumatoria del m´ximo n´mero de u a a u nodos en cada nivel:
k

n=
i=0

2i = 2k+1 − 1

Lema: Por cada ´rbol binario no vac´ T , si n es el n´mero de nodos terminales (hojas) y m es el a ıo u n´mero de nodos de grado 2, entonces n = m + 1. u Prueba: Sea l el n´mero de nodos de grado uno, entonces el n´mero total de nodos N en el ´rbol u u a es N = n + m + l. Todos los nodos en el ´rbolexcepto por la ra´ tienen un arco de llegada. Entonces, N es igual al a ız n´mero de arcos B + 1. Tambi´n, todo arco emana de un nodo de grado uno o de grado dos. As´ u e ı: B = l + 2m. Por lo tanto N = 1 + l + 2m. Substrayendo N = 1 + l + 2m de N = n + m + l nos queda que n = m + 1. 52

10.1.

Representaci´n por arreglos o

Un ´rbol binario se representa en un arreglo del siguiente modo:...