Arbol rojinegro

´ 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 4. Eliminaci´n o

Page 2 of 28 Full Screen Quit

´ Propiedades de los Arboles RojiNegros • Un ´rbol rojinegro es un ´rbol de b´squeda bia a u nariacon 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.

Contents

Page 3 of 28 Full Screen Quit

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

3. La ra´ es negra. ız 4. Si un nodo es rojo, entonces sus hijos son negros. 5. Cada ruta simple de un nodo a un hoja descendiente contiene el mismo n´mero de nodos negros. u Estas propiedades hacen que un ´rbol rojinegro sea a balanceado.

Page 4 of 28 Full Screen Quit

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

Contents
14

17

4121

30
NIL

47
NIL

10

16
NIL NIL

19
NIL

23
NIL NIL

28
NIL

38

7

12
NIL NIL NIL NIL

15
NIL NIL

20
NIL NIL

35
NIL NIL

39
NIL

Page 5 of 28
3

Full Screen Quit

NIL

NIL

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

Contents
1421 30

41

47

10

16

19

23

28

38 39

7

12

15

20

35

Page 6 of 28 Full Screen

3

NIL

Quit

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) hasta una hoja. Lema 1 Un ´rbol rojinegro con n nodo internos tiene a una altura de 2 log (n + 1), como m´ximo. aDebido a este lema, las operaciones Search, Minimum, Maximum, Successor y Predecessor pueden ser implementadas en un tiempo O(log n) en a ´rboles rojinegros.

Contents

Page 7 of 28 Full Screen Quit

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

• El resultado de insertar o eliminar nodos en un a ´rbol rojinegrousando 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 o los colores de algunos de los nodos y tambi´n came biar el apuntador al nodo.

Page 8 of 28 Full Screen Quit

Rotaciones (cont.) El apuntador al nodo se cambia medianteuna rotaci´n, la cual es una operaci´n local que preserva o o el ordenamiento de las llaves. La siguiente figura muestra los dos tipos de rotaciones: rotaci´n a la izquierda y a la derecha. o

Contents

y
Page 9 of 28 Full Screen Quit

RIGHT−ROTATE(T, y )
γ α

x

x

y

α

β

L EFT− OTATE(T, x ) R

β

γ

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

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

Page 10 of 28 Full Screen Quit

3 4 5 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] ← xPone x a la izquierda de y p[x] ← y

Rotaciones (cont.) La siguiente figura muestra como opera LeftRotate.
7 4 11 x y 3 6 9 18

Contents

2

14

19

L EFT− OTATE(T, x ) R

Page 11 of 28 Full Screen Quit
4

7

y x

18

3

6

11

19

2

9

14

Rotaciones (cont.) • La rotaci´n a la izquierda “pivotea” alrededor del o enlace de x a y.
Contents

• Esto hace...