Estructuras

de Datos.
Grado en Ingeniera Inform7ca, Ingeniera del So;ware e Ingeniera de
Computadores
ETSI Inform7ca
Universidad de Mlaga

Jos E. Gallardo, Francisco Gu7rrez, Pablo Lpez, Blas C. Ruiz

Dpto. Lenguajes y Ciencias de la Computacin
Universidad de Mlaga

rboles

rboles binarios Autn7cos / Perfectos / Completos

Relacin entre el peso y la altura
rboles binarios en Haskell; recorrido . Construccin de

un rbol binario de altura mnima

Colas con prioridad

MonYculo binario (Binary Heap) como AB completo

Insercin y eliminacin.
Representacin de un AB Completo con un Array
MonYculos en Java; representacin va arrays

La espina derecha 7ene longitud logartmica

Mezcla de monYculos zurdos (WBLH)
Representacin de Colas de prioridad con monYculos
zurdos
Comportamiento de los WBLHs
Construccin de un monYculo zurdo en 7empo lineal
Heap Sort
MonYculos zurdos en Java

Iterador En-Orden para BST

Either: Tipo unin en Java
Implementacin de iteradores

rboles AVL

MonYculos zurdos (Weight Biased Le;ist Heaps)

Insercin. Tree Sort

Bsqueda de un elemento, del mximo y del mnimo
Eliminacin
Complejidad de las operaciones
BST en Java

Iteradores para BST en Java

Especicacin. Implementacin lineal (Haskell)

MonYculos. Propiedad del monYculo (Heap-Order Prop.)

Terminologa, Denicin formal

rboles en Haskell

rboles binarios

rboles binarios de bsqueda

(Binary Search Tree,BST)

Altura de un rbol AVL. El nmero de oro

Rotaciones en rboles binarios de bsqueda
Insercin, descompensacin y rebalanceo por rotacin
Bsqueda y eliminacin en un rbol AVL
Complejidad de operaciones
rboles AVL en Java

Diccionarios

Signatura y axiomas
Implementacin de diccionarios va rboles AVL.

 Son las estructuras no lineales ms importantes

La relacin entre los objetos es jerrquica
Ms rica que la relacin lineal (antes despus )

Son esenciales en la organizacin de datos

Muchos algoritmos son ms ecientes va rboles
10

:->
:/\

:\/

Var

No

Var

Var

Var

"p"

"q"

"q"

15

"p"

12

20

Los rboles almacenan datos jerrquicamente

Cada elemento 7ene un padre (salvo la raz)
Cada elemento 7ene cero o ms hijos
Los de cero hijos se denominan hojas

Un nodo con algn hijo se llama interno

Se suelen dibujar inver&dos:

raz

2 es padre
de 5 y 6

interno

2
5 es un
hijo de 2
hoja

6 es un hijo
de 2

9
4

El padre del padre es el abuelo

Los hijos del mismo padre se llaman hermanos
Un arco es un par de nodos (u,v) tal que u es el padre de v
Un camino es una secuencia de nodos tal que:
o es vaca, o 7ene un solo nodo,
1 es abuelo de 5, 6,
7, 8 y 9
o 7ene varios , y cualesquiera
dos consecu7vos forman un arco

Un camino

1
Un arco

6 es hermano de 5

9
5

 Un rbol es un conjunto de nodos junto a una

relacin padre-hijo tal que :

Si el conjunto es vaco, el rbol es el rbol vaco

En otro caso:
Es posible seleccionar un nodo r, llamado raz
Los restantes nodos pueden agruparse en conjuntos disjuntos
tales que cada uno de estos conjuntos es, a su vez, un rbol.
Una raz (si existe) de cada uno de stos rboles se llama hijo
de r.
Veamos como esta denicin se describe en Haskell

data Tree a = Empty | Node a [Tree a] deriving Show

Lista de subrboles hijos
Valor del nodo
Constructor del rbol vaco

tree1 :: Tree Int
tree1 =
Node 1 [ Node 2 [ Node 4 [ ]
, Node 5 [ ]
, Node 6 [ ]
]

, Node 3 [ Node 7 [ ] ]
]

Una hoja

Suma los valores de los nodos

4

sumT :: (Num a) => Tree a -> a
sumT Empty
= 0
sumT (Node x ts) = x + sum [sumT t | t <- ts]

Los datos en un rbol se organizan en niveles:

Nivel 0

La raz est en el nivel 0

Los hijos de la raz en el nivel 1

Los nietos en el nivel 2

Nivel 1

etc.
4

Nivel 2

La altura de un rbol se dene como:

heightT
heightT
heightT
heightT

:: Tree a -> Int

Empty
= 0
(Node x []) = 1
(Node x ts) = 1 + maximum [heightT t | t <- ts]

 rbol binario:
Cada nodo 7ene a lo sumo dos hijos
Los hijos se denominan hijo izquierdo e hijo derecho

rbol Binario Autn7co:

Salvo las hojas, cada nodo

7ene dos hijos

rbol Binario Completo:

Todos los nodos son completos

(con dos hijos) salvo quizs

los del l7mo nivel que
aparecen todos pegados a la izquieda

rbol Binario Perfecto:

Son autn7cos con todas

las hojas en el nivel mximo

10

 n: nmero de nodos
h: altura

Se da la igualdad para cada rbol pefecto

Para todo rbol binario no vaco

h n 2h-1 (= 1 + 2 + 22 + + 2h-1)
1+log2(n) h n
1+n <=2h
log2(1+n) <= h
log2(n) < log2 (1+n) <= h
1 +log2(n) <= h

3 n 23 -1
h= 3

n= 7

1+log2(7) h 7

11

data TreeB a = EmptyB | NodeB a (TreeB a) (TreeB a) deriving Show

Constructor del rbol vaco
Valor del nodo
Subrbol derecho
Subrbol
i
zquierdo



tree2 :: TreeB Int
tree2 =
NodeB 1 (NodeB 2 (NodeB 4 EmptyB EmptyB)
(NodeB 5 EmptyB EmptyB))
(NodeB 3 (NodeB 6 EmptyB EmptyB)
EmptyB)

-- suma de valores de los nodos

sumB :: (Num a) => TreeB a -> a
sumB EmptyB
= 0
sumB (NodeB x lt rt) = x + sumB lt + sumB rt
Subrbol izquierdo
(Le; subtree)

Right subtree

12

data TreeB a = EmptyB | NodeB a (TreeB a) (TreeB a) deriving Show

la lista de nodos de cierto nivel de un rbol
-
atLevelB
:: Int -> TreeB a -> [a]

atLevelB _ EmptyB
= []
atLevelB 0 (NodeB x lt rt) = [x]
atLevelB n (NodeB x lt rt) = atLevelB (n-1) lt ++ atLevelB (n-1) rt

Nivel 0

Main> atLevelB 0 tree2

[1]

Nivel 1

Main> atLevelB 1 tree2

[2,3]

Nivel 2

Main> atLevelB 2 tree2

[4,5,6]

13

- caminos hasta cierto nodo (desde la raz)

pathsToB
:: (Eq a) => a -> TreeB a -> [[a]]

pathsToB
x EmptyB = []

pathsToB x (NodeB y lt rt)
| x==y
= [y] : ps
| otherwise
= ps
where
ps = map (y:) (pathsToB x lt ++ pathsToB x rt)

Main> pathsToB 5 tree3

[[1,2,5]]
Main> pathsToB 2 tree3
[ [1,2] , [1,3,2]
]

Main> head $ pathsToB 2 tree3
[1,2]

14

Recorrido o exploracin de un rbol: proceso que visita

cada nodo exactamente una vez

Los recorridos se clasican segn el orden de visita

Los rdenes de visita ms usuales para rboles binarios

(que pueden generalizarse para cualquier rbol) son:
Pre-Orden
En-Orden (o en profundidad)
Post-Orden
En anchura (se vern ms tarde)
15

preOrderB :: TreeB a -> [a]

preOrderB EmptyB
= []
preOrderB (NodeB x lt rt) = [x] ++ preOrderB lt ++ preOrderB rt

inOrderB :: TreeB a -> [a]
-- o recorrido en profundidad
inOrderB EmptyB
= []
inOrderB (NodeB x lt rt) = inOrderB lt ++ [x] ++ inOrderB rt

postOrderB :: TreeB a -> [a]
postOrderB EmptyB
= []
postOrderB (NodeB x lt rt) = postOrderB lt ++ postOrderB rt ++ [x]

Main> preOrderB tree4

[1,2,4,5,3,6,7]
Main> inOrderB tree4
[4,2,5,1,6,3,7]
Main> postOrderB tree4
[4,5,2,6,7,3,1]

16

Sea xs una lista

Pretendemos construir un rbol binario t de altura
mnima, vericando adems inOrderB t = xs
minTreeB [1..7] =>

minTreeB [1..6] =>

17

Prelude> splitAt 2 [10..15]

([10,11],[12,13,14,15])
Prelude> splitAt 3 [10..15]
([10,11,12],[13,14,15])
Prelude> quickCheck p_minTreeB
minTreeB :: [a] -> TreeB a
+++ OK, passed 100 tests.
minTreeB []
= EmptyB
minTreeB xs
= NodeB z (minTreeB yz) (minTreeB zs)
where
m = length xs `div` 2
(yz,z:zs) = splitAt m xs

p_minTreeB xs = n>0 ==> inOrderB t == xs
&& heightB t == 1 + log2 n
where
t = minTreeB xs

n = length xs
Es fcil demostrar estas dos igualdades por

induccin sobre la longitud de la lista xs
log2 :: Int -> Int
log2 x = truncate (logBase 2 (fromIntegral x))

18

minTreeB :: [a] -> TreeB a

minTreeB []
= EmptyB
minTreeB xs
= NodeB z (minTreeB ys) (minTreeB zs)
where
m = length xs `div` 2
(ys,z:zs) = splitAt m xs


Sea T(n) el nmero de pasos para evaluar minTreeB sobre una lista con n

