by erika pulido 15 years ago
1306
More like this
es una estructura de datos de árbol, una variante de Árbol-B utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2.
El número de claves que pueden ser indexadas usando un árbol-B+ está en función del orden del árbol y su altura.
El mínimo número de claves por registro es la mitad del máximo número de claves.
El número máximo de claves en un registro es llamado el orden del árbol-B+.
Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos.
Rebalanceo después de la eliminación
Eliminacion
Tipos
Eliminación en un nodo interno
Eliminación en un nodo hoja
La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades
1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento. 2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos. 3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera: 1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento. 2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador. 3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.
Todas las inserciones se hacen en los nodos hoja.
Prosedimiento
1. . Situarse en el nodo raíz. 2. (*). Comprobar si contiene la clave a buscar. 1. . Encontrada fin de procedimiento . 2. . No encontrada: 1. Si es hoja no existe la clave. 2. En otro caso el nodo actual es el hijo que corresponde: 1. . La clave a buscar k < k1 :hijo izquierdo. 2. . La clave a buscar k > ki y k < ki+1 hijo iesimo. 3. . Volver a paso 2(*).
Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo.
Las búsquedas se realizan de la misma manera que en los ABB, pero al estar el árbol equilibrado la complejidad de la búsqueda nunca excederá de O (log n).
Extracción
Una extracción trae consigo una disminución de laaltura de la rama donde se extrajo y tendrá como efecto un cambio en el factor de equilibrio del nodo padre de la rama en cuestión, pudiendo necesitarse una rotación.
insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodoque pueda haberse desequilibrado durante la inserción.
Proceso de inserción:
desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario
insertar el nuevo nodo con factor de equilibrio “equilibrado”
buscar hasta encontrar la posición de inserción o modificación.
Rotaciones
El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio.
Rotacion doble a la izquierda
Rotacion doble a la derecha
Rotacion simple a la izquierda
De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).
Rotacion simple a la derecha
De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’)será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).
Factor de equilibrio
Si el factor de equilibrio de un nodo es
-1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.
1 -> el nodo está equilibrado y su subárbol derecho es un nivel más alto.
0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.
FE = altura subárbol derecho - altura subárbol izquierdo
Es la diferencia entre las alturas del árbol derecho y el izquierdo
Es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis.
Propiedades
El camino más largo desde la raíz hasta una hoja no es más largo que 2 veces el camino más corto desde la raíz del árbol a una hoja en dicho árbol.
Cada camino simple desde un nodo a una hoja descendiente contiene el mismo número de nodos negros, ya sea contando siempre los nodos negros nulos, o bien no contándolos nunca.
Los hijos de todo nodo rojo son negros (también llamada "Propiedad del rojo").
Todas las hojas son negras (las hojas son los hijos nulos).
La raíz es negra.
Todo nodo es o bien rojo o bien negro.
Operaciones
Eliminación
Inserción
Búsqueda
Rotación
Un árbol rojo-negro es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables
Recorridos en amplitud (o por niveles)
el recorrido se realiza en orden por los distintos niveles del árbol.
Inorden
Posorden
Preorden
árbol binario completo
árbol binario perfecto
es un árbol binario lleno en el que todas las hojas están a la misma profundidad
árbol binario lleno
es un árbol en el que cada nodo tiene cero o dos hijos.
Tiene un hijo izquierdo y un hijo derecho.
No tiene hijos (hoja).
Longitud de camino
Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X.
Peso
Es el número de nodos del árbol sin contar la raíz.
Altura
Es el máximo número de niveles de todos los nodos del árbol.
Nivel
Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
Grado del arbol
Es el máximo grado de todos los nodos del árbol.
Grado
Es el número de descendientes directos de un determinado nodo.
Nodo interno
Es un nodo que no es raíz ni terminal.
Hoja
Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
Hermano
Dos nodos serán hermanos si son descendientes directos de un mismo nodo.
Padre
X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
Hijo.
X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
