Download 6ppt-pdf - Escuela de Ingeniería Informática

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5 – Arboles
Un árbol A es un conjunto finito de uno o más nodos tales:
1. Existe un nodo especial denominado RAIZ(V1) del árbol
2. Los nodos restantes (V1 ,V2 ,...Vn) se dividen en m>=0 conjuntos disjuntos
denominados A1, A2, A3,...Am, cada uno de los cuales es, a su vez, un árbol.
Estos árboles se llaman subárboles de la RAIZ.
A
B
C
E
F
D
G
K
H
I
J
L
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
G
H
I
J
L
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
2.5.1 – Arboles Binarios
Un Arbol binario es un conjunto finito de cero o más nodos tales que:
1. Existe un nodo denominado raíz del árbol
2. Cada nodo tiene 0, 1 o 2 subárboles, conocidos como subárbol izquierdo y
subárbol derecho.
Se dice que dos árboles binarios son similares si tienen la misma estructura
A
C
T
E
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
C
B
E
D
C
D
E
A
B
3
4
A
Se dice que un árbol binario es equilibrado si las alturas de los dos subárboles
de cada nodo del árbol se diferencian en una unidad como máximo.
C
N
D
F
Desarrollado por
Ricardo Soto De Giorgis
B
E
T
S
F
C
N
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.1 – Arboles Binarios
Un árbol binario es completo si todos sus
nodos, excepto las hojas, tienen
exactamente dos subárboles.
B
A
R
E
A
Se dice que dos árboles binarios son
equivalentes si tienen la misma
estructura
y además
la misma
información
A
D
D
Capítulo 2 - Estructuras Dinámicas
2.5.1 – Arboles Binarios
B
A
Raíz: Nodo que no tiene antecesores
Nodo: Vértices o elementos del árbol
B
C
Nodo Terminal u hoja: Vértices o elementos
del árbol que no contienen subárboles.
E
F
Hermanos: Nodos de un mismo padre.
Nodos Interiores: Nodos que no son hoja ni raíz.
Bosque: Colección de dos o más árboles.
K
Arista: Enlace entre dos nodos consecutivos.
Camino: Secuencia de aristas consecutivas.
Rama: Camino que termina en hoja.
Nivel: Longitud que se determina por la longitud del camino
desde la raíz al nodo específico.
Altura o profundidad: el número máximo de nodos de una
rama. Equivale al nivel más alto de los nodos más uno.
Peso: es el número de nodos terminales.
Grado: el número de hijos que salen de un nodo
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5 – Arboles
Desarrollado por
Ricardo Soto De Giorgis
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
2.5.1 – Arboles Binarios
A
B
T
Un árbol binario es degenerado si todos sus nodos excepto el último tienen
sólo un subárbol
C
N
E
D
F
A
S
B
A
Un árbol binario es lleno si todas sus
hojas están al mismo nivel y todos sus
nodos interiores tienen cada uno 2 hijos.
B
T
T
C
N
D
A
B
N
C
D
E
Un árbol binario de altura h puede tener
como máximo 2h-1 nodos.
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
1
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Capítulo 2 - Estructuras Dinámicas
2.5.2 – Representación de Arboles Binarios mediante punteros
2.5.2 – Recorrido de árboles binarios
Se denomina recorrido de un árbol al proceso que permite acceder una sola
vez a cada uno de los nodos del árbol. Cuando un árbol se recorre, el
conjunto completo de nodos se examina.
INFO
A
B
A
IZQ
C
B
DER
Recorrido pre-orden
1. Visitar nodo raíz
2. Recorrer el subárbol izquierdo en pre-orden
3. Recorrer el subárbol derecho en pre-orden
C
E
T
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
T
Recorrido in-orden
1. Recorrer el subárbol izquierdo en in-orden
2. Visitar nodo raíz
3. Recorrer el subárbol derecho en in-orden
E
S
S
Recorrido post-orden
1. Recorrer el subárbol izquierdo en post-orden
2. Recorrer el subárbol derecho en post-orden
3. Visitar nodo raíz
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Desarrollado por
Ricardo Soto De Giorgis
2.5.2.1 – Recorrido in-orden
Recorrido in-orden
1. Recorrer el subárbol izquierdo en in-orden
2. Visitar nodo raíz
3. Recorrer el subárbol derecho en in-orden
Recorrido pre-orden
1. Visitar nodo raíz
2. Recorrer el subárbol izquierdo en pre-orden
3. Recorrer el subárbol derecho en pre-orden
ABDHIEJKCFLMGNO
A
B
Desarrollado por
Ricardo Soto De Giorgis
I
B
G
F
L
K
HDIBJEKALFMCNGO
A
C
E
J
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.2.1 – Recorrido pre-orden
H
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Capítulo 2 - Estructuras Dinámicas
D
Escuela de Ingeniería
Informática
M
D
N
O
Escuela de Ingeniería
Informática
H
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Desarrollado por
Ricardo Soto De Giorgis
I
C
E
J
G
F
K
L
M
N
O
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Capítulo 2 - Estructuras Dinámicas
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.2.1 – Recorrido post-orden
2.5.3 - Notaciones
La notación algorítmica que utilizaremos es la siguiente:
Recorrido post-orden
1. Recorrer el subárbol izquierdo en post-orden
2. Recorrer el subárbol derecho en post-orden
3. Visitar nodo raíz
puntero_a <tipo de dato>:punt
puntero_a nodo:punt
struct nodo{
registro: nodo
HIDJKEBLMFNOGCA
A
int elem;
entero:elem
punt:izq, der
B
struct nodo *izq, *der;
}
fin_registro
C
Creación de un árbol:
D
E
struct nodo* Crear(){
G
F
struct nodo* L = (struct nodo*)malloc(sizeof(struct
nodo));
L-> elem = 5;
L-> der=NULL;
H
I
J
K
L
M
N
O
L-> izq=NULL;
return L;
}
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
2
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
Desarrollado por
Ricardo Soto De Giorgis
ABDHIEJKCFLMGNO
B
D
C
E
I
J
F
K
G
L M N
O
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
HDIBJEKALFMCNGO
Desarrollado por
Ricardo Soto De Giorgis
HIDJKEBLMFNOGCA
I
C
E
J
F
K
Escuela de Ingeniería
Informática
G
L M N
O
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Ejercicios (Recorrido de árboles)
nuevo = (struct pila*)malloc(sizeof(struct pila));
nuevo->valor = valor;
nuevo->sgte = *cima;
*cima = nuevo;
}
struct nodo* pop(struct pila **cima) {
struct pila *p;
struct nodo *v;
p = *cima;
if(!*cima){
return (NULL);
}else{
*cima = p->sgte;
v = p->valor;
free(p);
return(v);
}
}
A
B
D
C
E
I
J
F
K
G
L M N
O
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.4 – Arboles atados
2.5.4 – Arboles atados
Se dice que un árbol binario está atado si cada nodo del árbol posee un
campo adicional de tipo puntero direccionado (si el recorrido lo requiere) al
nodo siguiente en un determinado recorrido (pre-orden, in-orden o postorden).
Atadura Unidireccional
D-B F-E-A G-C L-J -H K
A
B
Existen distintas formas de atar un
árbol binario, pero cada una
corresponderá al recorrido en
cuestión.
H
C
A
D
B
D
Escuela de Ingeniería
Informática
D
void push(struct pila **cima, struct nodo *valor) {
struct pila *nuevo;
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Desarrollado por
Ricardo Soto De Giorgis
A
B
Capítulo 2 - Estructuras Dinámicas
Ejercicios (Recorrido de árboles)
Desarrollado por
Ricardo Soto De Giorgis
Ejercicios (Recorrido de árboles)
void inorden(struct nodo *p){
struct pila *cima;
printf("\n inorden:\n");
cima=NULL;
push(&cima,NULL);
while(cima){
while(p){
push(&cima,p);
p=p->izq;
}
H
if(cima){
p=pop(&cima);
if(cima)printf("%d-", p->elem);
}
p=p->der;
}
}
A
Escuela de Ingeniería
Informática
void postorden(struct nodo *p){
struct pila *cima;
printf("\n postorden:\n");cima=NULL;
push(&cima,NULL);
while(cima){
while(p){
push(&cima,p);
if(p->der){
push(&cima,p->der);
push(&cima,NULL);
}
p=p->izq;}
p=pop(&cima);
while(p){
printf("%d-", p->elem);
p=pop(&cima);
}
H
if(!p){
p=pop(&cima);
}
}
}
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
Ejercicios (Recorrido de árboles)
void preorden(struct nodo *p){
struct pila *cima;
printf("\n preorden:\n");
cima=NULL;
push(&cima,NULL);
while(p){
printf("%d-", p->elem);
if(p->der){
push(&cima,p->der);
}
if(p->izq){
p=p->izq;
}else{
p=pop(&cima);
H
}
}
}
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
I
E
J
E
C
K
L
G
H
G
F
F
M
N
O
ICI 241 – Estructura de Datos
J
K
L
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
3
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.5 – Arboles binarios de búsqueda
2.5.5 – Arboles binarios de búsqueda
Supongamos que se tiene n claves distintas en orden ascendente K1, K2,
K3,…,Kn y que se tiene un árbol binario T de n nodos.
Se define Ni como el iésimo nodo visitado si se recorre T en In-orden. Luego
si se almacena la clave Ki en el nodo Ni, el árbol resultante tiene la siguiente
propiedad:
Esta propiedad garantiza que el recorrido in-orden de T dará una lista
ordenada de los elementos de T.
Ki
H
Para cada nodo Ni con clave Ki, todas las claves en los nodos del subárbol
izquierdo son menores que Ki y todas las claves en los nodos del subárbol
derecho son mayores que Ki.
D
B
Ki
<Ki
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
L
F
N
J
C
Desarrollado por
Ricardo Soto De Giorgis
E
G
I
K
M
O
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.5 – Arboles binarios de búsqueda
2.5.5 – Arboles binarios de búsqueda
struct nodo* buscar(struct nodo *a, struct nodo **ant, int valor){
int enc;
struct nodo *anterior;
enc=0;
anterior=NULL;
while(!enc && (a)){
if(a->elem==valor){
enc=1;
}else{
anterior=a;
if(valor<a->elem){
a=a->izq;
}else{
a=a->der;
}
}
}
*ant=anterior;
return a;
}
Desarrollado por
Ricardo Soto De Giorgis
>Ki
>Ki
A
Desarrollado por
Ricardo Soto De Giorgis
<Ki
Escuela de Ingeniería
Informática
void insertar(struct nodo **a, int valor){
struct nodo *nuevo,*ant;
/* Buscar posicion de insercion */
p=buscar(*a, &ant, valor);
if(!p){
/*crear nodo nuevo*/
nuevo = (struct nodo*)malloc(sizeof(struct nodo));
nuevo->elem = valor;
nuevo->izq=nuevo->der=NULL;
if(!ant){
*a=nuevo;
}else{
if(valor<ant->elem){
ant->izq=nuevo;
}else{
ant->der=nuevo;
}
}
}else{
printf("nodo ya esta en el arbol");
}
}
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.5 – Arboles binarios de búsqueda
void borrar(struct nodo **a, int valor) {
struct nodo *a1,*ab, *padre,*actual,*nodo;
int aux;
actual=buscar(*a, &padre, valor); /* Buscar posicion de eliminacion */
while(actual) {
if(eshoja(actual)) {
if(padre){
if(padre->der == actual){ /*Nodo a eliminar es hoja derecha*/
padre->der = NULL;
}else{ /*Nodo a eliminar es hoja izquierda*/
padre->izq = NULL;
}
}else
*a=NULL;
}
2.5.6 – Arboles AVL
Se dice que un árbol binario está balanceado si y sólo si en cada nodo las
alturas de sus 2 subárboles difieren como máximo en 1.
Todos los árboles perfectamente balanceados son árboles AVL.
actual=NULL;
free(actual);
H
NO AVL
return;
}else{
padre = actual;
if(actual->der) { /*buscar el nodo de mas a la izquierda del subarbol derecho*/
nodo = actual->der;
while(nodo->izq) {
padre = nodo; nodo = nodo->izq;
}
}else{ /*buscar el nodo de mas a la derecha del subarbol izquierdo */
nodo = actual->izq;
while(nodo->der) {
padre = nodo; nodo = nodo->der;
}
}
aux = actual->elem; /* Intercambio */
actual->elem = nodo->elem;
nodo->elem = aux;
actual = nodo;
}
D
H
AVL
L
F
D
L
F
E
}
}
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
4
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
AVL
2.5.6.1 – Rotaciones
D
H
D
B
L
L
F
J
A través de rotaciones es posible transformar un árbol binario cualquiera en
un árbol AVL.
N
Rotación derecha simple
K
E
M
O
B
A
A
V
T3
H
H
NO AVL
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
H
2.5.6 – Arboles AVL
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
D
D
B
F
L
F
T1
N
J
I
T2
T2
((T1 A T2) B T3)
M
B
T1
T3
(T1 A (T2 B T3))
O
P
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.6.1 – Rotaciones
2.5.6.1 – Rotaciones
Rotación izquierda simple
Rotación derecha doble
A
B
B
T1
ICI 241 – Estructura de Datos
T2
A
T3
T1
C
A
T3
T2
B
T4
A
B
T1
T1
(T1 A (T2 B T3))
T2
((T1 A T2) B T3)
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
Desarrollado por
Ricardo Soto De Giorgis
T2
T3
T4
T3
(T1 A (T2 B T3) C T4)
Desarrollado por
Ricardo Soto De Giorgis
C
Escuela de Ingeniería
Informática
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
((T1 A T2) B (T3 C T4))
ICI 241 – Estructura de Datos
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.6.1 – Rotaciones
Ejercicios (Rotaciones)
Rotación izquierda doble
A
B
C
T1
B
A
T4
T1
T2
T2
T3
T4
T3
(T1 A (T2 B T3) C T4)
Desarrollado por
Ricardo Soto De Giorgis
C
Escuela de Ingeniería
Informática
((T1 A T2) B (T3 C T4))
ICI 241 – Estructura de Datos
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
5
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Capítulo 2 - Estructuras Dinámicas
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.7 – Arboles B
2.5.7 – Arboles B
K<20
20<K<40
Se define un árbol B como un árbol de orden m que cumple con las
siguientes propiedades.
40<K<60
20
40
60
80
24
29
7
8
Ningún nodo tiene más de m hijos.
Cada nodo excepto la raíz tiene al menos m / 2 hijos.
Todos los caminos desde la raíz a una hoja tienen la misma longitud.
4
9
14
19
34
39
Todas las hojas están al mismo nivel.
El número de claves en el nodo interno es uno menos que el número de
sus hijos.
0
1
2
3
5
6
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
13
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.7 – Inserción en un árbol B
2.5.7 – Inserción en un árbol B
Para determinar el punto de inserción apropiado para el nuevo registro,
considerar los siguientes pasos.
Si el nodo en el cual se debe insertar el registro aún no ha excedido su
capacidad (m-1 registros o claves) insertando o manteniendo el orden
establecido.
40
20
12
Insercíón y eliminación de datos
Búsqueda más rápida
Menor altura
Escuela de Ingeniería
Informática
11
Desventajas
Ventajas
Desarrollado por
Ricardo Soto De Giorgis
10
60
Si el nodo en el cual se debe insertar el registro excede su capacidad
producto de esta nueva inserción (overflow), se debe proceder a dividir el
nodo según el siguiente criterio.
Considerar como si el nodo tuviera capacidad para n registros y por lo
tanto n+1 hijos (punteros).
50
20
80
40
60
80
Determinar el registro medio de acuerdo a:
Registro medio (RM): p/2 = (n + 1)/2
20
Desarrollado por
Ricardo Soto De Giorgis
40
60
Registro medio (RM): 5/2 = (4 + 1)/2
80
Escuela de Ingeniería
Informática
ICI 241 – Estructura de Datos
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
430 480
Árbol B de orden 5
380 395 406 412
50
60
80
406 412
Desarrollado por
Ricardo Soto De Giorgis
Escuela de Ingeniería
Informática
451 472
Después de insertar 382
493 506 511
Después de insertar 518 y 508
50
40
493 506 511
451 472
395 430 480
380 382
20
Escuela de Ingeniería Informática
2.5.7 – Inserción en un árbol B
Tomar el RM e insertarlo en el nodo padre. Producto de lo anterior, el
nodo se dividirá en 2 y el nodo padre quedará con un hijo más.
40
ICI 241 – Estructura de Datos
Capítulo 2 - Estructuras Dinámicas
2.5.7 – Inserción en un árbol B
20
=3
395 430 480 508
60
380 382
80
ICI 241 – Estructura de Datos
Desarrollado por
Ricardo Soto De Giorgis
406 412
Escuela de Ingeniería
Informática
451 472
493 506
511 518
ICI 241 – Estructura de Datos
6
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Capítulo 2 - Estructuras Dinámicas
Escuela de Ingeniería Informática
Capítulo 2 - Estructuras Dinámicas
2.5.7 – Arboles B*
2.5.7 – Arboles B+
Hay diversas formas de mejorar la utilización del almacenamiento en un
árbol B. Un método es retrasar la división de un nodo cuando se desborda.
En lugar de eso, se redistribuyen en forma uniforme las claves en el nodo y
en uno de sus hermanos adyacentes.
Una de las principales desventajas del árbol B es la dificultad de recorrer las
claves en forma secuencial. El árbol B+, conserva la propiedad de acceso
aleatorio rápido del árbol B, al mismo tiempo que permite un acceso
secuencial rápido.
98
100
Árbol B de orden 7
10
20
30
40
50
60
Después de insertar 35 se
redistribuyen los hermanos
50
10
20
30
35
40
36
60
8
17
36
Escuela de Ingeniería
Informática
81
104 119
42
53
56
65
72
81
83
96
98
102 104
107 112 119
125 127
100 110 120 130
R8 R17 R36
Desarrollado por
Ricardo Soto De Giorgis
53
110 120 130
ICI 241 – Estructura de Datos
Desarrollado por
Ricardo Soto De Giorgis
R42 R53
R56 R65 R72 R81
Escuela de Ingeniería
Informática
R83 R96 R98
R
R
102
104
R
R
R
R
R
107
112
119
125
127
ICI 241 – Estructura de Datos
7