elementos:
T(0) = 1
T(n) = O(n) + 2 T(n/2), si n > 0
splitAt es O(n)

La solucin T(n) est en O(n log n) L

19

minTreeB' :: [a] -> TreeB a

minTreeB' xs = fst (aux (length xs) xs)

aux :: Int -> [a] -> (TreeB a, [a])
aux 0 xs = (EmptyB, xs)
aux 1 xs = (NodeB (head xs) EmptyB EmptyB,
aux n xs = (NodeB y t1 t2, zs)
where
m = div n 2
(t1, y:ys) = aux m xs
(t2, zs) = aux (n-m-1) ys

aux n xs devuelve un rbol con los n

primeros elementos de xs y el resto de la

lista (drop n xs). Estamos resolviendo
un problema ms general
tail xs)

Sea T(n) el nmero de pasos para evaluar minTreeB' sobre una

lista con n elementos:
T(0) = 1
T(n) = O(1) + 2 T(n/2), si n > 1
La solucin T(n) es de orden O(n) J
20

Consideremos que existe una relacin de orden

entre los elementos a encolar (edad, sueldo,),
de forma que se a7enda antes a los de mayor
prioridad: los ms jvenes, los de menor
sueldo, en deni7va, los menores para la
relacin de orden: SIFO (Smallest in, rst out)
Ser interesante organizar los elementos en la
cola de forma que la seleccin del primero a
atender, la eliminacin de ste, y la inclusin
de uno nuevo sean ecientes.

vip

Los elementos pueden insertarse en cualquier orden pero son

extrados de la cola de acuerdo con su prioridad.
21

-- devuelve una cola vaca

empty :: PQueue a

-- test para colas vacas
isEmpty :: PQueue a -> Bool

-- inserta un elemento en una cola de prioridad
enqueue :: (Ord a) => a -> PQueue a -> PQueue a

-- devuelve el elemento de mnima prioridad
first :: (Ord a) => PQueue a -> a

-- devuelve la cola obtenida al eliminar
-- el elemento de mnima prioridad
dequeue :: (Ord a) => PQueue a -> PQueue a

22

isEmpty empty

-- q1

not (isEmpty (enqueue x q))

-- q2

first (enqueue x empty) == x

-- q3

dequeue (enqueue x empty) == empty

-- q4

Los anteriores axiomas coinciden con los de Queue. Tres adicionales

capturan el comportamiento SIFO (smallest in, rst out) :
Los elementos con

igual prioridad salen

first (enqueue y (enqueue x q)) ==

first (enqueue (min x y) q)

en orden FIFO

dequeue (enqueue y (enqueue x q)) ==

enqueue (max x y ) (dequeue (enqueue (min x y ) q))

Ejercicio: probar first $ enq 3 $ enq 1 $ enq 2 empty == 1

-- pq1
-- pq2

23

module DataStructures.PriorityQueue.LinearPriorityQueue
( PQueue
empty
-- :: PQueue a
isEmpty -- :: PQueue a -> Bool
enqueue -- :: (Ord a) => a -> PQueue a -> PQueue a
first
-- :: PQueue a -> a
dequeue -- :: PQueue a -> PQueue a
) where

data PQueue a = Empty | Node a (PQueue a)

empty :: PQueue a
empty = Empty

isEmpty :: PQueue a -> Bool
isEmpty Empty = True
isEmpty _
= False

enqueue :: (Ord a) => a -> PQueue a -> PQueue a
Los elementos son encolados
enqueue x Empty = Node x Empty
en orden ascendente
enqueue x (Node y q)
Recursivamente, encola
| y <= x
= Node y (enqueue x q)
x detrs de y
| otherwise
= Node x (Node y q)
24


first :: PQueue a -> a
first Empty
= error "first on empty queue"
first (Node x _) = x
El elemento mnimo

aparece al principio


dequeue :: PQueue a -> PQueue a
dequeue Empty
= error "dequeue on empty queue"
dequeue (Node _ q) = q
Ejercicio: implementar la
Cola con Prioridad en Java
usando una lista enlazada

25

 Coste para la implementacin lineal:

Operacin

Coste

empty

O(1)

isEmpty

O(1)

enqueue

O(n)

first

O(1)

dequeue

O(1)

L pero podemos mejorarla

Veremos implementaciones de colas de prioridad que

mejoran enqueue, pero empeoran dequeue.
26

Un monYculo (heap) es un rbol que verica la siguiente

propiedad de orden (Heap-Order Property o HOP)
El valor de cada nodo dis7nto de la raz, es mayor o igual al valor de

su padre

Este no es
un heap L

Un heap J

0
Equivalentemente: la secuencia de nodos de cualquier camino desde

la raz a una hoja es ascendente

El valor mnimo est en la raz J

27

Un monYculo binario es un rbol binario completo que

sa7sface HOP (Heap-Order property)
Un montculo
binario J

Un montculo
binario J

Este no es un
completo L

Recordemos: la altura de un rbol binario completo con

n elementos es 1+log2(n). Luego la altura de un
monYculo binario ser mnima.
28

Queremos aadir un elemento a un monYculo binario de

forma que el resultado sea otro monYculo binario

insert(0)

29

Insercin: se realiza en dos fases (colocar al fondo, y reotar)

1) Colocar el nuevo elemento en la primera posicin libre:
A la derecha del l7mo nodo del l7mo nivel, o bien
A la izquierda del siguiente nivel si el l7mo est completo

El resultado es un
rbol completo J

2) Mientras que el nuevo elemento sea menor que el padre:

Intercambiar el nuevo con el padre

insert(0)
0
insert(0)

30

Insercin: se realiza en dos fases

1) Colocar el nuevo elemento en la primera posicin libre:
A la derecha del l7mo nodo del l7mo nivel, o bien
A la izquierda del siguiente nivel si el l7mo est completo
2) Mientras que el nuevo elemento sea menor que el padre:

Intercambiar el nuevo con el padre

Para reestablecer la
propiedad HOP J

insert(0)

3
0

31

Insercin: se realiza en dos fases

1) Colocar el nuevo elemento en la primera posicin libre:
A la derecha del l7mo nodo del l7mo nivel, o bien
A la izquierda del siguiente nivel si el l7mo est completo
2) Mientras que el nuevo elemento sea menor que el padre:

Intercambiar el nuevo con el padre

insert(0)

Swap 0 3

Para reestablecer la
propiedad HOP J

32

Insercin: se realiza en dos fases

1) Colocar el nuevo elemento en la primera posicin libre:
A la derecha del l7mo nodo del l7mo nivel, o bien
A la izquierda del siguiente nivel si el l7mo est completo
2) Mientras que el nuevo elemento sea menor que el padre:

Intercambiar el nuevo con el padre

Para reestablecer la
propiedad HOP J

Un montculo
binario J
insert(0)

Swap 0 3

Swap 0 1

1
3

33

Recordemos que un rbol completo con n elementos

7ene altura 1+log2(n)
500
450
400
350

Nmero de pasos

En el peor caso, la insercin

necesita un nmero de pasos
proporcional a log2(n)

300
250

Enorme diferencia
entre n y log n

200
150

Luego, insert est en O(log n) J

100
50

log n

N de nodos

34

 Sea minChild(u) el valor mnimo de los dos hijos del nodo u

Este puede ser el izquierdo o el derecho

La eliminacin de la raz se realiza en dos fases (subir el l7mo, y hundirlo)

1) Pasar el l7mo elemento
u a la raz
2) Mientras u > minChild(u) :

Intercambiar minChild(u) con u

Esta fase conserva la

completitud J

7
Delete root

35

 Sea minChild(n) el valor mnimo de los dos hijos del nodo n

Este puede ser el izquierdo o el derecho

La eliminacin de la raz se realiza en dos fases

1) Pasar el l7mo elemento u a la raz
2) Mientras u > minChild(u) :

Intercambiar minChild(u) c on u

Reestablecer la
propiedad HOP J

7
Delete root

2
5

3
4

36

 Sea minChild(n) el valor mnimo de los dos hijos del nodo n

Este puede ser el izquierdo o el derecho

La eliminacin de la raz se realiza en dos fases

1) Pasar el l7mo elemento u a la raz

Reestablecer la
propiedad HOP J

2) Mientras u > minChild(u) :

Intercambiar minChild(u) c on u

7
Delete root

2
5

3
4

Swap 7 2

7
5

37

 Sea minChild(n) el valor mnimo de los dos hijos del nodo n

Este puede ser el izquierdo o el derecho

La eliminacin de la raz se realiza en dos fases

1) Pasar el l7mo elemento u a la raz

Reestablecer la
propiedad HOP J

2) Mientras u > minChild(u) :

Intercambiar minChild(u) c on u

Swap 7 2

Delete root

7
5

38

 Sea minChild(n) el valor mnimo de los dos hijos del nodo n

Este puede ser el izquierdo o el derecho

Eliminacin de la raz: se realiza en dos fases

1) Pasar el l7mo elemento u a la raz

Reestablecer la
propiedad HOP J

2) Mientras u > minChild(u) :

Intercambiar minChild(u) c on u

El montculo
final J
Swap 7 2

Delete root

Swap 7 4

7
5

4
5

39

Los nodos de un ABC pueden colocarse fcilmente en forma consecu7va

dentro de un array por niveles:
a

Nivel 0
Nivel 1
Nivel 2

b
d

0
a

Nivel l 0

1
b

2
c

3
d

4
e

Nivel 1

5
f

Nive l 2

f
hijos

Padres e hijos pueden localizarse

fcilmente va aritmBca elemental:
La raz 7ene ndice 0
Para el nodo de ndice i:
El hijo izquierdo ocupa la pos. 2*i+1
El hijo derecho ocupa la pos. 2*i+2
El padre ocupa la pos. (i-1)/2

0
a

1
b

2
c

3
d

4
e

5
f

padres
40


package dataStructures.heap;

