arbolb
Páginas: 19 (4509 palabras)
Publicado: 4 de noviembre de 2015
168
Cap´ıtulo 4. Representaci´on de conjuntos mediante ´arboles
En cuanto al tiempo de ejecuci´on, b´asicamente podemos aplicar el mismo an´alisis
que en la inserci´on. El tiempo total para una supresi´on ser´a proporcional al nivel de la
clave buscada en el AVL, puesto que el tiempo en cada nivel es constante (o limitado
por una constante). Como el nivel m´aximo est´a en un O(log n), el tiempode ejecuci´on
ser´a tambi´en un O(log n).
Ejemplo 4.3 En un ´arbol AVL inicialmente vac´ıo almacenamos n´
umeros enteros. Insertamos los siguientes elementos: 7, 14, 32, 9, 40, 8, 3, 4. Despu´es eliminamos del ´arbol los
valores: 9, 32, 3. Vamos a ver la estructura del a´rbol despu´es de aplicar cada operaci´on,
indicando los casos en los que ocurre desbalanceo y la rotaci´on que se aplica.
Elresultado aparece en la figura 4.22. Se puede ver que en la inserci´on se requieren
en total 3 rotaciones, para 8 inserciones. Por otro lado, de las 3 eliminaciones ocurren
desbalanceos en 2 de ellas.
4.4.
´
Arboles
B
Los ´
arboles B 14 constituyen una categor´ıa muy importante de estructuras de datos,
que permiten una implementaci´on eficiente de conjuntos y diccionarios, para operaciones
deconsulta y acceso secuencial. Existe una gran variedad de a´rboles B: los a´rboles B,
B+ y B*; pero todas ellas est´an basadas en la misma idea, la utilizaci´on de ´arboles de
b´
usqueda no binarios y con condici´on de balanceo.
En concreto, los a´rboles B+ son ampliamente utilizados en la representaci´on de
´ındices en bases de datos. De hecho, este tipo de ´arboles est´an dise˜
nados espec´ıficamentepara aplicaciones de bases de datos, donde la caracter´ıstica fundamental es la predominancia del tiempo de las operaciones de entrada/salida de disco en el tiempo de ejecuci´on
total. En consecuencia, se busca minimizar el n´
umero de operaciones de lectura o escritura
de bloques de datos del disco duro o soporte f´ısico.
4.4.1.
´
Arboles
de b´
usqueda no binarios
En cierto sentido, losa´rboles B se pueden ver como una generalizaci´on de la idea
de ´arbol binario de b´
usqueda a ´arboles de b´
usqueda no binarios. Consideremos la representaci´on de ´arboles de b´
usqueda binarios y n-arios de la figura 4.23.
En un ABB (figura 4.23a) si un nodo x tiene dos hijos, los nodos del sub´arbol
izquierdo contienen claves menores que x y los del derecho contienen claves mayores que
x. En un ´arbolde b´
usqueda no binario (figura 4.23b), cada nodo interno puede contener q
claves x1 , x2 , . . ., xq , y q + 1 punteros a hijos que est´an “situados” entre cada par de claves
y en los dos extremos. Las claves estar´an ordenadas de menor a mayor: x1 < x2 < . . . < xq .
Adem´as, el hijo m´as a la izquierda contiene claves menores que x1 ; el hijo entre x1 y x2
contiene claves mayores que x1 ymenores que x2 ; y as´ı sucesivamente hasta el hijo m´as a
la derecha que contiene claves mayores que xq .
14
La B viene de balanceados.
´
4.4. Arboles
B
I(7)
169
I(14)
7
I(32)
7
Caso DD(7)
RSD(7)
7
14
7
14
I(9)
14
7
32
32
9
32
I(40)
I(8)
14
7
7
32
9
Caso DI(7)
RDD(7)
14
40
8
9
8
7
40
8
I(4)
8
7
4
40
3
3
E(9)
14
8
32
9
32
9
40
3
Caso ID(7)
RDD(7)
14
I(2)14
32
7
40
I(3)
14
32
9
I(40)
14
8
32
9
4
40
h2
7
3
Caso h1=h2
RSI(8)
14
4
32
9
3
40
h1
7
E(32)
14
32
40
8
7
4
E(32)
14
4
3
4
32
8
Caso h1>h2
RDI(14)
14
40
7
h2
3
3
8
7
4
40
E(3)
8
14
7
40
8
4
14
7
40
h1
Figura 4.22: Inserci´on y eliminaci´on de elementos en un AVL, seg´
un las operaciones del
ejemplo 4.3.
Definici´
on de ´
arbol B
Un ´
arbol B deorden p es b´asicamente un ´arbol de b´
usqueda n-ario donde los
nodos tienen p hijos como m´aximo, y en el cual se a˜
nade la condici´on de balanceo de que
todas las hojas est´en al mismo nivel. La definici´on formal de a´rbol B es la siguiente.
Definici´
on 4.6 Un ´
arbol B de orden p, siendo p un entero mayor que 2, es un a´rbol
con las siguientes caracter´ısticas:
1. Los nodos internos son de...
Cap´ıtulo 4. Representaci´on de conjuntos mediante ´arboles
En cuanto al tiempo de ejecuci´on, b´asicamente podemos aplicar el mismo an´alisis
que en la inserci´on. El tiempo total para una supresi´on ser´a proporcional al nivel de la
clave buscada en el AVL, puesto que el tiempo en cada nivel es constante (o limitado
por una constante). Como el nivel m´aximo est´a en un O(log n), el tiempode ejecuci´on
ser´a tambi´en un O(log n).
Ejemplo 4.3 En un ´arbol AVL inicialmente vac´ıo almacenamos n´
umeros enteros. Insertamos los siguientes elementos: 7, 14, 32, 9, 40, 8, 3, 4. Despu´es eliminamos del ´arbol los
valores: 9, 32, 3. Vamos a ver la estructura del a´rbol despu´es de aplicar cada operaci´on,
indicando los casos en los que ocurre desbalanceo y la rotaci´on que se aplica.
Elresultado aparece en la figura 4.22. Se puede ver que en la inserci´on se requieren
en total 3 rotaciones, para 8 inserciones. Por otro lado, de las 3 eliminaciones ocurren
desbalanceos en 2 de ellas.
4.4.
´
Arboles
B
Los ´
arboles B 14 constituyen una categor´ıa muy importante de estructuras de datos,
que permiten una implementaci´on eficiente de conjuntos y diccionarios, para operaciones
deconsulta y acceso secuencial. Existe una gran variedad de a´rboles B: los a´rboles B,
B+ y B*; pero todas ellas est´an basadas en la misma idea, la utilizaci´on de ´arboles de
b´
usqueda no binarios y con condici´on de balanceo.
En concreto, los a´rboles B+ son ampliamente utilizados en la representaci´on de
´ındices en bases de datos. De hecho, este tipo de ´arboles est´an dise˜
nados espec´ıficamentepara aplicaciones de bases de datos, donde la caracter´ıstica fundamental es la predominancia del tiempo de las operaciones de entrada/salida de disco en el tiempo de ejecuci´on
total. En consecuencia, se busca minimizar el n´
umero de operaciones de lectura o escritura
de bloques de datos del disco duro o soporte f´ısico.
4.4.1.
´
Arboles
de b´
usqueda no binarios
En cierto sentido, losa´rboles B se pueden ver como una generalizaci´on de la idea
de ´arbol binario de b´
usqueda a ´arboles de b´
usqueda no binarios. Consideremos la representaci´on de ´arboles de b´
usqueda binarios y n-arios de la figura 4.23.
En un ABB (figura 4.23a) si un nodo x tiene dos hijos, los nodos del sub´arbol
izquierdo contienen claves menores que x y los del derecho contienen claves mayores que
x. En un ´arbolde b´
usqueda no binario (figura 4.23b), cada nodo interno puede contener q
claves x1 , x2 , . . ., xq , y q + 1 punteros a hijos que est´an “situados” entre cada par de claves
y en los dos extremos. Las claves estar´an ordenadas de menor a mayor: x1 < x2 < . . . < xq .
Adem´as, el hijo m´as a la izquierda contiene claves menores que x1 ; el hijo entre x1 y x2
contiene claves mayores que x1 ymenores que x2 ; y as´ı sucesivamente hasta el hijo m´as a
la derecha que contiene claves mayores que xq .
14
La B viene de balanceados.
´
4.4. Arboles
B
I(7)
169
I(14)
7
I(32)
7
Caso DD(7)
RSD(7)
7
14
7
14
I(9)
14
7
32
32
9
32
I(40)
I(8)
14
7
7
32
9
Caso DI(7)
RDD(7)
14
40
8
9
8
7
40
8
I(4)
8
7
4
40
3
3
E(9)
14
8
32
9
32
9
40
3
Caso ID(7)
RDD(7)
14
I(2)14
32
7
40
I(3)
14
32
9
I(40)
14
8
32
9
4
40
h2
7
3
Caso h1=h2
RSI(8)
14
4
32
9
3
40
h1
7
E(32)
14
32
40
8
7
4
E(32)
14
4
3
4
32
8
Caso h1>h2
RDI(14)
14
40
7
h2
3
3
8
7
4
40
E(3)
8
14
7
40
8
4
14
7
40
h1
Figura 4.22: Inserci´on y eliminaci´on de elementos en un AVL, seg´
un las operaciones del
ejemplo 4.3.
Definici´
on de ´
arbol B
Un ´
arbol B deorden p es b´asicamente un ´arbol de b´
usqueda n-ario donde los
nodos tienen p hijos como m´aximo, y en el cual se a˜
nade la condici´on de balanceo de que
todas las hojas est´en al mismo nivel. La definici´on formal de a´rbol B es la siguiente.
Definici´
on 4.6 Un ´
arbol B de orden p, siendo p un entero mayor que 2, es un a´rbol
con las siguientes caracter´ısticas:
1. Los nodos internos son de...
Leer documento completo
Regístrate para leer el documento completo.