Download 3.5. Árboles Rojos-Negros 3.5. Árboles Rojos-Negros

 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
DEFINICIÓN Y PROPIEDADES
Un árbol Rojo-Negro es una representación en árbol binario de un árbol 2-3-4.
Los hijos de un nodo en un árbol Rojo-Negro son de dos tipos: Rojos y
Negros. Si el hijo ya existía en el árbol 2-3-4 original será Negro, sino será
Rojo
Propiedades
es un árbol binario de búsqueda
cada camino desde la raíz hasta las hojas tiene el mismo número de hijos
negros (esto es debido a que todos los nodos externos en un árbol 2-3-4
están en el mismo nivel y los hijos negros representan los hijos originales)
ningún camino desde la raíz a las hojas tiene dos o más hijos rojos
consecutivos
1
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
REPRESENTACIÓN (I)
Un 2-nodo será representado por un nodo q con sus dos hijos de color Negro
x
x
a
a
b
b
Un 3-nodo será representado por dos nodos conectados con un puntero Rojo
x
y
y
b
a
c
x
c
a
b
a
x
O bien
y
b
c
Un 4-nodo será representado por tres nodos, uno de los cuales es conectado a
los otros dos por punteros Rojos
x
a
y
b
z
c
y
x
d
a
z
b
c
d
2
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
REPRESENTACIÓN (II)
Ejemplo: representación de un árbol 2-3-4 como árbol Rojo-Negro
50
30
10
20
70
40
45
55
80
95
70
45
60
55
110
95
100
30
40
60 65
Caso b) del 3-nodo:
50
10
100
90
Caso a) del 3-nodo:
20
90
80
50
90
30
110
10
70
40
20
45
65
 DLSI (Univ. Alicante)
80
60
55
100
95
65
110
3
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
OPERACIONES BÁSICAS
Operaciones básicas:
Búsqueda (similar a los árboles binarios de búsqueda. Los colores de
los hijos no se usan)
Inserción (se utilizarán las transformaciones de los 4-nodos descritas
para los árboles 2-3-4)
Borrado (no se estudiará)
4
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
OPERACIONES BÁSICAS. INSERCIÓN (I)
Es la raíz de un árbol
x
z
y
b
a
y
x
d
c
z
d
c
b
a
Resultado
y
y
Cambio de color a negro
x
z
a
b
x
c
z
d
c
b
a
d
Cambio de color a negro
5
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
OPERACIONES BÁSICAS. INSERCIÓN (II)
Su padre es un 2-nodo
z
z
e
x
x
w
e
y
w
a
b
d
c
y
b
a
d
c
Resultado
z
x
z
w
a
y
b
c
e
x
e
w
d
a
y
b
c
Cambio de color:
padre a rojo
hijos a negros
d
6
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
OPERACIONES BÁSICAS. INSERCIÓN (III)
Su padre es un 3-nodo
y
y
z
w
w
v
a
e
x
b
z
f
v
d
c
d
c
b
a
f
e
x
Resultado
w
y
y
z
e
v
w
f
x
a
b
z
v
c
d
e
x
b
a
c
f
Cambio de color:
padre a rojo
hijos a negros
d
7
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
OPERACIONES BÁSICAS. INSERCIÓN (IV)
Transformación de 4-nodo:
Cambiar los hijos de rojos a negros. Cambiar enlace con el padre de negro a rojo
Si hay 2 enlaces rojos seguidos: ROTACIONES (no hay ningún cambio de color)
ROT. II
ROT. ID
z
y
z
x
d
x
a
c
y
y
b
a
c
b
x
ROT. DD
d
z
ROT. DI
x
a
a
b
c
x
d
a
y
b
z
z
c
d
y
d
b
Inserción: como máximo log n rotaciones y log n cambios de color
c
8
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
OPERACIONES BÁSICAS. INSERCIÓN. EJEMPLO (V)
Ejemplo. Insertar en un árbol Rojo-Negro inicialmente vacío los siguiente items
20, 40, 80, 65, 90, 50, 30, 35, 32, 70 y 60
40
20
DD
20, 40, 80
65
40
20
40
20
80
cambio color
80
65
80
40
40
50
90
20
80
65
20
cambio color
40
30, 35
20
80
65
90
80
30
90
65
35
50
90
50
9
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
OPERACIONES BÁSICAS. INSERCIÓN. EJEMPLO (VI)
40
40
32
DD
30
80
30
cambio color
20
35
65
90
20
50
80
35
60
40
40
cambio color
90
50
32
70
65
cambio color
30
30
20
20
35
65
35
50
65
90
90
32
32
80
80
50
70
70
60
10
 DLSI (Univ. Alicante)
Tema 3. Tipo árbol
3.5. Árboles Rojos-Negros
EJERCICIOS inserción
1) Insertar en el árbol Rojo-Negro obtenido en el ejemplo anterior los siguiente items
68, 77 y 75
11