public interface Heap<T extends Comparable<? super T>> {
boolean isEmpty();
El tipo T de los elementos del
montculo debe implementar
int
size();
el mtodo (relacin de orden)
compareTo
void
insert(T x);
T
minElem();
void
delMin();
}

41

package dataStructures.heap;

public class BinaryHeap<T extends Comparable<? super T>>


implements Heap<T> {

private T elems[];
private int size; // number of elements in heap

private static int INITIAL_CAPACITY = 128;

public BinaryHeap() {
elems = (T[]) new Comparable[INITIAL_CAPACITY];
size = 0;
}

private void ensureCapacity() {
if(size == elems.length)
elems = Arrays.copyOf(elems,2*elems.length);
}

public int size() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

El tipo T de los elementos del

montculo debe implementar
el mtodo (relacin de orden)
compareTo

42

// true if elems[idx1] < elems[idx2]

private boolean lessThan(int idx1, int idx2) {
return elems[idx1].compareTo(elems[idx2]) < 0;
}
// swaps elements in array elems at positions idx1 and idx2
private void swap(int idx1, int idx2) {
T aux = elems[idx1];
elems[idx1] = elems [idx2];
elems[idx2] = aux;
}

43

private static int ROOT_INDEX = 0; // root of heap is at index 0

private boolean isRoot(int idx) { // true if idx is index at root of tree

return idx==ROOT_INDEX;
}

private int parent(int idx) { // index for parent of node with index idx
return (idx-1) / 2; // integer division
}

private int leftChild(int idx) { // index for left child of node with index idx
return 2*idx+1;
}

private int rightChild(int idx) { // index for right child of node with index idx
return 1+leftChild(idx);
}

private boolean isNode(int idx) { // true if idx corresponds to index of a node in tree
return idx<size;
}
private boolean hasLeftChild(int idx) { // true if node with index idx has a left child
return leftChild(idx)<size;
}

private boolean isLeaf(int idx) { //returns true if node with index idx is a leaf node
return !hasLeftChild(idx); // !hasLeftChild(idx) !hasRightChild(idx)
44
}

private void heapifyUp(int idx) {

while(!isRoot(idx)) {
= (idx-1) / 2
int idxParent = parent(idx);

if(lessThan(idx,idxParent)) {
swap(idx,idxParent);

idx = idxParent; // move to parent node for next iteration
} else
break;
heapifyUp(n) est en O(log n)
}

}

public void insert(T x) {
ensureCapacity();
elems[size] = x; // put new element at right in last level of tree
heapifyUp(size); // move element up to enforce heap-order property
size++;

}
45

public T minElem() {
if(isEmpty())
throw new EmptyHeapException("minElem on empty heap");
else
return elems[ROOT_INDEX];
}

El mnimo siempre
se encuentra en la
raz J

46

private void heapifyDown() {

int idx = ROOT_INDEX; // start at root of tree
2*idx+1 >= size

while(!isLeaf(idx)) {
int idxChild = leftChild(idx);
=2*idx+1
int idxRightChild = rightChild(idx);
if(isNode(idxRightChild) && lessThan(idxRightChild,idxChild))
idxChild = idxRightChild;
// idxCHild es el ndice del hijo con el menor de los valores
if(lessThan(idxChild,idx)) {
swap(idxChild,idx);
idx = idxChild; // move to child node for next iteration
} else
break;
}

heapifyDown() est en O(log size)
}
public void delMin() {
if(isEmpty())
throw new EmptyHeapException("delMin on empty heap");
else {
elems[ROOT_INDEX] = elems[size-1]; // move last child to root of tree
size--;
heapifyDown(); // move element down to enforce heap-order property
}
47
}

 Coste de las operaciones:

Operacin
BinaryHeap
isEmpty
minElem
insert
delMin

Coste
O(1)
O(1)
O(1)
O(log n)
O(log n)

O(n) si redimensionamos
el array

48

Llamamos peso de un nodo el nmero de elementos que cuelgan desde el nodo

Representaremos un monYculo va un rbol binario aumentado: en cada nodo

aparece (adems de su valor y los hijos) su peso:

data Heap a = Empty | Node a Int (Heap a) (Heap a)

weight :: Heap a -> Int
Peso del nodo
weight Empty
= 0
weight (Node _ w _ _) = w
rbol con raz 'a'
con 6 elementos

h1 :: Heap Char
h1 = Node 'a' 6 (Node 'd' 3 (Node 'e' 1 Empty Empty)
(Node 'f' 1 Empty Empty))
(Node 'b' 2 (Node 'c' 1 Empty Empty)
Empty)
rbol con raz b'
con 2 elementos

49

Un rbol es Weight Biased Le;ist si, para cualquier nodo en el

rbol, el peso de su hijo izquierdo es mayor o igual que el peso de
su hijo derecho
isWeightedLeftist :: Heap a -> Bool
isWeightedLeftist Empty
= True
isWeightedLeftist (Node _ _ lh rh) = weight lh >= weight rh
&& isWeightedLeftist lh
&& isWeightedLeftist rh

Un heap Weight Biased Le;ist (WBLH) es un rbol Weight Biased

Le;ist que sa7sface la propiedad de Heap-order
Es un
WBLH J

Es un
WBLH J

Es un
WBLH J

50

module DataStructures.Heap.WeightBiasedLeftistHeap
( Heap
, empty
-- :: Heap a
, isEmpty -- :: Heap a -> Bool
, minElem -- :: Heap a -> a
, delMin
-- :: (Ord a) => Heap a -> Heap a
, insert
-- :: (Ord a) => a -> Heap a -> Heap a
) where

data Heap a = Empty | Node a Int (Heap a) (Heap a) deriving Show

empty :: Heap a
empty = Empty

isEmpty :: Heap a -> Bool
isEmpty Empty = True
isEmpty _
= False

minElem :: Heap a -> a
minElem Empty
= error "minElem on empty heap"
minElem (Node x _ _ _) = x
El mnimo del montculo

es la raz del arbol

51

delMin :: (Ord a) => Heap a -> Heap a

delMin Empty
= error "delMin on empty heap"
delMin (Node _ _ lh rh) = merge lh rh

elimina la raz (el menor)

y mezcla los hijos

singleton :: a -> Heap a
singleton x = Node x 1 Empty Empty

insert :: (Ord a) => a -> Heap a -> Heap a
Crea un montculo de un elemento y
lo mezcla con el montculo
insert x h = merge (singleton x) h

merge :: (Ord a) => Heap a -> Heap a -> Heap a
...

En definitiva: las operaciones delicadas (insert, delMin) y su

complejidad dependen de la definicin de merge.

Definiremos merge para que su complejidad sea logartmica J
52

Sea llama espina derecha de un rbol binario al camino

desde la raz hasta el nodo terminal ms a la derecha
Espina derecha

rightSpine :: Heap a -> [a]

rightSpine Empty
= []
rightSpine (Node x _ _ rh) = x : rightSpine rh

Para cualquier WBLT con n elementos,

la longitud de su espina derecha es log2(n+1)
esto demostrar que la complejidad de merge es logartmica
53

-- longitud de la espina derecha

lrs :: Heap a -> Int
lrs Empty
= 0
lrs (Node x _ _ rh) = 1 + lrs rh

Teorema.- Para cualquier monYculo zurdo (WBLT) t con n

elementos, la longitud de la espina derecha sa7sface

lrs t log2(n+1)

Por induccin sobre t; hay que probar:

Caso base:

lrs Empty log2(0+1)

Paso induc7vo: siendo p = weight

si lrs lh
entonces

lh, q = weight rh

log2(p+1) && lrs rh log2(q+1)

lrs (Node x _ lh rh) log2(p+q+2) 54

 Caso base:

-- length of right spine

lrs :: Heap a -> Int
lrs Empty
= 0
lrs (Node x _ _ rh) = 1 + lrs rh

lrs Empty log2(0+1)

{- 1) ecuacin de lrs (parte izquierda)
0 log2(0+1)
{- aritmtica de log (parte derecha) -}
0 0

True

-}

55

Paso induc7vo:
Sean p = weight lh y q = weight rh
si lrs lh
entonces

-- longitud de la espina derecha

lrs :: Heap a -> Int
lrs Empty
= 0
lrs (Node x _ _ rh) = 1 + lrs rh
Hiptesis de
induccin

log2(p+1) && lrs rh log2(q+1)

lrs (Node x _ lh rh) log2(p+q+2)

lrs (Node x _ lh rh) log2(p+q+2)

{- 2) lrs al miembro izdo. de la desigualdad -}

1 + lrs rh log2(p+q+2)

{- Hiptesis de induccin, transitividad de -}

1 + log2(q+1) log2(p+q+2)
{- 1 = log2 2,
log x + log y = log (xy) -}
log2(2q+2) log2(p+q+2)
{- _ y log2 son montonas}
2q+2 p+q+2
{- p q

porque el montculo es zurdo -}

True
56

Dos monYculos zurdos construidos con 50 elementos aleatorios:

la espina derecha es muy corta!

57

 Pretendemos obtener un nuevo WBLH mezclando

dos WBLHs

merge

=>

Y pretendemos obtenerlo ecientemente:

Mezclndolos a travs de sus espinas derechas (O(log n))
58

Queremos mezclar dos listas ordenadas para obtener una lista ordenada:

merge [1,7,9] [0,2,4]

-- sacamos la menor de las cabezas y seguimos mezclando
0 : merge [1,7,9] [2,4]
merge :: (Ord a) => [a] -> [a] -> [a]

merge []
ys
= ys
0 : 1 : merge [7,9] [2,4]
merge xs
[]
= xs

merge ls@(x:xs) rs@(y:ys)
= x : merge xs rs
0 : 1 : 2 : merge [7,9] [4] | x <= y
| otherwise
= y : merge ls ys

0 : 1 : 2 : 4 : merge [7,9] []

0 : 1 : 2 : 4 : [7,9]

El algoritmo anterior puede generalizarse para montculos

59

