Arboles B+

ARBOL B+

son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.

CARACTERISTICAS=

B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo .
Un arbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un arbol que satisface las siguientes propiedades:
Cada nodo tiene como máximo M hijos.
Cada nodo (excepto raiz y hojas) tiene como mínimo M/2 hijos.
La raiz tiene al menos 2 hijos si no es un nodo hoja.
Todos los nodos hoja aparecen al mismo nivel,y no tienen hijos.
Un nodo no hoja con k hijos contiene k-1 elementos almacenados.
Los hijos que cuelgan de la raíz (r1, · · · rm) tienen que cumplir ciertas condiciones :
El primero tiene valor menor que r1.
El segundo tiene valor mayor que r1 y menor que r2 etc.
El último hijo tiene mayor que rm .

OPERACIONES=

Búsqueda

La búsqueda es similar a la de los árboles binarios. 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. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.

procedimiento=

Situarse en el nodo raíz.
(*). Comprobar si contiene la clave a buscar.
. Encontrada fin de procedimiento .
. No encontrada:
Si es hoja no existe la clave.
En otro caso el nodo actual es el hijo que corresponde:
. La clave a buscar k <> ki y k <>
Inserción

Todas las inserciones se hacen en los nodos hoja.
Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
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.
De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.
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.
El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.
Si las divisiones de nodos suben hasta la raíz, se crea una nueva raíz con un único elemento como valor separador, y dos hijos. Es por esto por lo que la cota inferior del tamaño de los nodos no se aplica a la raíz. El máximo número de elementos por nodo es U-1. Así que debe ser posible dividir el número máximo de elementos U-1 en dos nodos legales. Si este número fuera impar, entonces U=2L, y cada uno de los nuevos nodos tendrían (U-2)/2 = L-1 elementos, y por lo tanto serían nodos legales. Si U-1 fuera par, U=2L-1, así que habría 2L-2 elementos en el nodo. La mitad de este número es L-1, que es el número mínimo de elementos permitidos por nodo.
Un algoritmo mejorado admite una sola pasada por el árbol desde la raiz,hasta el nodo donde la inserción tenga lugar,dividiendo todos los nodos que estén llenos encontrados a su paso.Esto evita la necesidad de volver a cargar en memoria los nodos padres,que pueden ser caros si los nodos se encuentran en una memoria secundaria.Sin embargo,para usar este algoritmo mejorado, debemos ser capaces de enviar un elemento al nodo padre y dividir el resto U-2 elementos en 2 nodos legales,sin añadir un nuevo elemento.Esto requiere que U=2L en lugar de U=L-1,lo que explica por qué algunos libros de texto imponen este requisito en la definicion de árboles-B.

Eliminación

La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades. Hay dos estrategias populares para eliminar un nodo de un árbol B.
localizar y eliminar el elemento, y luego corregir, o
hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando
Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.

Ejemplo

Prueba_Arboles
import java.awt.Color;
import java.awt.Container;
import java.awt.FlowLayout;
import java.awt.Font;
import java.awt.TextArea;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;

