Nada

´
Arboles RojiNegros
Profesor: Julio C´sar L´pez
e
o
jlopez@eisc.univalle.edu.co

October 18, 2003

Contents

Page 1 of 28
Full Screen
Quit

Contenido
1. Propiedades de los ´rboles rojinegros
a
Contents

2. Rotaciones
3. Inserci´n
o

Page 2 of 28
Full Screen
Quit

4. Eliminaci´n
o

´
Propiedades de los Arboles RojiNegros

Contents

Page 3 of 28
Full ScreenQuit

• Un ´rbol rojinegro es un ´rbol de b´squeda bia
a
u
naria con un bit extra de almacenamiento por nodo:
su color, el cual puede ser rojo o negro.
• Lo anterior indica que cada nodo del ´rbol contiene
a
los campos: color, key, left, right, y p.

Propiedades (cont.)
Un ´rbol de b´squeda binaria es rojinegro si satisa
u
face las siguientes propiedades:
1. Todo nodo es rojo onegro.
2. Toda hoja (nil) es negra.
Contents

3. La ra´ es negra.
ız
4. Si un nodo es rojo, entonces sus hijos son negros.

Page 4 of 28

5. Cada ruta simple de un nodo a un hoja descendiente
contiene el mismo n´mero de nodos negros.
u

Full Screen
Quit

Estas propiedades hacen que un ´rbol rojinegro sea
a
balanceado.

Propiedades (cont.)
La siguiente figura es un ejemplo de un´rbol roa
jinegro.
26

17

Contents

41

14

21

30

47
NIL

10

16

19
NIL

7

12

23

NIL

NIL

15

28
NIL

NIL

38
NIL

20

39

35

Page 5 of 28
NIL

3

Full Screen
Quit

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

Propiedades (cont.)
Para simplificar las condiciones de l´
ımites, seusar´ un
a
nodo centinela para representar NIL como en siguiente
figura :
26

17

41

Contents
14

21

10

7

Page 6 of 28

16

12

15

19

30

23

28

20

38

35

3

Full Screen
NIL

Quit

47

39

Propiedades (cont.)
Se denomina altura negra del nodo x, bh(x), al
n´mero de nodos negros en cualquier camino desde el
u
nodo x (sin incluirlo) hastauna hoja.

Contents

Page 7 of 28
Full Screen
Quit

Lema 1
Un ´rbol rojinegro con n nodo internos tiene
a
una altura de 2 log (n + 1), como m´ximo.
a
Debido a este lema, las operaciones Search, Minimum, Maximum, Successor y Predecessor
pueden ser implementadas en un tiempo O(log n) en
a
´rboles rojinegros.

Rotaciones
• Las operaciones Tree-Insert y Tree-Delete
toman un tiempoO(log n) en un ´rbol rojinegro
a
con n llaves.
Contents

Page 8 of 28
Full Screen
Quit

• El resultado de insertar o eliminar nodos en un
a
´rbol rojinegro usando el algoritmo de ´rboles de
a
b´squeda binaria, podr´ violar las propiedades de
u
ıa
los ´rboles rojinegros.
a
• De modo que cuando se realizan las operaciones de
inserci´n o eliminaci´n, puede que se deba cambiar
o
olos colores de algunos de los nodos y tambi´n came
biar el apuntador al nodo.

Rotaciones (cont.)
El apuntador al nodo se cambia mediante una
rotaci´n, la cual es una operaci´n local que preserva
o
o
el ordenamiento de las llaves.

Contents

La siguiente figura muestra los dos tipos de rotaciones: rotaci´n a la izquierda y a la derecha.
o

RIGHT−ROTATE(T, y )

y

x

Page 9of 28

γ

x

Full Screen
Quit

α

β

α

L EFT− OTATE(T, x )
R

y

β

γ

Rotaciones (cont.)
El c´digo para la rotaci´n a la izquierda de un nodo x
o
o
asume que right[x] = nil.
Left-Rotate(T ,x)
1 y ← right[x]
2 right[x] ← lef t[y]

Asigna y
Convierte el sub´rbol izquierdo de y
a
al sub´rbol derecho de x
a

Contents

Page 10 of 28
Full Screen
Quit

3
45
6
7
8
9
10
11

p[lef t[y]] ← x
p[y] ← p[x]
Enlaza el padre de x a y
if p[x] = nil
then root[T ] ← y
else if x = lef t[p[x]]
then lef t[p[x]] ← y
else right[p[x]] ← y
lef t[y] ← x
Pone x a la izquierda de y
p[x] ← y

Rotaciones (cont.)
La siguiente figura muestra como opera LeftRotate.
7

4

11

x
y

3

Contents

6

9

18

2

14

19

L EFT−...