Necesitamos una funcin auxiliar para construir un rbol zurdo a par7r de otros
dos y de un valor:
node :: a -> Heap a -> Heap a -> Heap a
node x h h'
El de ms peso a la
| w >= w'
= Node x s h h'
izquierda
| otherwise = Node x s h' h
where
Manteniendo el
w = weight h
invariante: los
w' = weight h'
El resultado es zurdo,
pero no necesariamente
s = w + w' + 1
argumentos son zurdos
ordenado, salvo que 0
no supere a las raices

node 0

=>

60

merge :: (Ord a) => Heap a -> Heap a -> Heap a

merge Empty h'
= h'
merge h
Empty = h
merge h@(Node x w lh rh) h'@(Node x' w' lh' rh')
| x <= x'
= node x lh (merge rh h')
| otherwise
= node x' lh' (merge h rh')

Conservando el
invariante: los
argumentos son
monYculos zurdos

extraemos el menor nodo junto a su hijo izquierdo,

y mezclamos el resto

Si los argumentos son monYculos zurdos, es posible

demostrar por induccin:
1. la mezcla es un monYculo zurdo J
2. el nmero de llamadas a merge es menor que la suma
de las longitudes de las espinas izquierdas de los
argumentos J

61

merge :: (Ord a) => Heap a -> Heap a -> Heap a

merge Empty h'
= h'
merge h
Empty = h
merge h@(Node x w lh rh) h'@(Node x' w' lh' rh')
| x <= x'
= node
x lh (merge rh h')

| otherwise
= node x' lh' (merge h rh')

Conservando el
invariante: los
argumentos son
monYculos zurdos

x
merge

x'

=>

62

merge :: (Ord a) => Heap a -> Heap a -> Heap a

merge Empty h'
= h'
merge h
Empty = h
merge h@(Node x w lh rh) h'@(Node x' w' lh' rh')
| x <= x'
= node
x lh (merge rh h')

| otherwise
= node x' lh' (merge h rh')

Conservando el
invariante: los
argumentos son
monYculos zurdos

La funcin node coloca lh

a la derecha de
x
merge

x'

rh

h'

lh

merge

=>

63

merge :: (Ord a) => Heap a -> Heap a -> Heap a

merge Empty h'
= h'
merge h
Empty = h
merge h@(Node x w lh rh) h'@(Node x' w' lh' rh')
| x <= x'
= node x lh (merge rh h')
| otherwise
= node
x' lh' (merge h rh')

x
merge

merge

=>

x'

Conservando el
invariante: los
argumentos son
monYculos zurdos

1
lh'

=>

rh'

merge

64

merge :: (Ord a) => Heap a -> Heap a -> Heap a

merge Empty h'
= h'
merge h
Empty = h
merge h@(Node x w lh rh) h'@(Node x' w' lh' rh')
| x <= x'
= node x lh (merge rh h')
| otherwise
= node
x' lh' (merge h rh')

Conservando el
invariante: los
argumentos son
monYculos zurdos

1
merge

merge

=>

=>

x'

merge

65

module DataStructures.PriorityQueue.WBLeftistPriorityQueue
( PQueue
, empty
-- :: PQueue a
, isEmpty
-- :: PQueue a -> Bool
, first
-- :: PQueue a -> a
, dequeue
-- :: (Ord a) => PQueue a -> PQueue a
, enqueue
-- :: (Ord a) => a -> PQueue a -> PQueue a
) where

import qualified DataStructures.Heap.WeightBiasedLeftistHeap as H

data PQueue a = PQ (H.Heap a)

empty :: PQueue a
empty = PQ H.empty

isEmpty :: PQueue a -> Bool
isEmpty (PQ h) = H.isEmpty h

enqueue :: (Ord a) => a -> PQueue a -> PQueue a
enqueue x (PQ h) = PQ (H.insert x h)

first :: PQueue a -> a
first (PQ h) = H.minElem h

dequeue :: (Ord a) => PQueue a -> PQueue a
dequeue (PQ h) = PQ (H.delMin h)

66

 Eciencia de las operaciones:

Operacin
empty
isEmpty
minElem
merge
insert
delMin

Coste
O(1)
O(1)
O(1)
O(log n)
O(log n)
O(log n)

El resultado es similar
al obtenido con
monYculos binarios
en Java va arrays

67

-- construccin en forma ascendente (bottom-up): O(n)

mkHeap :: (Ord a) => [a] -> Heap a
Construimos una lista de
mkHeap [] = empty
montculos simples
mkHeap xs = mergeLoop (map singleton xs)
where
Mezclamos dos a dos
mergeLoop [h] = h
hasta obtener un solo
elemento
mergeLoop hs = mergeLoop (mergePairs hs)

mergePairs []
= []
mezcla dos a dos
mergePairs [h]
= [h]
mergePairs (h:h':hs) = merge h h' : mergePairs hs

Sea T(n) el nmero de pasos de mkHeap para una lista con n elementos:
T(n) = n/2 O(log2 1) + n/4 O(log2 2) + n/8 O(log2 4) + + 1 O(log2 (n/2))
n/2 mezclas de
montculos de 1
elemento

n/4 mezclas de
montculos de 2
elementos

n/8 mezclas de
montculos de 4
elementos

1 mezcla de
montculos de
n/2 elementos

La solucin T(n) es O(n) J

68

mergeLoop (map singleton [8, 3, 1, 6, 2, 4, 5, 7]) =>

mergeLoop (mergePairs[

mergeLoop (mergePairs [

mergeLoop (mergePairs [

mergeLoop [

]) =>

]) =>

]) =>

] =>

69

heapSort :: (Ord a) => [a] -> [a]

heapSort est en
heapSort = heapToList . mkHeap
O(n log n)

n eliminaciones donde cada una
heapToList :: (Ord a) => Heap a -> [a] realiza O(log n) pasos + O(n)
heapToList h
para la operacin mkHeap
| isEmpty h = []
| otherwise = minElem h : heapToList (delMin h)

[1,3,4,6,7,8,9]

heapToList

mkHeap

[6,3,8,1,4,7,9]

70

package dataStructures.heap;

public class WeigthBiasedLeftistHeap<T extends Comparable<? super T>>

implements Heap<T>{
root

protected static class Tree<E> {
E elem;
// elemento raz del MZ
int weight;
// peso o nmero de elementos
Tree<E> left; // hijo izdo
a 5
Tree<E> right; // hijo dcho
}

// referencia a la raz del montculo
d 3
b 1
protected Tree<T> root;

public WeigthBiasedLeftistHeap() {
root = null;
}
e 1
f 1

public boolean isEmpty() {
return root == null;
significa null
}

private static<T> int weight(Tree<T> t) {
return t==null ? 0 : t.weight;
}

public int size() {
return isEmpty() ? 0 : root.weight;
}

71

private static <T> Tree<T> node(T x, Tree<T>

"int w = weight(h);!
"int wp = weight(hp);!
"Tree<T> tree = new Tree<T>();!
"tree.elem = x;!
"tree.weight = 1 + w + wp;!
"if (w >= wp) {!
"
"tree.left = h;!
"
"tree.right = hp;!
"} else {!
"
"tree.left = hp;!
"
"tree.right = h;!
"}!
"return tree;!
node :: a -> Heap a ->
}!
node x h h'
"!
| w >= w'
= Node x
| otherwise = Node x
where
w = weight h
w' = weight h'
s = w + w' + 1

h, Tree<T> hp) {!

Heap a -> Heap a

s h h'
s h' h

72

// Merges two heap trees along their right spines.!

// Returns merged heap.!
private static <T extends Comparable<? super T>> !
"
"
"
"
"Tree<T> merge(Tree<T> h, Tree<T> hp) {!
"if (h == null)!
"
"return hp;!
"if (hp == null)!
"
"return h;!
!

"T x = h.elem;!
"T xp = hp.elem;!
"if (x.compareTo(xp) <= 0) {
// x <= xp!
"
"return node(x, h.left, merge(h.right, hp));!
"} else {!
"
"return node(xp, hp.left, merge(h, hp.right));
"
"
"!
"}!
merge :: (Ord a) => Heap a -> Heap a -> Heap a
merge Empty h'
= h'
merge h
Empty = h
merge h@(Node x w lh rh) h'@(Node x' w' lh' rh')
| x <= x'
= node x lh (merge rh h')
| otherwise
= node x' lh' (merge h rh')

73

// mezcla dos MZs a lo largo de sus espinas derechas, devolviendo un MZ

private static <T extends Comparable<? super T>> Tree<T> merge(Tree<T> h1, Tree<T> h2) {
if (h1 == null)
return h2;
if (h2 == null)
return h1;

if (h2.elem.compareTo(h1.elem) < 0) {// forzamos que h1 sea el de clave menor

// intercambiamos h1 and h2
Tree<T> aux = h1;
h1 = h2;
h2 = aux;
} // la mezcla quedar referenciada por h1

h1.right = merge(h1.right, h2); // mezcla sobre la espina derecha
int wL = weight(h1.left);
int wR = weight(h1.right);
h1.weight = wL + wR + 1; // reajustamos el nuevo peso
// intercambiamos los hijos de h1 si fuera necesario para que h1 quede zurdo
if (wL < wR) {
Tree<T> aux = h1.left;
h1.left = h1.right;
h1.right = aux;
}

return h1;
}

74

public T minElem() {
if(isEmpty())
throw new EmptyHeapException("minElem on empty heap");
else
return root.elem;
El mnimo en la raz
}
public void delMin() {
if(isEmpty())
throw new EmptyHeapException("delMin on empty heap");
else
Mezclamos los hijos
sin la raz
root = merge(root.left,root.right);
}

public void insert(T x) {
Tree<T> tree = new Tree<T>();
tree.elem = x;
tree.weight = 1;
root = merge(root, tree);
}

Creamos un nuevo MZ
con un solo elemento

La insercin se produce
al mezclar la raz con el
nuevo MZ
75

Un BST (Binary Search Tree) es un rbol binario tal que para cada
nodo v,
todos los elementos del subrbol

izquierdo son menores que v, y

todos los elementos del subrbol
derecho son mayores que v

Invariante de un BST

data BST a = Empty | Node a (BST a) (BST a) deriving Show

isBST :: (Ord a) => BST a -> Bool
isBST Empty
= True
isBST (Node x lt rt) = forAll (<x) lt && forAll (>x) rt
&& isBST lt && isBST rt
where
forAll :: (a -> Bool) -> BST a -> Bool
forAll p Empty
= True
forAll p (Node x lt rt) = p x && forAll p lt && forAll p rt
76

Problema: insertar un nuevo elemento en un BST de

forma que el resultado sea otro BST (se conserve el
invariante)

insert 7

77

Problema: insertar un nuevo elemento en un BST de

forma que el resultado sea otro BST (se conserve el
invariante)
7

7 debe quedar a la
derecha de 4

78

Problema: insertar un nuevo elemento en un BST de

forma que el resultado sea otro BST (se conserve el
invariante)
7
7 a la izquierda de 8

79

Problema: insertar un nuevo elemento en un BST de

forma que el resultado sea otro BST (se conserve el
invariante)

7 a la derecha de 6

80

Problema: insertar un nuevo elemento en un BST de

forma que el resultado sea otro BST (se conserve el
invariante)

7 debe quedar
aqu

81

Problema: insertar un nuevo elemento en un BST de

forma que el resultado sea otro BST (se conserve el
invariante)

82

insert :: (Ord a) => a -> BST a -> BST a

insert x' Empty = Node x' Empty Empty
insert x' (Node x lt rt)
| x'==x
= Node x' lt rt
| x'<x
= Node x (insert x' lt) rt
| otherwise = Node x lt (insert x' rt)

Si x'==x, entonces
x es sustituido por x'

El nmero de pasos es proporcional a la altura del rbol:

Para un rbol con n claves, insert O(n), pero podra conseguirse, para
cierto 7po de rboles, insert O(log n)

Altura en O(log n) J

Altura en O(n) L

83

Dos BSTs generados con elementos aleatorios:

Los rboles quedan muy

desequilibrados L

84

La insercin de una coleccin ordenada produce BSTs

degenerados

85

 Recorriendo en orden un BST obtenemos la lista

ordenada de sus elementos (algoritmo tree sort)

mkBST :: (Ord a) => [a] -> BST a

mkBST xs = foldr insert empty xs
treeSort :: (Ord a) => [a] -> [a]
treeSort = inOrderB . mkBST

[1,3,4,6,7,8,9]

inOrderB

mkBST

[9,7,4,1,8,3,6]

86

search :: (Ord a) => a -> BST a -> Maybe a

search x' Empty = Nothing
search x' (Node x lt rt)
| x'==x
= Just x
| x'<x
= search x' lt
| otherwise
= search x' rt

isElem :: (Ord a) => a -> BST a -> Bool
isElem x t = isJust (search x t)

Maybe

search 4

search 10

data Maybe a = Nothing | Just a

isJust :: Maybe a -> Bool
isJust (Just _) = True
isJust Nothing
= False

87

El mnimo elemento se encuentra en la posicin ms a la

izquierda (al nal de la espina izquierda):
minim
minim
minim
minim

:: BST a -> a
Empty
(Node x Empty rt)
(Node x lt rt)

= error "minim on empty tree"

= x
= minim lt

Mnimo
elemento

88

El mximo elemento se encuentra al nal de la espina

derecha:
maxim
maxim
maxim
maxim

:: BST a -> a
Empty
(Node x lt Empty)
(Node x lt rt)

= error "maxim on empty tree"

= x
= maxim rt

Mximo
elemento

89

En la primera fase localizamos el elemento siguiendo un algoritmo

parecido al de insercin.
(a) Si el nodo a eliminar es una hoja, se elimina sin ms
Man7ene invariante el orden

=>

delete 'c'

hoja

90

En la primera fase localizamos el elemento siguiendo un algoritmo

parecido al de insercin.
(b) Si el nodo a eliminar 7ene un solo hijo, el nodo padre puede
conectarse con el nodo hijo.
Man7ene invariante el orden

Solo 1 hijo

delete b'

=>

91

En la primera fase localizamos el elemento siguiendo un algoritmo

parecido al de insercin.
(c) Si el nodo a borrar 7ene dos hijos:
El mnimo elemento del hijo derecho sus7tuir al elemento a borrar. El rbol

resultante sigue siendo un BST

Man7ene Invariante el orden

2 hijos

=>

delete d'

Hijo derecho
Mnimo del
hijo derecho
92

En la primer fase localizamos el elemento siguiendo un algoritmo

parecido al de insercin.
(c) Si el nodo a borrar 7ene dos hijos:
Alterna7vamente: El mximo elemento del hijo izquierdo sus7tuir al

elemento a borrar. El rbol resultante sigue siendo un BST

Man7ene invariante el orden

2 hijos

=>

delete d'

Hijo izquierdo

Mximo del
hijo izquierdo

93

Quitar y devolver el mnimo elemento de un rbol:

split :: BST a -> (a,BST a)
split (Node x Empty rt) = (x,rt)
split (Node x lt
rt) = (m,Node x lt' rt)
where (m,lt') = split lt

split

=>

94

delete :: (Ord a) => a -> BST a -> BST a

delete x' Empty = Empty
delete x' (Node x lt rt)
| x'==x
= join lt rt
| x'<x
= Node x (delete x' lt) rt
| otherwise
= Node x lt (delete x' rt)


join :: BST a -> BST a -> BST a
join Empty rt
= rt
Uno de los hijos es vaco
join lt
Empty = lt
join lt
rt
= Node m lt rt'
where (m,rt') = split rt

rbol derecho sin

Mnimo
elemento del
rbol derecho

el elemento
mnimo

Todas las claves de lt son

menores que las de rt,
luego x es mayor que las
claves de lt

95

Operacin
empty
isEmpty
insert
isElem
delete
minim
maxim

Coste
O(1)
O(1)
O(n)
O(n)
O(n)
O(n)
O(n)

(*) Podemos obtener complejidades en O(log n) si imponemos a

los BST condiciones de balanceo; por ejemplo, AVL
96

Ser interesante disponer de una interfaz para dis7ntas versiones de los BST (los puros y los
equilibrados AVL)

package dataStructures.binarySearchTree;

import dataStructures.tuple.Tuple2;

public interface SearchTree<K extends Comparable<? super K>, V> {

public boolean isEmpty();
public int size();
Implementaremos una variante en la
public int height();
que cada nodo del rbol guarda, adems
public void insert(K k, V v);
de las referencias a los hijos, otros dos
public V search(K k);
datos: una clave y un valor.
public boolean isElem(K k);

public void delete(K k);
Los nodos en el rbol estarn ordenados
public Iterable<K> inOrder();
public Iterable<K> postOrder();
segn sus claves.
public Iterable<K> preOrder();
public Iterable<V> values();
public Iterable<Tuple2<K,V>> keysValues();

97

package dataStructures.binarySearchTree;

public class BST<K extends Comparable<? super K>, V> implements SearchTree<K,V> {

private static class Tree<K,V> {
private K key;
private D value;
private Tree<K,V> left, right;

public Tree(C k, V v) {
key = k;
value = v;
left = null;
right = null;
}
}

private Tree<K,V> root;
private int size;

public BST() {
root = null;
size = 0;
}

public boolean isEmpty() {
return root == null;
}

public int size () {
return size;
}

98

public V search(K key) {

return BST.searchRec(root, key);
}

Devuelve el valor del rbol

asociado a la clave key, o null
si la clave no est en el rbol

private static <K extends Comparable<? super K>, V>

V searchRec(Tree<K,V> tree, K key) {
if (tree == null)
return null;
else if (key.compareTo(tree.key) == 0)
Recordemos que los
return tree.value;
rboles estn ordenados
else if (key.compareTo(tree.key) < 0)
segn clave
return searchRec(tree.left, key);
else
return searchRec(tree.right, key);
}
public boolean isElem(K key) {
return search(key) != null;
}

Devuelve true si el rbol

contiene la clave key
99

public void insert(K key, V value) {

root = insertRec(root, key, value);
}

Inserta un nodo con clave key

y valor value en el rbol. Si
el nodo con key ya exista se
reemplaza el valor con el
nuevo

// returns modified tree

private Tree<K,V> insertRec(Tree<K,V> node, K key, V value) {
if (node == null) {
node = new Tree<K,V>(key,value); // new node
size++;
}
else if (key.compareTo(node.key) == 0)
node.value = value; // key was already present
else if (key.compareTo(node.key) < 0)
node.left = insertRec(node.left, key, value);
else
node.right = insertRec(node.right, key, value);
return node;
}
100

// precondicin: node no es un rbol vaco

// Elimina la clave mnima y su valor asociado del rbol primer
// argumento, dejando la clave mnima y su valor en el segundo
//argumento

private static <K, V> Tree<K,V>

split(Tree<K,V> node, Tree<K,V> temp) {
if (node.left == null) {
// min encontrado: copia clave y valor al 2 arg. temp

temp.key = node.key;
temp.value = node.value;
return node.right; // devuelve el hijo derecho
} else {
// elimina el mnimo de la subrama izquierda

node.left = split(node.left, temp);

return node;

101

public void delete(K key) {

root = deleteRec(root, key);
}

Borra el nodo con

clave key

// Devuelve el rbol modificado

private Tree<K,V> deleteRec(Tree<K,V> node, K key) {
if (node == null)
; // key no encontrada; no hacemos nada
2 hijos
else if (key.compareTo(node.key) == 0) {
if (node.left == null)
node = node.right;
else if (node.right == null)
node = node.left;
else // tiene dos hijos
Hijo
node.right = split(node.right, node);
derecho
Mnimo del hijo
size--;
derecho
} else if (key.compareTo(node.key) < 0)
node.left = deleteRec(node.left, key);
else
Quitamos el mnimo de
node.right = deleteRec(node.right, key);
node.right, pero
return node;
copiando antes su
}
contenido en node

102

public interface SearchTree<K extends Comparable<? super K>, V> {

public boolean isEmpty();
public int size();
public int height();
public void insert(K k, V v);
...
public Iterable<K> preOrder();
public Iterable<K> postOrder();
public Iterable<K> inOrder();
public Iterable<V> values(); //itera valores inOrder
public Iterable<Tuple2<K,V>> keysValues(); // //itera pares inOr.

Recordemos
las interfaces:
interface Iterable<T> {
public
Iterator<T> iterator();
}

public interface Iterator<T> {
boolean hasNext();
T next();
void remove();
}
}
Consideraremos cinco mtodos para generar un objeto del 7po
Iterable<*> para recorrer (iterar) un BST, manipulando claves,
valores, o ambos, u7lizando los recorridos estndar:

- Por claves
Preorden:
PostOrden:
InOrden:

Iterable<K> preOrder();
Iterable<K> postOrder();
Iterable<K> inOrder();

- Por valores:

Iterable<V> values();
- Por pares (clave, valor): Iterable<Tuple2<K,V>> keysValues();

103

BST<Integer,String> bst = new BST<Integer,String>();

bst.insert(5, "five");
bst.insert(2, "two");
de tipo
bst.insert(7, "seven");
Iterable<Integer>
bst.insert(1, "one");
bst.insert(3, "three");

Ambos Imprimen:
1
System.out.println("InOrder traversal:");
for(int i : bst.inOrder()) {
2
3
System.out.printf("%d ",i);
}
5
System.out.println();
7

System.out.println("InOrder traversal:");
Iterator<Integer> it = bst.inOrder().iterator();
Devuelve un iterador que
while(it.hasNext())
recorre las claves del rbol
System.out.printf("%d ",it.next());
en orden
System.out.println();

System.out.println(KeysValues inOrder traversal:");
for(Tuple<Integer.String> par : bst.keysValues()) {
1 one
System.out.printf("%d %s", par._1(), par._2() );
2 two

3 three
}
5 five
System.out.println();
7 seven



104

Usa un stack para organizar los nodos pendientes

root

Para recorrer los

void save(Tree<K,V> node) {

elementos, se guardan en
// en orden inverso, el stack es LIFO
un stack
if (node.right != null)
Visitaremo la subrama
push red right subtree in stack
derecha en tercer lugar
push blue node in stack

Visitaremos la clave y valor
if (node.left != null)
en segundo lugar
push red left subtree in stack
}
Visitaremos la subrama
izquierda en primer lugar

Visitaremos la subrama
izquierda en primer lugar
(red)

Visitaremos el nodo en
segundo lugar (blue)

stack

Visitaremos la subrama
derecha en tercer lugar
(red)

El stack se usar organizar el orden de los elementos a

visitar.

El stack debe guardar dos 7pos de rboles
- rboles para visitar (red tree)
- rboles de los que solo interesa la clave y el valor
del nodo raz (blue tree)
105

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}
nextTree() es un mtodo
de la clase Traversal

que encapsula el stack; las

sucesivas llamadas cambian
el stack y generan una
secuencia de referencias a
nodos

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

106

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push right subtree in stack
push key in stack

if (node.left != null)
push left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

107

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

108

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push right subtree in stack
push key in stack

if (node.left != null)
push left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

109

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

110

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

111

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

112

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

113

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

114

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

115

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

116

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

117

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue nodein stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

118

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

119

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

120

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

121

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

122

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

123

void save(Tree<K,V> node) {

// en orden inverso, el stack es LIFO
if (node.right != null)
push red right subtree in stack
push blue node in stack

if (node.left != null)
push red left subtree in stack
}

public Tree<K,V> nextTree() {

t = stack.top();
stack.pop();

t
nextTree =>
}
stack

while (t is a red tree) {

save(t);
t = stack.top();
stack.pop();
}
return t; //blue tree

124

El stack debe ser capaz de diferenciar los rboles almacenados

(red o blue)
El 7po base del stack ser Either< Tree<K,V>, Tree<K,V> >
Un objeto del 7po Either<A,B> pueden guardar:

o un valor de 7po A (izquierda), o un valor de 7po B (derecha)

Los rboles blue son los de la izquierda y red los de la derecha

EJEMPLO

Either<Integer,String> either = new Left(5);

true si either
guarda un Integer

if(either.isLeft())
Integer n = either.left();

Either guarda el Integer

5

Devuelve el Integer de
either

either = new Right("five");

Either guarda el String

"five"

true si either
guarda un String

if(either.isRight())
String s = either.right();

Devuelve el String de
either

125

package dataStructures.either;
public interface Either<A,B> {
boolean isLeft();
boolean isRight();
A left();
B right();
}

public class Left<A,B> implements Either<A,B> {
private A left;

public Left(A x) { left = x; }

public boolean isLeft() { return true; }
public boolean isRight() { return false; }
public A left() { return left; }
public B right() { throw new NoSuchElementException("right on Left object"); }

public String toString() { return "Left("+left+")"; }
}

public class Right<A,B> implements Either<A,B> {
private B right;

public Right(B x) { right = x; } ...
126
}

private abstract class Traversal {

Stack<Either<Tree<K,V>, Tree<K,V>>> stack = new LinkedStack<Either<Tree<K,V>, Tree<K,V>>>();

abstract void save(Tree<K,V> node);

public Traversal() {
if (root != null)
save(root);
}

public boolean hasNext() {

return !stack.isEmpty();
}

No hay ms
elementos ya que el
stack est vacio

Stack puede guardar o

bien un rbol del que

nos interesan valor y raz
(valor a la izquierda) o
bien un rbol para visitar
(valor a la derecha)

public Tree<K,V> nextTree() {

if (!hasNext())
throw new NoSuchElementException();
Either<Tree<K,V>, Tree<K,V>> either = stack.top();
stack.pop();

Mientras sea un rbol de la derecha

hay que visitarlo

Inicializa el stack

Ser definido para cada

recorrido: inOrder,
preOrder y postOrder

while (either.isRight()) {
Tree<K,V> node = either.right();
save(node);
either = stack.top();
stack.pop();
Es un rbol de la izquierda. Nos
}
interesa solo la clave y el valor
return either.left();

public void remove() {

throw new UnsupportedOperationException();
}

127

public class InOrderTravesal extends Travesal {

Visitamos el

void
save(Tree<K,V>
node)
{
subrbol derecho en

// in reverse order, cause stack is LIFO

tercer lugar (right)
if (node.right != null)


stack.push(new Right<Tree<K,V>, Tree<K,V>>(node.right)); Visitamos rbol con
stack.push(new Left<Tree<K,V>, Tree<K,V>>(node));

if (node.left != null)
stack.push(new Right<Tree<K,V>, Tree<K,V>>(node.left));

clave y valor en
segundo lugar (left)

Visitamos el subrbol
izquierdo en primer
lugar (right)

private class InOrderIt extends InOrderTraversal implements Iterator<K> {

"public K next() {
"
"return super.nextTree().key;
Solo se necesita la
"}
clave del nodo raz
}
public class BST<K extends Comparable<? super K>, V>




implements SearchTree<K,V> {
"public Iterable<K> inOrder() {

return new Iterable<K>() {
"
"
"public Iterator<K> iterator() {



return new InOrderIt();


}
"
"};
}...
}

128

public class PreOrderTraversal extends Traversal {

Visitamos el

void
save(Tree<K,V>
node)
{

subrbol derecho en
// in reverse order, cause stack is LIFO

tercer lugar (right)
if (node.right != null)


stack.push(new Right<Tree<K,V>, Tree<K,V>>(node.right));
Visitamos el subrbol
if (node.left != null)
stack.push(new Right<Tree<K,V>, Tree<K,V>>(node.left)); izquierdo en segundo
lugar (right)
stack.push(new Left<Tree<K,V>, Tree<K,V>>(node));
Visitamos rbol con clave y
}
valor en primer lugar (left)
}
private class PreOrderIt extends PreOrderTraversal implements Iterator<K> {
"public K next() {
"
"return super.nextTree().key;
Solo se necesita la
"}
clave del nodo raz
}
public class BST<K extends Comparable<? super K>, V>




implements SearchTree<K,V> {
"public Iterable<K> PreOrder() {

return new Iterable<K>() {
"
"
"public Iterator<K> iterator() {



return new PreOrderIt();


}
"
"};
}...
}

129

public class PostOrderTravesal extends Travesal {

void save(Tree<K,V> node) {
// in reverse order, cause stack is LIFO

stack.push(new Left<Tree<K,V>, Tree<K,V>>(node));

Visitamos el
subrbol derecho en
if (node.right != null)
stack.push(new Right<Tree<K,V>, Tree<K,V>>(node.right)); segundo lugar (right)

Visitamos rbol con

clave y valor en tercer
lugar (left)

if (node.left != null)
stack.push(new Right<Tree<K,V>, Tree<K,V>>(node.left));

Visitamos el subrbol
izquierdo en primer
lugar (right)

private class PostOrderIt extends PostOrderTraversal implements Iterator<K> {

"public K next() {
"
"return super.nextTree().key;
Solo se necesita la
"}
clave del nodo raz
}
public class BST<K extends Comparable<? super K>, V>




implements SearchTree<K,V> {
"public Iterable<K> postOrder() {

return new Iterable<K>() {
"
"
"public Iterator<K> iterator() {



return new PostOrderIt();


}
"
"};
}...
}

130

Solo denimos la iteracin por valores para el recorrido InOrder

private class ValuesIt extends InOrderTraversal implements Iterator<V> {

"public V next() {
"
"return super.nextTree().value;
Solo se necesita el
"}
valor del nodo raz
}
public class BST<K extends Comparable<? super K>, V>




implements SearchTree<K,V> {
"public Iterable<V> values() {

return new Iterable<V>() {
"
"
"public Iterator<V> iterator() {



return new ValuesIt();


}
"
"};
}...
}

131

Solo denimos la iteracin por pares para el recorrido InOrder

private class KeyValuesIt extends InOrderTraversal !

!
!
!
!
!implements Iterator<Tuple2<K,V>> {
"public Tuple2<K,V> next() {
"
"Tree<K,V> node = super.nextTree();
"
"return new Tuple2<K,V>(node.key, node.value);
"}
Se necesita clave y valor del nodo raz.
}
Se devuelve una Tuple2 con los dos datos
public class BST<K extends Comparable<? super K>, V>




implements SearchTree<K,V> {
"public Iterable<Tuple2<K,V>> keysValues() {

return new Iterable<Tuple2<K,V>>() {
"
"
"public Iterator<Tuple2<K,V>> iterator() {



return new KeyValuesIt();


}
"
"};
}...
}

132

Si las operaciones de insercin y eliminacin en un BST

man7enen la altura pequea, el rbol se dice
balanceado en altura; tales operaciones pueden llegar a
tener una complejidad p7ma O(log n); sin balanceo
pueden elevarse hasta O(n)
h|p://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Existen varias aproximaciones a los rboles balanceados:

rboles AVL
rboles 2-3 y 2-3-4
rboles Rojo-negro (Red-Black)
133

h|p://en.wikipedia.org/wiki/
AVL_tree

Llamados as por el nombre de sus creadores,

Adelson-Velskii y Landis:

"An algorithm for the organiza7on of informa7on (1962)

Los rboles AVL son rboles binarios de bsqueda que sa7sfacen

la propiedad de balanceado-en-altura (height-balance) :
en cada nodo, las alturas de sus hijos dieren a lo sumo en 1

Todos estos son rboles AVL

134

data AVL a = Empty | Node a Int (AVL a) (AVL a)

4

En cada nodo

mantenemos su altura
Altura

2
3

height :: AVL a -> Int
height Empty
= 0
1
1
2
2
height (Node k h lt rt) = h

0 0 0 0

1
1 0
1

isAVL :: (Ord a) => AVL a -> Bool
0 0 0 0
0 0
isAVL Empty
= True
isAVL (Node k h lt rt) = forAll (<k) lt && forAll (>k) rt
&& abs (height lt - height rt) <= 1
&& isAVL lt && isAVL rt
where
forAll :: (a -> Bool) -> AVL a -> Bool
forAll p Empty
= True
forAll p (Node x h lt rt) =


p x && forAll p lt && forAll p rt

135

 Dos rboles AVL con 50 elementos aleatorios:

136

La altura h de un rbol AVL con n elementos es O(log n)

h log (n+1)
Sea N(h) el mnimo nmero de
nodos de un AVL de altura h:

N(1) = 1
rboles AVL trees con alturas 1,2 y 3
N(2) = 2
N(h) = 1 + N(h - 1) + N(h - 2) , h > 2
Nodo de la raz
de un rbol de
atura h

La altura de un
hijo debe ser
h -1

La diferencia de las alturas de los

hijos debe ser 1, y el mnimo de
nodos corresponde a h-2

Probaremos: h 1 N(h), luego h log (n+1)

= 1+5/2
137

 El nmero de oro

ecuacin

es la raz posi7va de la

x2 = 1 + x, es decir

1+ 5
=
= 1.618033988749895 ...
2

Por tanto, 2 = 1 + , y de aqu:

n+2 = n + n+1

138

 Usando h = h-1 + h-2, es fcil demostrar (por

induccin sobre h) que la funcin N(h) denida por la

recurrencia:

N(0) = 0,

N(1) = 1,

N(h) = 1 + N(h - 1) + N(h - 2) , h > 1
sa7sface
h 1 N(h) h+1 1
Pero si n es nmero de nodos de un rbol AVL de
altura h, entonces N(h) n, de donde


h 1 n
y de aqu: h log (n+1)
Recordemos que para todo rbol: log2 (n+1) h
139

 El nmero de oro (de Fidias?) y los nmeros de

Fibonacci aparecen de mltiples formas

- en la arquitectura y el arte

el Partenn de Fidias, la Gioconda de Leonardo da Vinci,

- en el reino vegetal, animal, astronoma

girasol, concha del Nautilus,
la forma de algunas galaxias

- en todas las ciencias, y en computacin !

geometra, grafos, recurrencias,

Relacin con los nmeros de Fibonacci:

fn =

1
(n ()n )
5

= lim

f n +1
fn

n = f n + f n 1
140

Origen del nmero ureo o divina proporcin

Segn Euclides en sus Elementos (Libro VI), es la
proporcin entre media y extrema razn: el todo es a
la parte como la parte al resto. Es decir,


a + b = a o tambin x = 1
a
b
1
x 1



Construccin de un
Rectngulo ureo



Fernando Corbaln, La proporcin urea, RBA (2010)
Entrevista a Fernando Corbaln (You Tube)
141

 Una rotacin es una operacin que cambia

ligeramente la estructura de un rbol binario de

bsqueda sin violar el invariante del orden

Una rotacin mueve un nodo hacia arriba y otro

hacia abajo. Un subrbol es desconectado del

nodo subido y enganchado al nodo bajado

Las rotaciones se usan para rebalancear la altura

de los rboles binarios de bsqueda

142

Construye un nuevo nodo a par7r de dos rboles AVL y

un valor, memorizando la altura del nuevo nodo
node :: a -> AVL a -> AVL a -> AVL a
node k lt rt = Node k h lt rt
where h = 1 + max (height lt) (height rt)

node 4

=>

143

rotR :: AVL a -> AVL a

rotR (Node k h (Node lk lh llt lrt) rt) = node lk llt (node k lrt rt)

lk

llt

lk

lrt

rt

llt

lrt

rt

144

rotR :: AVL a -> AVL a

rotR (Node k h (Node lk lh llt lrt) rt) = node lk llt (node k lrt rt)

Man7ene invariante el orden

7

lk

lk

rt

mayores
que 7
llt
menores
que 3

lrt
mayores
que 3 y
menores que 7

llt

menores
que 3
lrt
mayores
que 3 y
menores que 7

rt
mayores
que 7

145

rotL :: AVL a -> AVL a

rotL (Node k h lt (Node rk rh rlt rrt)) = node rk (node k lt rlt) rrt

lt

rlt

rk

rrt

lt

rk

rrt

lrt

146

rotL :: AVL a -> AVL a

rotL (Node k h lt (Node rk rh rlt rrt)) = node rk (node k lt rlt) rrt

Man7ene invariante el orden

k

lt

rk

menores
que 3
rlt
mayores
que 3 y
menores que 7

rk

rrt

mayores
que 7
rrt
mayores
que 7

lt
menores
que 3

rlt
mayores
que 3 y
menores que 7

147

 La insercin en un AVL 7ene dos fases:

- insercin como en un BST
- rebalanceo de los nodos modicados:

insert 0
No necesita
rebalanceo

148

 La insercin en un AVL 7ene dos fases:

- insercin como en un BST
- rebalanceo de los nodos modicados:
No necesita
rebalanceo

insert 0
2

149

 La insercin en un AVL 7ene dos fases:

- insercin como en un BST
- rebalanceo de los nodos modicados:
3

insert 0

Necesita rotacin
simple rotR ya que
la altura del hijo es
dos unidades mayor
que la del hijo
derecho

150

 La insercin en un AVL 7ene dos fases:

- insercin como en un BST
- rebalanceo de los nodos modicados:
Este es un rbol AVL

insert 0

rotR

151

Una rotacin simple a la derecha

no produce el balanceo

insert 7
No necesita
rebalanceo

152

insert
7
No necesita
rebalanceo

153

Necesita doble
rotacin
Inclinado a la
derecha

insert 7

154

insert 7

rotL
hijo izquierdo

155

rotL
hijo izquierdo

insert 7

Este es un rbol AVL

156

Igual que la insercin en un rbol Binario de Bsqueda

pero restaurando el balanceo en todos los nodos
modicados:

insert :: (Ord a) => a -> AVL a -> AVL a

insert k' Empty = node k' Empty Empty
insert k' (Node k h lt rt)
| k == k
= Node k' h lt rt
| k < k
= balance k (insert k' lt) rt
| otherwise
= balance k lt (insert k' rt)
Solo deben ser rebalanceados los nodos
modicados en el camino desde la raz
hasta el punto de insercin
157

Este es un rbol AVL

h+1
h+2
insert
h
h+1

Tras la insercin la
rama izquierda se
descompensa

Ahora no es
un rbol AVL
L

h+2

Puede volver a
balancearse con una
simple rotacin

h
h+1
h+2
158

Este es un rbol AVL

h+1
h+2
insert
h
h+1

Tras la insercin, la
rama izquierda se
descompensa

Ahora no es
un rbol AVL
L

h+2

Puede rebalancearse
con una doble
rotacin

h
h+1
h+2
159

Este es un rbol AVL

h+1
h+2
insert
h
h+1

Ahora no es
un rbol AVL
L

Tras la insercin, la
rama derecha se
descompensa

h+2

Puede rebalancearse
con una simple
rotacin

h
h+1
h+2

160

Este es un rbol AVL

h+1
h+2
insert
h
h+1

Ahora no es
un rbol AVL
L

Tras la insercin, la
rama derecha se
descompensa

h+2

Puede rebalancearse
con una doble
rotacin

h
h+1
h+2

161

rightLeaning :: AVL a -> Bool

rightLeaning (Node x h lt rt) = height lt < height rt

leftLeaning :: AVL a -> Bool

leftLeaning (Node x h lt rt) = height lt > height rt

162

balance :: a -> AVL a -> AVL a -> AVL a

balance k lt rt
| (lh-rh > 1) && leftLeaning lt = rotR
| (lh-rh > 1)
= rotR
| (rh-lh > 1) && rightLeaning rt = rotL
| (rh-lh > 1)
= rotL
| otherwise
= node
where lh = height lt
rh = height rt

(node k
(node k
(node k
(node k
k lt rt

lt rt)
(rotL lt) rt)
lt rt)
lt (rotR rt))

k
lt

rt

rotR (node k lt rt)

Rotacin a la
derecha

h+1

h+1

h+2

h+2

163

balance :: a -> AVL a -> AVL a -> AVL a

balance k lt rt
| (lh-rh > 1) && leftLeaning lt = rotR
| (lh-rh > 1)
= rotR
| (rh-lh > 1) && rightLeaning rt = rotL
| (rh-lh > 1)
= rotL
| otherwise
= node
where lh = height lt
rh = height rt

(node k
(node k
(node k
(node k
k lt rt

lt rt)
(rotL lt) rt)
lt rt)
lt (rotR rt))

k
lt

rt

rotL (node k lt rt)

Rotacin a la
izquierda

h+1

h+1

h+2

h+2

164

k
lt

balance :: a -> AVL a -> AVL a -> AVL a

balance k lt rt
| (lh-rh > 1) && leftLeaning lt = rotR
| (lh-rh > 1)
= rotR
| (rh-lh > 1) && rightLeaning rt = rotL
| (rh-lh > 1)
= rotL
| otherwise
= node
where lh = height lt
rh = height rt

(node k
(node k
(node k
(node k
k lt rt

lt rt)
(rotL lt) rt)
lt rt)
lt (rotR rt))

rt
rotR (node k (rotL lt) rt)

h
h

h+1

h+1

h+2

h+2

Solo una de estas

ramas tiene h+2

Rotacin a la izquierda en
el subrbol izquierdo (lt)

h
h+1
h+2

Rotacin a la
derecha en la raz

165

balance :: a -> AVL a -> AVL a -> AVL a

balance k lt rt
| (lh-rh > 1) && leftLeaning lt = rotR
| (lh-rh > 1)
= rotR
| (rh-lh > 1) && rightLeaning rt = rotL
| (rh-lh > 1)
= rotL
| otherwise
= node
where lh = height lt
rh = height rt

lt rt)
(rotL lt) rt)
lt rt)
lt (rotR rt))

rt

lt

(node k
(node k
(node k
(node k
k lt rt

rotL (node k lt (rotR rt))

h
h

h+1

h+1

h+2

h+2

Solo una de estas

ramas tiene h+2

h
Rotacin a la derecha en el
subrbol derecho (rt)

h+1
h+2

Rotacin a la
izquierda en la raz

166

search 4

Igual que en rboles Binarios de Bsqueda:

search 10

isElem :: (Ord a) => a -> AVL a -> Bool

isElem k t = isJust (search k t)

Maybe

search :: (Ord a) => a -> AVL a -> Maybe a

search k' Empty = Nothing
search k' (Node k h lt rt)
| k'==k
= Just k
| k'<k
= search k' lt
| otherwise
= search k' rt

data Maybe a = Nothing | Just a

isJust :: Maybe a -> Bool
isJust (Just _) = True
isJust Nothing
= False

167

Igual que en un rbol Binario de Bsqueda, pero

restaurando el balanceo en los nodos modicados:
delete :: (Ord a) => a -> AVL a -> AVL a
delete k' Empty = Empty
delete k' (Node k h lt rt)
| k'==k
= join lt rt
| k'<k
= balance k (delete k' lt) rt
| otherwise
= balance k lt (delete k' rt)
join :: AVL a -> AVL a -> AVL a
join Empty rt
= rt
join lt
Empty = lt
join lt
rt
= balance k' lt rt'
where (k',rt') = split rt
-- Elimina y devuelve el mnimo elemento de un rbol
split :: AVL a -> (a,AVL a)
split (Node k h Empty rt) = (k,rt)
split (Node k h lt
rt) = (k',balance k lt' rt)
where (k',lt') = split lt
168

Operacin
empty
isEmpty
insert
isElem
delete
minim
maxim

Coste
O(1)
O(1)
O(log n)
O(log n)
O(log n)
O(log n)
O(log n)

(*) Comprense con los costes para un BST estndar

169

package dataStructures.SearchTree;

public class AVL<K extends Comparable<? super K>, V> implements SearchTree<K,V>{

private static class Tree<C,D> {

private C key;
private D value;
private int height;
private Tree<C,D> left, right;

public Tree(C k, D v) {
key = k;
value = v;
height = 1;
left = null;
right = null;
}
}

Implementaremos una variante en la

que en cada nodo almacenamos: una
clave y un valor.

Los nodos en el rbol estarn ordenados
segn las claves.

private Tree<K,V> root;

public AVL() {
root = null;
}

public boolean isEmpty() {

return root == null;
}

170

public static int height(Tree<?,?> tree) {
return tree == null ? 0 : tree.height;
}

public boolean rightLeaning() {
return height(left) < height(right);
}
public boolean leftLeaning() {
return height(left) > height(right);
}
void setHeight() {
height = 1 + Math.max(height(left), height(right));
}

171

// rota a la derecha el receptor. Devuelve la nueva raz

public Tree<K,V> rotR() {

Tree<K,V> lt = this.left;
Tree<K,V> lrt = lt.right;

this.left = lrt;
this.setHeight();

lt.right = this;
lt.setHeight();

7 this
return lt;
}
lt

lrt

lt

lrt

this

9
172

// Rota a la izquierda el receptor. Devuelve la nueva raz

public Tree<K,V> rotL() {
Tree<K,V> rt = this.right;
Tree<K,V> rlt = rt.left;

this.right = rlt;
this.setHeight();

rt.left = this;
rt.setHeight();

return rt;
this 3
7 rt
}
0

rlt

rt

this

lrt
173

// Balancea el receptor. Devuelve el nodo despues de balancearlo

public Tree<K,V> balance() {
int lh = height(left);
int rh = height(right);

Tree<K,V> balanced;

if (lh - rh > 1 && left.leftLeaning()) {

balanced = this.rotR(); //Se necesita simple rotacin
} else if (lh - rh > 1) {
left = left.rotL();
//Se necesita doble rotacin
balanced = this.rotR();
} else if (rh - lh > 1 && right.rightLeaning()) {
balanced = this.rotL(); //Se necesita simple rotacin
} else if (rh - lh > 1) {
right = right.rotR();
//Se necesita doble rotacin
balanced = this.rotL();
} else {
balanced = this;
//No se necesita rotacin
balanced.setHeight();
}
return balanced;

}

174

Igual que en un rbol Binario de Bsqueda:

public V search(K key) {

return AVL.searchRec(root, key);
}
private static <C extends Comparable<? super C>, D>



D searchRec(Tree<C,D> tree, C key) {
if (tree == null)
return null;
else if (key.compareTo(tree.key) == 0)
return tree.value;
else if (key.compareTo(tree.key) < 0)
return searchRec(tree.left, key);
else
return searchRec(tree.right, key);
}
public boolean isElem(K key) {
return search(key) != null;
}

175

Igual que la insercin en un rbol Binario de Bsqueda pero restaurando

el balanceo en todos los nodos modicados:

public void insert(K k, V v) {

root = AVL.insertRec(root, k, v);
}
// returns modified tree
private static <C extends Comparable<? super C>, D>

Tree<C,D> insertRec(Tree<C,D> node, C key, D value) {
if (node == null)
node = new Tree<C,D>(key, value);
else if (key.compareTo(node.key) == 0)
node.value = value;
else if (key.compareTo(node.key) < 0) {
node.left = insertRec(node.left, key, value);
node = node.balance();
} else {
node.right = insertRec(node.right, key, value);
node = node.balance();
}
return node;
}
176

Un diccionario permite manejar echas (asociaciones) entre un conjunto de

claves a y un conjunto de valores b:

data Dict a b

-- un diccionario vaco
empty :: Dict a b

isEmpty :: Dict a b -> Bool

-- inserta/aade una asociacin en un diccionario
insert :: (Eq a) => a -> b -> Dict a b -> Dict a b

-- recupera el valor en el diccionario
valueOf :: (Eq a) => a -> Dict a b -> Maybe b

177

True ==> isEmpty empty

True ==> not (isEmpty (insert k v d))


True ==> valueOf k empty == Nothing

k==k' ==> valueOf k (insert k' v' d) == Just v'

k/=k' ==> valueOf k (insert k' v' d) == valueOf k d


True ==> insert k v' (insert k v d) = insert k v' d

k/=k' ==> insert k' v' (insert k v d)
== insert k v (insert k' v' d)

178

Un diccionario puede ser implementado ecientemente

usando un rbol AVL con claves y valores en los nodos

Los nodos deberan ordenarse segn la clave

Valor

Clave

5 "five"
2 "two"

1 "one"

9 "nine"

3 "three"
179

module DataStructures.Dictionary.AVLDictionary
( Dict
, empty
, isEmpty
, insert
, get
) where

import qualified DataStructures.BinarySearchTree.AVL as T

data Rel a b = a :-> b

Dos asociaciones son iguales
instance (Eq a) => Eq (Rel a b) where
sii tienen la misma clave
(k :-> _) == (k' :-> _) = (k == k')

instance (Ord a) => Ord (Rel a b) where
(k :-> _) <= (k' :-> _) = (k <= k')

180

data Dict a b = D (T.AVL (Rel a b))

-- las operaciones son delegadas a operaciones con AVL
empty :: Dict a b
empty = D T.empty
Un diccionario es vaco si lo

es como rbol AVL
isEmpty :: Dict a b -> Bool
isEmpty (D avl) = T.isEmpty avl

insert :: (Ord a) => a -> b -> Dict a b -> Dict a b
insert k v (D avl) = D (T.insert (k :-> v) avl)

valueOf :: (Ord a) => a -> Dict a b -> Maybe b
valueOf k (D avl) =
case T.search (k :-> undefined) avl of
Nothing
-> Nothing
Just (_ :-> v) -> Just v

181

 La complejidad de las operaciones son las

correspondientes a un rbol AVL:

Operacin
empty
isEmpty
insert
valueOf

Coste
O(1)
O(1)
O(log n)
O(log n)

182