public class PruebaArbol extends JFrame {

Container c=getContentPane();
private JMenuBar menu;
private JMenu i1,i2;
private JMenuItem construye,mostrar,alt,hoj,anc,salir,creditos,nuevo,inor,pos,pre;
private int dato=0,nodos=0;
Arbol arbol;
String aux="R",fila=" ",columna="\n\n",cadena=new String();
private TextArea most;

public PruebaArbol(String cogollo)
{
super(cogollo);
c.setLayout(new FlowLayout());
menu = new JMenuBar();
i1 = new JMenu("ARCHIVO");
i2 = new JMenu("PROCESOS");
nuevo=new JMenuItem("NUEVO PROYECTO");
salir=new JMenuItem("SALIR");
construye=new JMenuItem("CONSTRUIR ARBOL");
mostrar=new JMenuItem("MOSTRAR ARBOL");
alt=new JMenuItem("ALTURA DEL ARBOL");
hoj=new JMenuItem("HOJAS DEL ARBOL");
anc=new JMenuItem("ANCESTROS DEL ARBOL");
inor=new JMenuItem("INORDEN");
pre=new JMenuItem("PREORDEN");
pos=new JMenuItem("POSORDEN");
creditos=new JMenuItem("CREDITOS");
i1.add(nuevo);
i1.add(construye);
i1.add(mostrar);
i1.add(creditos);
i1.add(salir);
i2.add(alt);
i2.add(hoj);
i2.add(anc);
i2.add(inor);
i2.add(pos);
i2.add(pre);


nuevo.addActionListener(new manejaEventos());
salir.addActionListener(new manejaEventos());
mostrar.addActionListener(new manejaEventos());
construye.addActionListener(new manejaEventos());
alt.addActionListener(new manejaEventos());
anc.addActionListener(new manejaEventos());
hoj.addActionListener(new manejaEventos());
inor.addActionListener(new manejaEventos());
pre.addActionListener(new manejaEventos());
pos.addActionListener(new manejaEventos());
creditos.addActionListener(new manejaEventos());
menu.add(i1);
menu.add(i2);
c.setBackground(new Color(128,0,255));
setJMenuBar(menu);

setSize( 1024 , 768 );
setVisible( true );

}


class manejaEventos implements ActionListener
{
public void actionPerformed(ActionEvent e)
{

if(e.getSource()==construye){


arbol=new Arbol();
int valor=0;
nodos=Integer.parseInt( JOptionPane.showInputDialog(null,"ingrese el numero de nodos para el arbol") );
for (int i=1;i<=nodos;i++){ dato=Integer.parseInt( JOptionPane.showInputDialog(null,"ingrese el dato a insertar en el arbol") ); arbol.insertarNodo(dato); } }//end construye if(e.getSource()==pre){ JOptionPane.showMessageDialog(null,"Preorden : "+arbol.preorden()); }//end preorden if(e.getSource()==inor){ JOptionPane.showMessageDialog(null,"Inorden : "+arbol.inorden()); }//end inorden if(e.getSource()==pos){ JOptionPane.showMessageDialog(null,"Posorden : "+arbol.posorden()); }//end posorden if(e.getSource()==alt){ JOptionPane.showMessageDialog(null,"Altura : "+arbol.altura(arbol.retornaraiz())); }//end altura if(e.getSource()==hoj){ JOptionPane.showMessageDialog(null,"Hojas : "+arbol.hojas(arbol.retornaraiz())); }//end hojas if(e.getSource()==anc){ int db=Integer.parseInt(JOptionPane.showInputDialog(null,"Ingrese el dato cuyos ancestros desea conocer")); JOptionPane.showMessageDialog(null,"Ancestro : "+arbol.ancestros(arbol.retornaraiz(),db)); }//end ancestros if(e.getSource()==mostrar){ mostrarArbol(arbol.retornaraiz(),aux); c.removeAll(); c.add(most); c.setBackground(Color.WHITE); c.repaint(); }//end mostrar if(e.getSource()==nuevo){ c.removeAll(); arbol=new Arbol(); cadena=new String(); most=new TextArea(); dato=0;nodos=0; aux="R";fila=" ";columna="\n\n"; c.setBackground(Color.WHITE); }//end nuevo if(e.getSource()==creditos){ c.removeAll(); JLabel cred=new JLabel("ESTE PROGRAMA FUE DISEÑADO POR JUAN RICARDO COGOLLO OYOLA"); cred.setBounds(200,200,510,200); cred.setFont(new Font("EuropeExt", Font.BOLD + Font.ITALIC, 14)); cred.setForeground(Color.DARK_GRAY); c.setBackground(Color.white); c.add(cred); c.repaint(); } if(e.getSource()==salir){ System.exit(0); }//end salir }} public static void main(String[] args) { PruebaArbol ventana = new PruebaArbol("ARBOLES BINARIOS DE BUSQUEDA"); ventana.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } void pintar(int d,String h){ cadena=cadena+columna+fila+h+" : "+String.valueOf(d); most = new TextArea("",200,300,0); most.setBounds(20,200,700,500); most.append(cadena); most.setEditable(false); } void mostrarArbol(NodoArbol R,String hijo){ String h=hijo; if(R!=null){ pintar(R.retornadato(),h); if(R.li!=null){ aux="Izq"; fila=fila+" "; mostrarArbol(R.li,aux); int n=fila.length(); fila=fila.substring(10); } if(R.ld!=null){ aux="Der"; fila=fila+" "; mostrarArbol(R.ld,aux); int n=fila.length(); fila=fila.substring(10); } } }//end windows }