bueno me dejjaron de trabajo hacer el arbol b* donde se le ingresen los datos desde archivos de texto y que borre algunos numeros qe estan almacenados en otro archivo de texto y la verdad es que ya hice todo lo que es el arbol b* pero por alguna razon no borra los datos que le pido si pudiesen ayudarme se los agradeceria mucho
Código:
#include #include
#include
#include
using namespace std;
enum A_donde{VACIO,INICIO,MEDIO,FINAL};
enum B_encontrado{NO,SI};
enum Para_donde{izquierda,derecha};
class lista_ord;
/*
la ectructura caja es donde se almacenan cada uno de los digitos introducidos en
el Arbol B*
*/
struct caja{
caja *siguiente, *anterior;
float valor;
lista_ord *hijo_menor;
lista_ord *hijo_mayor;
int repetidos;
};
/*
la clase "lista ordenada" contiene cada una de las funciones
que se utilizan para el correcto ordenamiento de los digitos,
tal ordenamiento es de menor a mayor.
En donde la lista ordenada es doblemente ligada.
*/
class lista_ord{
caja *numero_repetido;
public:
int dos_tercios;
caja *padre_clave_izq, *padre_clave_der,*h_a_padre;
caja *principio, *anterior, *final;
lista_ord *lista_padre,*lista_siguiente,*lista_anterior;
B_encontrado encontrado;
A_donde donde;
caja *mitad;
int cuantos,orden;
lista_ord();
~lista_ord();
void buscar2(float);
lista_ord* buscar1(float);
int agregar(float,int);
int borrar(int);
void pintar(ofstream);
int cuantos1();
caja* mitad1();
void cal_dos_tercios(int n);
void vecino_dos_tercios();
void pintar2();
};
/*
"cal_dos_tercios" esta funcion calcula el dos tercios, en donde el parametro que
resive es orden del arbol, dicho calculo es guardado en una variable llamada
dos_tercios que se encuentra declarada como privada en la clase "lista_ord".
*/
void lista_ord::cal_dos_tercios(int orden){
float x;
int y;
x=(2.0/3)*(2*orden);
y=(int)x;
x=x-y;
if(x>.5){ dos_tercios=y+1;}
else {dos_tercios=y;}
}
/*
constructor de lista ordenado.
Aqui estan inicializadas cada una de
las varables de la lista.
*/
lista_ord::lista_ord(){
numero_repetido=NULL;
cuantos=0;
principio=NULL;
final=NULL;
anterior=NULL;
encontrado=NO;
donde=VACIO;
lista_padre=NULL;
padre_clave_izq=NULL;
padre_clave_der=NULL;
lista_siguiente=NULL;
lista_anterior=NULL;
h_a_padre=NULL;
}
/*
Buscar1 es el indicado de señalar si el numero a introducir ya
se encuantra en e arbol B* o en que lista de debe insertar.
dicho numero esta representado con la variable 'a' que es el parametro
que resive la función.
*/
lista_ord* lista_ord::buscar1(float a){
caja *p;
p=principio;
anterior=NULL;
if(p==NULL){
encontrado=NO;
donde=VACIO;
return(NULL);
}
while(p){
if(p->valor==a){
encontrado=SI;
return(this);
}
else{
if(p->valorhijo_menor==NULL){
return(this);
}else {
if(p->siguiente==NULL){ return(p->hijo_mayor);}
p=p->siguiente;
}
}else{ if(p->valor>a){
if(p->hijo_menor==NULL){
encontrado=NO;
return(this);
}else return(p->hijo_menor);
}} }
}
encontrado=NO;
donde=FINAL;
}
/*
buscar2:
Ella es la encargada de buscar el lugar en donde va el numero que se desea insertar ademas
de decirnos tambien si el número ya se encuentra en la lista o no.
Este buscar solo es llamado cuando se agrega.
*/
void lista_ord::buscar2(float a){
caja *p;
p=principio;
anterior=NULL;
encontrado=NO;
if(p==NULL){
encontrado=NO;
donde=VACIO;
return;
}
while(p){
if(p->valor==a){
encontrado=SI;
numero_repetido=p;
return;
}
else if(p->valorsiguiente;
}
else{
encontrado=NO;
if(anterior==NULL)donde=INICIO;
else donde=MEDIO;
return;
}
}
encontrado=NO;
donde=FINAL;
}
/*
agregar:
Esta funcion trabaja agregando cada uno de los numeros a la lista, asi como tambien
calcular la "mitad" si es la raiz o en otro caso el "h_a_padre".Estas son variables necesaria
para cada lista.
*/
int lista_ord::agregar(float a,int b){
caja *p;
buscar2(a);
if(encontrado==SI){
numero_repetido->repetidos++;
return(1);
}
p=new caja;
p->repetidos=1;
p->valor=a;
p->hijo_mayor=NULL;
p->hijo_menor=NULL;
if(donde==MEDIO){
p->siguiente=anterior->siguiente;
p->anterior=anterior;
anterior->siguiente=p;
(p->siguiente)->anterior=p;
if(b==SI){
if(cuantos%2!=0 && a>(mitad->valor)) mitad=mitad->siguiente;
if(cuantos%2==0 && a<=(mitad->valor)) mitad=mitad->anterior;
}else{
if(cuantos>(2*orden-dos_tercios) && p->valorvalor)h_a_padre=h_a_padre->anterior;
}
}
else if(donde==INICIO){
p->siguiente=principio;
p->anterior=NULL;
principio=p;
(p->siguiente)->anterior=p;
if(b==SI){
if(cuantos%2==0) mitad=mitad->anterior;
}else{
if(cuantos>(2*orden-dos_tercios))h_a_padre=h_a_padre->anterior;
}
}
else if(donde==FINAL){
p->siguiente=NULL;
p->anterior=final;
anterior->siguiente=p;
final=p;
if(b==SI){
if(cuantos%2!=0) mitad=mitad->siguiente;
}
}
else{
p->siguiente=NULL;
p->anterior=NULL;
principio=p;
final=p;
mitad=p;
}
if(b != SI){
if((2*orden-dos_tercios)==cuantos){
h_a_padre=final;
}
}
cuantos++;
return 0;
}
/*
pintar:
pinta cada uno de los elemntos de una lista
*/
void lista_ord::pintar(ofstream salida){
caja *p;
p=principio;
while(p){
salida<valor<<" ("<repetidos<<") "<siguiente;
}
}
void lista_ord::pintar2(){
caja *p;
p=principio;
while(p){
cout<valor<<" ("<repetidos<<") "<siguiente;
}
}
//destructor.
lista_ord::~lista_ord(){
caja *p;
p=principio;
while(p){
principio=p->siguiente;
delete p;
p=principio;
}
cuantos=0;
principio=NULL;
}
/*
vecino_dos_tercios:
el funcionamiento de esta funcion es decirle a la lista creada quien es su h_a_padre.
este metodo solamente entra cuando se crea una nueva lista en el arbol.
*/
void lista_ord::vecino_dos_tercios(){
int un_tercio;
un_tercio=(2*orden - dos_tercios);
int cont=0;
caja *p=principio;
while(p){
if(cont==un_tercio){
h_a_padre=p;
return;
}
cont++;
p=p->siguiente;
}
}
/*
ArbolB:
En ella encotraremos las funciones y variables que crean a nuestro arbol B*.
*/
class ArbolB{
//Cambio cambio;
lista_ord *raiz, *donde1,*lista;
float a1,b1;
B_encontrado encontrado,cambio;
Para_donde para_donde;
int capacidad,contador,repetido;
public:
ArbolB();
int d;
float caso_especial_con_raiz(float);
void recorrer2(lista_ord *lista1,lista_ord *lista2);
void agregar(float a);
void orden(int d);
void pintar();
void distribuir(lista_ord*);
void crear_vecinos(lista_ord *);
void separar(lista_ord *l);
float caso_especial(float);
lista_ord* buscar_vecino(lista_ord*);
void recorrer(lista_ord *,lista_ord* );
caja* pre_distribuir(lista_ord*);
lista_ord* buscar_espacio(lista_ord*);
lista_ord* buscar_vecino2(lista_ord*,int);
caja* buscar(float a);
void borrar(float a);
void lleno_dos_tercios(bool);
lista_ord* borrar_lista(lista_ord*,bool);
void disminuir_nivel();
void pre_disminuir_nivel();
void pintar2();
void leer_datos();
void datos_borrados();
};
/* orden():
el unico funcionamiento de esta funcion es
resivir como parametro el orden del arbol que el usiario decea,
para despues introducirlo en una variable llamada d, cual esta
representa en la clase el orden del arbol.
*/
void ArbolB::orden(int a){
d=a;
}
/*
pintar de arbolB:
su funcionamiento es pintar el arbol en un archivo.
*/
void ArbolB::pintar(){
lista_ord *lista,*padre,*inicio;
caja *p,*m;
ofstream salida;
salida.open("arbolb.txt");
if(raiz==NULL){
salida<<"NO hay datos "<mitad->valor<principio;
while(p){
salida<<"Padre : "<valor<hijo_menor){
lista=p->hijo_menor;
salida<<"final de hijo menores "<final->valor<valor<principio;
while(m){
salida<valor<<"("<repetidos<<")"<siguiente;
}
salida<<"principio de hijo menor"<principio->valor<h_a_padre!=NULL)
salida<<"H_A_PADRE: "<h_a_padre->valor<cuantos<padre_clave_izq!=NULL)
salida<<"padre clave izq: "<padre_clave_izq->valor<padre_clave_der!=NULL)
salida<<"padre clave der: "<padre_clave_der->valor<hijo_mayor){
lista=p->hijo_mayor;
salida<<"final de hijo mayores "<final->valor<valor<principio;
while(m){
salida<valor<<"("<repetidos<<")"<siguiente;
}
if(lista->principio!=NULL)
salida<<"principio de hijo mayor"<principio->valor<lista_padre->final->valor<h_a_padre!=NULL)
salida<<"H_A_PADRE: "<h_a_padre->valor<cuantos<padre_clave_izq!=NULL)
salida<<"padre clave izq: "<padre_clave_izq->valor<padre_clave_der!=NULL)
salida<<"padre clave der: "<padre_clave_der->valor<siguiente;
}salida<<"\n***********************************************************************"<lista_siguiente;
}
inicio=inicio->principio->hijo_menor;
padre=inicio;
}
salida<<"capacidad: "<lista_padre!=lista1->lista_padre){
aux=caja1->valor;
aux2=caja1->repetidos;
subir=lista1->lista_padre;
while(subir->padre_clave_der==NULL)
subir=subir->lista_padre;
caja1->valor=subir->padre_clave_der->valor;
caja1->repetidos=subir->padre_clave_der->repetidos;
subir->padre_clave_der->valor=aux;
subir->padre_clave_der->repetidos=aux2;
caja* caja2;
caja2=new caja;
caja2->valor=caja1->valor;
caja2->repetidos=caja1->repetidos;
caja2->hijo_menor=caja1->hijo_mayor;//se cambio de lugar
lista1=lista1->lista_padre->lista_siguiente->principio->hijo_menor;
if(lista2->lista_padre!=lista1->lista_padre){
caja1=pre_distribuir(lista1); }
else{
recorrer(lista1,lista2);}
caja2->siguiente=lista1->principio;
lista1->principio->anterior=caja2;
lista1->principio=caja2;
caja2->anterior=NULL;
lista1->cuantos++;
caja2->hijo_mayor=caja2->siguiente->hijo_menor;
//cambios*****************
if(caja2->hijo_menor){
caja2->hijo_menor->lista_padre=lista1;
caja2->hijo_menor->padre_clave_izq=NULL;
caja2->hijo_menor->padre_clave_der=caja2;
caja2->hijo_menor->lista_anterior->padre_clave_der=NULL;
caja2->siguiente->hijo_menor->padre_clave_izq=caja2;
}
if(lista1->cuantos==(2*d-lista1->dos_tercios)+1)
lista1->h_a_padre=lista1->final;
else if(lista1->cuantos > (2*d-lista1->dos_tercios)+1)
lista1->h_a_padre=lista1->h_a_padre->anterior;
}
free(caja1);
}else{
caja1=pre_distribuir(lista1);
while(lista2->lista_padre!=lista1->lista_padre){
aux=caja1->valor;
aux2=caja1->repetidos;
subir=lista1->lista_padre;
while(subir->padre_clave_izq==NULL)
subir=subir->lista_padre;
caja1->valor=subir->padre_clave_izq->valor;
caja1->repetidos=subir->padre_clave_izq->repetidos;
subir->padre_clave_izq->valor=aux;
subir->padre_clave_izq->repetidos=aux2;
caja* caja2;
caja2=new caja;
caja2->valor=caja1->valor;
caja2->repetidos=caja1->repetidos;
caja2->hijo_mayor=caja1->hijo_menor;//se cambio de lugar
lista1=lista1->lista_padre->lista_anterior->final->hijo_mayor;
if(lista2->lista_padre!=lista1->lista_padre){
caja1=pre_distribuir(lista1);}
else {recorrer(lista1,lista2);}
caja2->siguiente=NULL;
lista1->final->siguiente=caja2;
caja2->anterior=lista1->final;
lista1->final=caja2;
lista1->cuantos++;
caja2->hijo_menor=caja2->anterior->hijo_mayor;
//cambios
if(caja2->hijo_mayor){
caja2->hijo_mayor->lista_padre=lista1;
caja2->hijo_mayor->padre_clave_der=NULL;
caja2->hijo_mayor->padre_clave_izq=caja2;
caja2->hijo_mayor->lista_siguiente->padre_clave_izq=NULL;
caja2->anterior->hijo_mayor->padre_clave_der=caja2;
}
if(lista1->cuantos==(2*d-lista1->dos_tercios)+1)
lista1->h_a_padre=lista1->final;
}
free(caja1);
}
}
/*
pre_distribuir:
saca el ultimo o primer numero de la lista dejando un espacio, despues
se utiliza la funcion 'recorrer' para llenar el espacio donde
se extrajo la caja
*/
caja * ArbolB ::pre_distribuir(lista_ord * lista){
caja *ultimo;
lista_ord *lista2;
if(para_donde==derecha){
ultimo=lista->lista_padre->final->hijo_mayor->final;
lista2=lista->lista_padre->final->hijo_mayor;
lista2->final=lista2->final->anterior;
lista2->final->siguiente->anterior=NULL;
lista2->final->siguiente=NULL;
lista2->cuantos--;
if(lista2->cuantos < lista2->dos_tercios-1)lista2->h_a_padre=NULL;
recorrer(lista,lista2);
return ultimo;
}else{
ultimo=lista->lista_padre->principio->hijo_menor->principio;
lista2=lista->lista_padre->principio->hijo_menor;
lista2->principio=lista2->principio->siguiente;
lista2->principio->anterior->siguiente=NULL;
lista2->principio->anterior=NULL;
lista2->cuantos--;
if(lista2->h_a_padre!=NULL)
lista2->h_a_padre=lista2->h_a_padre->siguiente;
recorrer(lista,lista2);
return ultimo;
}
return NULL;
}
/*
buscar_espacio:
Se encarga de buscar espacio cuando hay padres vecinos.
*/
lista_ord* ArbolB::buscar_espacio(lista_ord *donde1){
lista_ord *inicio,*inicio2;
lista_ord *aux;
inicio=donde1->lista_padre;
while(inicio->lista_anterior)
inicio=inicio->lista_anterior;
while(inicio){
inicio2=inicio;
while(inicio2){
if(inicio2->principio->hijo_menor->cuantos < 2*d){
if(donde1->final->valor < inicio2->principio->hijo_menor->principio->valor) para_donde=derecha;
else para_donde=izquierda;
return(inicio2->principio->hijo_menor);
}
aux=buscar_vecino(inicio2->principio->hijo_menor);
if(aux==NULL && inicio2->cuantos==2*d){
inicio2=inicio2->lista_siguiente;
}else{
if(aux==NULL && inicio2->cuantos!=2*d){
crear_vecinos(inicio2);
distribuir(inicio2->final->hijo_mayor);
while(inicio->principio->hijo_menor)
inicio=inicio->principio->hijo_menor;
inicio=inicio->lista_padre;
inicio2=inicio;
}else if(aux!=NULL){
if(donde1->final->valor < aux->principio->valor) para_donde=derecha;
else para_donde=izquierda;
return aux;
}
}
}
inicio=inicio->lista_padre;
}
return NULL;
}
/*
distribuir:
este metodo distribuye uniformemete cada una de
las lista despues de crear un nuevo vecino.
*/
void ArbolB::distribuir(lista_ord *nuevo_vecino){
lista_ord *lista1,*lista2;
lista2=nuevo_vecino->lista_anterior;
lista1=nuevo_vecino->lista_padre->principio->hijo_menor;
para_donde=derecha;
while(true){
while(lista1!=lista2){
if(lista2->cuantos==nuevo_vecino->cuantos &&
(lista2->cuantos-lista2->lista_anterior->cuantos)!=-1){
recorrer(lista2,lista2->lista_siguiente);
}else{
if(((lista2->lista_anterior->cuantos-lista2->cuantos)==0 ||
(lista2->lista_anterior->cuantos-lista2->cuantos)==1) &&
((lista2->cuantos-nuevo_vecino->cuantos)==0 ||
(lista2->cuantos-nuevo_vecino->cuantos)==-1)){
cambio=SI;
return;
}
}
recorrer(lista1,lista2);
lista2=nuevo_vecino->lista_anterior;
lista1=lista1->lista_siguiente;
}
if(((lista2->lista_anterior->cuantos-lista2->cuantos)==0 ||
(lista2->lista_anterior->cuantos-lista2->cuantos)==1) &&
((lista2->cuantos-nuevo_vecino->cuantos)==0 ||
(lista2->cuantos-nuevo_vecino->cuantos)==-1)){
cambio=SI;
return;
}
lista1=nuevo_vecino->lista_padre->principio->hijo_menor;
}
}
float ArbolB::caso_especial_con_raiz(float a){
float aux;
int rep=1;
if(para_donde==derecha && donde1==donde1->lista_padre->final->hijo_mayor){
lista_ord *subir;
subir=donde1->lista_padre;
while(subir->padre_clave_der==NULL)
subir=subir->lista_padre;
if(subir->padre_clave_der->valor < a ){
aux=subir->padre_clave_der->valor;
if(subir->padre_clave_der->repetidos > 1) rep=subir->padre_clave_der->repetidos;
subir->padre_clave_der->valor=a;
subir->padre_clave_der->repetidos=1;
a=aux;
if(donde1->agregar(a,NO)==0)contador++;
donde1->final->repetidos=rep;
return 0.102101;
}
}else{
if(para_donde==izquierda && donde1==donde1->lista_padre->principio->hijo_menor){
lista_ord *subir;
subir=donde1->lista_padre;
while(subir->padre_clave_izq==NULL)
subir=subir->lista_padre;
if(subir->padre_clave_izq->valor > a ){
aux=subir->padre_clave_izq->valor;
if(subir->padre_clave_izq->repetidos > 1) rep=subir->padre_clave_izq->repetidos;
subir->padre_clave_izq->valor=a;
subir->padre_clave_izq->repetidos=1;
a=aux;
if(donde1->agregar(a,NO)==0)contador++;
donde1->principio->repetidos=rep;
return 0.102101;
}
}
}
return a;
}
void ArbolB::agregar(float a){
cambio=NO;
if(a==12)a1=a;
if(raiz==NULL){
lista_ord *lista;
lista=new lista_ord;
lista->orden=d;
donde1=lista;
if(donde1->agregar(a,SI)==0)contador++;
else repetido++;
raiz=lista;
capacidad=2*d;
}else{
raiz->encontrado=NO;
donde1=raiz;
while(donde1->principio->hijo_menor && donde1->encontrado==NO)
donde1=donde1->buscar1(a);
if(donde1->principio->hijo_menor==NULL)
donde1->buscar2(a);
if(capacidad==contador && donde1->encontrado==NO){
separar(raiz);
capacidad=(capacidad*(2*d+1))+2*d;
donde1=raiz;
while(donde1->principio->hijo_menor && donde1->encontrado==NO)
donde1=donde1->buscar1(a);
if(donde1->principio->hijo_menor==NULL)//modificacion nueva
donde1->buscar2(a);
}
if(donde1==raiz){
if(donde1->agregar(a,SI)==0)contador++;
else repetido++;
return;
}
float aux;
if(donde1->cuantos==2*d && donde1->encontrado==NO){
lista_ord *donde2;
donde2=buscar_vecino(donde1);
if(donde2!=NULL){
recorrer(donde1,donde2);
a=caso_especial(a);
if(a==0.102101f){
if(cambio==SI)lleno_dos_tercios(false);
return; }
}else{
if(donde2==NULL && donde1->lista_padre->cuantos<2*d){
crear_vecinos(donde1->lista_padre);
distribuir(donde1->lista_padre->final->hijo_mayor);
//lleno_dos_tercios();//cambios
if(donde1->cuantos==2*d) {
donde2=buscar_vecino(donde1);
recorrer(donde1,donde2);
}
}else{
donde2=buscar_espacio(donde1);
//buscar de nuevo
donde1=raiz;
while(donde1->principio->hijo_menor && donde1->encontrado==NO)
donde1=donde1->buscar1(a);
if(donde1->lista_padre==donde2->lista_padre){
if(donde1->cuantos==2*d){
donde2=buscar_vecino(donde1);
recorrer(donde1,donde2);
}
}else{
recorrer2(donde1,donde2);
a=caso_especial_con_raiz(a);
if(a==0.102101f){
if(cambio==SI)lleno_dos_tercios(false);
return;}
}
a=caso_especial(a);
if(a==0.102101f){
if(cambio==SI)lleno_dos_tercios(false);
return;}
if(donde1->agregar(a,NO)==0)contador++;
else repetido++;
if(cambio==SI)lleno_dos_tercios(false);
donde1=raiz;
return;
}
}
donde1=raiz;
while(donde1->principio->hijo_menor)
donde1=donde1->buscar1(a);
if(donde1->cuantos==2*d){
donde2=buscar_vecino(donde1);
recorrer(donde1,donde2);
}
if(donde1->agregar(a,NO)==0)contador++;
else repetido++;
if(cambio==SI)lleno_dos_tercios(false);
donde1=raiz;
return;
}
else{
if(donde1->agregar(a,NO)==0)contador++;
else repetido++;
if(cambio==SI)lleno_dos_tercios(false);
}donde1->encontrado=NO;
}
}
float ArbolB::caso_especial(float a){
float aux;
int rep=1;
if(para_donde==derecha && donde1->padre_clave_der!=NULL){
if(donde1->lista_siguiente->cuantos==2*d && donde1->lista_siguiente->principio->valor > a && donde1->padre_clave_der->valor < a ){
aux=donde1->padre_clave_der->valor;
if(donde1->padre_clave_der->repetidos > 1)
rep=donde1->padre_clave_der->repetidos;
donde1->padre_clave_der->valor=a;
donde1->padre_clave_der->repetidos=1;
a=aux;
if(donde1->agregar(a,NO)==0)contador++;
donde1->final->repetidos=rep;
return 0.102101;
}
}
if(para_donde==izquierda && donde1->padre_clave_izq!=NULL){
if(donde1->lista_anterior->cuantos == 2*d && donde1->lista_anterior->final->valor < a && donde1->padre_clave_izq->valor > a ){
aux=donde1->padre_clave_izq->valor;
if(donde1->padre_clave_izq->repetidos > 1)
rep=donde1->padre_clave_izq->repetidos;
donde1->padre_clave_izq->valor=a;
donde1->padre_clave_izq->repetidos=1;
a=aux;
if(donde1->agregar(a,NO)==0)contador++;
donde1->principio->repetidos=rep;
return 0.102101;
}
}return a;
}
lista_ord* ArbolB:: buscar_vecino(lista_ord* lista){
lista_ord *lista1;
lista1=lista;
while(lista1->lista_siguiente && lista1->padre_clave_der){
lista1=lista1->lista_siguiente;
if(lista1->cuantos < 2*d){
para_donde=derecha;
return lista1;
}
}
lista1=lista;
while(lista1->lista_anterior && lista1->padre_clave_izq){
lista1=lista1->lista_anterior;
if(lista1->cuantos < 2*d){
para_donde=izquierda;
return lista1;
}
}
return(NULL);
}
void ArbolB::crear_vecinos(lista_ord *padre){
lista_ord *nuevo_vecino,*aux;
caja *p;
nuevo_vecino=new lista_ord;
nuevo_vecino->orden=d;
nuevo_vecino->final=padre->final->hijo_mayor->final;
padre->final->hijo_mayor->h_a_padre->anterior->siguiente=NULL;
padre->final->siguiente=padre->final->hijo_mayor->h_a_padre;
padre->final->hijo_mayor->final=padre->final->hijo_mayor->h_a_padre->anterior;
padre->final->hijo_mayor->h_a_padre->anterior=padre->final;
padre->final=padre->final->siguiente;
padre->final->hijo_menor=padre->final->anterior->hijo_mayor;
padre->final->hijo_menor->padre_clave_der=padre->final;
if(padre->final->hijo_menor->lista_siguiente!=NULL){
aux=padre->final->hijo_menor->lista_siguiente;//
padre->final->hijo_menor->lista_siguiente->lista_anterior=nuevo_vecino;
nuevo_vecino->lista_siguiente=padre->final->hijo_menor->lista_siguiente;
}
padre->final->hijo_menor->lista_siguiente=nuevo_vecino;
nuevo_vecino->lista_anterior=padre->final->hijo_menor;
padre->final->hijo_mayor=nuevo_vecino;
nuevo_vecino->padre_clave_izq=padre->final;
nuevo_vecino->principio=padre->final->siguiente;
padre->final->siguiente=NULL;
nuevo_vecino->principio->anterior=NULL;
padre->final->hijo_menor->cuantos-=nuevo_vecino->lista_anterior->dos_tercios;
nuevo_vecino->cuantos=nuevo_vecino->lista_anterior->dos_tercios-1;
padre->cuantos++;
padre->final->hijo_menor->h_a_padre=NULL;
nuevo_vecino->dos_tercios=nuevo_vecino->lista_anterior->dos_tercios;
nuevo_vecino->vecino_dos_tercios();//nuevo h_a_padre
nuevo_vecino->lista_padre=nuevo_vecino->lista_anterior->lista_padre;
if(nuevo_vecino->principio->hijo_menor!=NULL){ //modifica los los padres de los hijos de nueva lista;
nuevo_vecino->principio->hijo_menor->padre_clave_izq=NULL;
p=nuevo_vecino->principio;
while(p){
p->hijo_menor->lista_padre=nuevo_vecino;
if(p==nuevo_vecino->final){
p->hijo_mayor->lista_padre=nuevo_vecino;
}
p=p->siguiente;
}
nuevo_vecino->lista_anterior->final->hijo_mayor->padre_clave_der=NULL;
}
if(padre==raiz) {
if(padre->cuantos%2==0) padre->mitad=padre->mitad->siguiente;
}else if(padre->cuantos==(2*d-padre->dos_tercios)+1) padre->h_a_padre=padre->final;
}
void ArbolB::recorrer(lista_ord *lista1,lista_ord *lista2){
lista_ord *padre,*aux;
padre=lista2->lista_padre;
if(para_donde==derecha){
while(lista2 != lista1){
lista2->principio->anterior=lista2->padre_clave_izq;
if(lista2->lista_padre->principio==lista2->lista_padre->final){
//caso donde siguiente y anterior son nulos derecha
lista1->final=lista1->final->anterior;
lista2->lista_padre->principio->siguiente=lista2->principio;
lista1->final->siguiente->anterior=NULL;
lista2->lista_padre->principio=lista1->final->siguiente;
lista2->principio=lista2->principio->anterior;
lista1->final->siguiente=NULL;
lista1->lista_padre->principio->hijo_menor=lista1;
aux=lista1->lista_padre->principio->hijo_mayor;//
lista1->lista_padre->principio->hijo_mayor=lista2;
lista2->principio->hijo_mayor=lista2->principio->siguiente->hijo_menor;//
lista2->principio->hijo_menor=aux;//
if(lista2->principio->hijo_menor!=NULL){//
lista2->principio->hijo_menor->lista_padre=lista2;//
lista2->principio->hijo_menor->padre_clave_izq=NULL;//
lista2->principio->hijo_menor->padre_clave_der=lista2->principio;//
lista2->principio->hijo_mayor->padre_clave_izq=lista2->principio;//
lista1->final->hijo_mayor->padre_clave_der=NULL;//
}//
lista1->padre_clave_der=lista1->lista_padre->principio;
lista2->padre_clave_izq=lista2->lista_padre->principio;
lista2->lista_padre->final=lista2->lista_padre->principio;
if(lista2->lista_padre==raiz){
raiz->mitad=raiz->principio;
}
lista2->cuantos++;
lista1->cuantos--;
if(lista2->cuantos==(2*d-lista2->dos_tercios)+1)
lista2->h_a_padre=lista2->final;
else if(lista2->cuantos > (2*d-lista2->dos_tercios)+1 && lista2->h_a_padre!=NULL)
lista2->h_a_padre=lista2->h_a_padre->anterior;
return;
}else{//en medio o final para la derecha
if(lista2->padre_clave_der!=NULL){
lista2->padre_clave_der->anterior=lista2->lista_anterior->final;
lista2->lista_anterior->final->siguiente=lista2->padre_clave_der;
}
lista2->principio->anterior->siguiente=lista2->principio;
lista2->principio=lista2->principio->anterior;
lista2->padre_clave_izq=lista2->lista_anterior->final;
lista2->lista_anterior->padre_clave_der=lista2->padre_clave_izq;
lista2->lista_anterior->final=lista2->lista_anterior->final->anterior;
lista2->lista_anterior->final->siguiente=NULL;
lista2->padre_clave_izq->hijo_menor=lista2->lista_anterior;
aux=lista2->padre_clave_izq->hijo_mayor;//
lista2->padre_clave_izq->hijo_mayor=lista2;
lista2->principio->hijo_menor=aux;//
lista2->principio->hijo_mayor=lista2->principio->siguiente->hijo_menor;//
if(lista2->principio->hijo_menor!=NULL){//
lista2->principio->hijo_menor->padre_clave_izq=NULL;//
lista2->principio->hijo_menor->padre_clave_der=lista2->principio;//
lista2->principio->hijo_menor->lista_padre=lista2;//
lista2->principio->hijo_mayor->padre_clave_izq=lista2->principio;//
lista2->lista_anterior->final->hijo_mayor->padre_clave_der=NULL; //
}//
lista2->cuantos++;
lista2->lista_anterior->cuantos--;
//***************
if(lista2->lista_anterior->padre_clave_izq==NULL){
padre->principio=lista2->padre_clave_izq;
padre->principio->anterior=NULL;
}else {
lista2->principio->anterior->siguiente=lista2->padre_clave_izq;
lista2->padre_clave_izq->anterior=lista2->principio->anterior;
lista2->principio->anterior=NULL;
if(lista2->padre_clave_der==NULL)
padre->final=lista2->padre_clave_izq;
} if(lista2->principio==raiz->mitad)
raiz->mitad=lista2->padre_clave_izq;
if(padre!=raiz&&padre->h_a_padre==lista2->principio)padre->h_a_padre=lista2->padre_clave_izq;
if(lista2->cuantos==(2*d-lista2->dos_tercios)+1) lista2->h_a_padre=lista2->final;//????
if(lista2->cuantos > (2*d-lista2->dos_tercios)+1 && lista2->h_a_padre!=NULL) lista2->h_a_padre=lista2->h_a_padre->anterior;/////////////////????
}
lista2=lista2->lista_anterior;
}
}else{
while(lista2 != lista1){
lista2->final->siguiente=lista2->padre_clave_der;
//caso donde siguiente y anterior son nulos izquierda
if(lista2->lista_padre->principio==lista2->lista_padre->final){
lista1->principio=lista1->principio->siguiente;
lista2->padre_clave_der->anterior=lista2->final;
lista1->principio->anterior->siguiente=NULL;
lista2->lista_padre->final=lista1->principio->anterior;
lista2->final=lista2->final->siguiente;
lista1->principio->anterior=NULL;
lista1->lista_padre->final->hijo_mayor=lista1;
aux=lista1->lista_padre->final->hijo_menor;
lista1->lista_padre->final->hijo_menor=lista2;
lista2->final->hijo_mayor=aux;
lista2->final->hijo_menor=lista2->final->anterior->hijo_mayor;
lista1->padre_clave_izq=lista1->lista_padre->final;
lista2->padre_clave_der=lista2->lista_padre->final;
lista2->lista_padre->principio=lista2->lista_padre->final;
if(lista2->final->hijo_mayor!=NULL){
lista2->final->hijo_mayor->padre_clave_izq=lista2->final;
lista2->final->hijo_mayor->padre_clave_der=NULL;
lista2->final->hijo_mayor->lista_padre=lista2;
lista2->final->hijo_menor->padre_clave_der=lista2->final;
lista1->principio->hijo_menor->padre_clave_izq=NULL;
}//
if(lista2->lista_padre==raiz)
lista2->lista_padre->mitad=lista2->lista_padre->principio;
lista2->cuantos++;
lista1->cuantos--;
if(lista2->cuantos==(2*d-lista2->dos_tercios)+1)
lista2->h_a_padre=lista2->final;
lista1->h_a_padre=lista1->h_a_padre->siguiente;
return;
}else{//caso medio y final de la izquierda
if(lista2->padre_clave_izq!=NULL){
lista2->padre_clave_izq->siguiente=lista2->lista_siguiente->principio;
lista2->lista_siguiente->principio->anterior=lista2->padre_clave_izq;
}
lista2->final->siguiente->anterior=lista2->final;
lista2->final=lista2->final->siguiente;
lista2->padre_clave_der=lista2->lista_siguiente->principio;
lista2->lista_siguiente->padre_clave_izq=lista2->padre_clave_der;
lista2->lista_siguiente->principio=lista2->lista_siguiente->principio->siguiente;
lista2->lista_siguiente->principio->anterior=NULL;
aux=lista2->padre_clave_der->hijo_menor;//
lista2->padre_clave_der->hijo_menor=lista2;
lista2->padre_clave_der->hijo_mayor=lista2->lista_siguiente;
lista2->final->hijo_menor=lista2->final->anterior->hijo_mayor;//
lista2->final->hijo_mayor=aux;
if(lista2->principio->hijo_menor!=NULL){//
lista2->final->hijo_mayor->padre_clave_izq=lista2->final;//
lista2->final->hijo_mayor->padre_clave_der=NULL;//
lista2->final->hijo_mayor->lista_padre=lista2;//
lista2->final->hijo_menor->padre_clave_der=lista2->final;//
lista2->lista_siguiente->principio->hijo_menor->padre_clave_izq=NULL;//
}
lista2->cuantos++;
lista2->lista_siguiente->cuantos--;
if(lista2->lista_siguiente->padre_clave_der==NULL){
padre->final=lista2->padre_clave_der;
padre->final->siguiente=NULL;
}else {
lista2->final->siguiente->anterior=lista2->padre_clave_der;
lista2->padre_clave_der->siguiente=lista2->final->siguiente;
lista2->final->siguiente=NULL;
if(lista2->padre_clave_izq==NULL)
lista2->lista_padre->principio=lista2->padre_clave_der;
}
if(lista2->final==raiz->mitad)
raiz->mitad=lista2->padre_clave_der;
if(padre!=raiz&&padre->h_a_padre==lista2->final)padre->h_a_padre=lista2->padre_clave_der;
if(lista2->lista_siguiente->h_a_padre!=NULL)
lista2->lista_siguiente->h_a_padre=lista2->lista_siguiente->h_a_padre->siguiente;
if(lista2->cuantos==(2*d-lista2->dos_tercios)+1)
lista2->h_a_padre=lista2->final;
}
lista2=lista2->lista_siguiente;
}return;
}
}
void ArbolB::separar(lista_ord *raiz1){
lista_ord *menores, *mayores;
caja *p;
menores=new lista_ord;
menores->orden=d;
mayores=new lista_ord;
mayores->orden=d;
menores->principio=raiz1->principio;
menores->final=raiz1->mitad->anterior;
menores->final->siguiente=NULL;
raiz1->principio=raiz1->mitad;
raiz1->mitad->anterior=NULL;
mayores->final=raiz1->final;
raiz1->final=raiz1->principio;
mayores->principio=raiz1->mitad->siguiente;
raiz->mitad->siguiente=NULL;
raiz1->principio->siguiente=NULL;
raiz1->final->siguiente=NULL;
if(mayores->principio!=NULL)
mayores->principio->anterior=NULL;
menores->lista_padre=raiz1;
mayores->lista_padre=raiz1;
raiz1->cuantos=1;
mayores->cuantos=d-1;
menores->cuantos=d;
raiz1->principio->hijo_menor=menores;
raiz1->principio->hijo_mayor=mayores;
menores->padre_clave_der=raiz1->principio;
menores->padre_clave_izq=NULL;
mayores->padre_clave_izq=raiz1->principio;
mayores->padre_clave_der=NULL;
menores->lista_siguiente=mayores;
menores->lista_anterior=NULL;
mayores->lista_siguiente=NULL;
mayores->lista_anterior=menores;
menores->cal_dos_tercios(d);
mayores->dos_tercios=menores->dos_tercios;
menores->vecino_dos_tercios();//calcula en h_a_padre
mayores->vecino_dos_tercios();//calcula en h_a_padre
if(menores->final->hijo_mayor!=NULL){
menores->final->hijo_mayor->padre_clave_der=NULL;
p=menores->principio;
while(p){
p->hijo_menor->lista_padre=menores;
if(p->siguiente==NULL)
p->hijo_mayor->lista_padre=menores;
p=p->siguiente;
}
}
if(mayores->final!=NULL && mayores->principio!=NULL ){
if(mayores->final->hijo_mayor!=NULL){
mayores->principio->hijo_menor->padre_clave_izq=NULL;
p=mayores->principio;
while(p){
p->hijo_menor->lista_padre=mayores;
if(p->siguiente==NULL)
p->hijo_mayor->lista_padre=mayores;
p=p->siguiente;
}
}
}
cambio=SI;
}
void ArbolB::lleno_dos_tercios(bool quien){
lista_ord *lista_menor, *lista_mayor, *parada, *inicio, *lleno;
lista_ord *vecino=NULL;
lista_menor=raiz->principio->hijo_menor;
inicio=lista_menor;
para_donde=derecha;
//el arbol debe quedar 2/3 lleno
while(inicio->principio->hijo_menor!=NULL){
while(lista_menor!=NULL){
lleno=lista_menor->principio->hijo_menor;
while(lista_menor->cuantos < lista_menor->dos_tercios ){
if(quien==true){
while(lista_menor->cuantos < lista_menor->dos_tercios ){
vecino=buscar_vecino2(lista_menor,lista_menor->dos_tercios);
if(vecino){
if(vecino->lista_padre==lista_menor->lista_padre)recorrer(vecino,lista_menor);
else {recorrer2(vecino,lista_menor); }
}else break;
} }
if(vecino==NULL){ para_donde=derecha;
if(lista_menor->final->hijo_mayor->cuantos!=2*d){
while(lista_menor->final->hijo_mayor->cuantos!=2*d && lista_menor->cuantos dos_tercios ){
while(lleno->cuantos< 2)lleno=lleno->lista_siguiente;
if(lleno->lista_padre==lista_menor){
recorrer(lleno,lista_menor->final->hijo_mayor);}
else recorrer2(lleno,lista_menor->final->hijo_mayor);
} if(lleno!=NULL)lleno=lista_menor->principio->hijo_menor;
}
crear_vecinos(lista_menor);
if(lista_menor->final->hijo_mayor->lista_anterior->cuantos < 2 && lista_menor->cuantos < lista_menor->dos_tercios)
recorrer(lista_menor->principio->hijo_menor,lista_menor->final->hijo_mayor->lista_anterior);
lleno=lista_menor->principio->hijo_menor;
while(lista_menor->final->hijo_mayor->cuantos!=2*d && lista_menor->cuantos dos_tercios ){
while(lleno->cuantos<2)lleno=lleno->lista_siguiente;
if(lleno->lista_padre==lista_menor)
recorrer(lleno,lista_menor->final->hijo_mayor);
else recorrer2(lleno,lista_menor->final->hijo_mayor);
} if(lleno!=NULL)lleno=lleno->lista_siguiente;
}
}
lista_menor=lista_menor->lista_siguiente;
}inicio=inicio->principio->hijo_menor;
lista_menor=inicio;
}
//se llenan las hojas al menos 2/3 -1
lista_ord* inicio2;
while(inicio){
while(inicio->cuantos < inicio->dos_tercios-1){
vecino=buscar_vecino2(inicio,inicio->dos_tercios-1);
if(vecino){
if(inicio->lista_padre == vecino->lista_padre) recorrer(vecino,inicio);
else recorrer2(vecino,inicio);
}else {inicio2=borrar_lista(inicio,false);inicio=inicio->lista_siguiente;free(inicio2);}
} inicio=inicio->lista_siguiente;
}
}
caja* ArbolB::buscar(float a){
encontrado=NO;
lista=raiz;
caja* cajita;
while(lista){
cajita=lista->principio;
while(cajita){
if(cajita->siguiente!=NULL){
if(a==cajita->valor){
encontrado=SI;
return(cajita);
}
if(a>cajita->valor && asiguiente->valor){
lista=cajita->hijo_mayor;
break;
}else if(a>cajita->valor){
cajita=cajita->siguiente;
}else if(avalor){
lista=cajita->hijo_menor;
break;
}
}else{
if(a==cajita->valor){
encontrado=SI;
return(cajita);
}
if(avalor){
lista=cajita->hijo_menor;
break;
}else if(a>cajita->valor){
lista=cajita->hijo_mayor;
break;
}
}
}
}
encontrado=NO;
cout<<"no encontro"<lista_siguiente;
lista_ord* lista2=lista3->lista_anterior;;
while(lista1!=NULL || lista2!=NULL){
if(lista1){
if(lista1->cuantos > var){
para_donde=izquierda;
return lista1;
}
lista1=lista1->lista_siguiente;
}
if(lista2){
if(lista2->cuantos > var){
para_donde=derecha;
return lista2;
}
lista2=lista2->lista_anterior;
}
}
return NULL;
}
void ArbolB::borrar(float a){
if(a==3283){a1=a;}
lista_ord *lista2,*lista3,*lista4;
caja *aux,*cajita;cajita=buscar(a);
lista2=NULL;
if(encontrado==SI){
if(cajita->repetidos>1){
cajita->repetidos--;
repetido--;
return;
}
if(lista->principio->hijo_menor!=NULL){
lista2=cajita->hijo_mayor;
while(lista2->principio->hijo_menor){ // profundisa
lista2=lista2->principio->hijo_menor;
}
if(lista2->cuantos > lista2->dos_tercios-1){
aux=lista2->principio;
lista2->principio=lista2->principio->siguiente;
lista2->principio->anterior=NULL;
lista2->h_a_padre=lista2->h_a_padre->siguiente;
lista2->cuantos--;
contador--;
}else if(lista2->lista_anterior->cuantos > lista2->dos_tercios-1){
lista2=lista2->lista_anterior;
aux=lista2->final;
lista2->final=lista2->final->anterior;
lista2->final->siguiente=NULL;
lista2->cuantos--;
contador--;
}else{ // no tiene suficientes claves lista2 oh la lista anterior
aux=lista2->principio;
lista2->principio=lista2->principio->siguiente;
lista2->principio->anterior=NULL;
lista2->cuantos--;
lista2->h_a_padre=NULL;
contador--;
}
cajita->valor=aux->valor;
cajita->repetidos=aux->repetidos;
free(aux);
if(lista2->cuantos >= lista2->dos_tercios-1)return;//
}else{//////no tiene hijos
if(lista==raiz && lista->cuantos==1 && cajita->repetidos==1){
free(cajita);
free(raiz);
raiz=NULL;
donde1=NULL;
capacidad=0;
contador=0;
repetido=0;
return;
}
if(lista->final==cajita){
lista->final=cajita->anterior;
cajita->anterior->siguiente=NULL;
if(lista==raiz){
if(lista->cuantos%2==0) lista->mitad=lista->mitad->anterior;
}else if(lista->h_a_padre==cajita){
lista->h_a_padre=NULL;
}
lista->cuantos--;
contador--;
free(cajita);
}else if(lista->principio==cajita){
lista->principio=cajita->siguiente;
lista->principio->anterior=NULL;
lista->cuantos--;
contador--;
if(lista!=raiz){
if(lista->cuantos < (2*d-lista->dos_tercios)+1)
lista->h_a_padre=NULL;
else if(lista->cuantos >= (2*d-lista->dos_tercios)+1)
lista->h_a_padre=lista->h_a_padre->siguiente;
}
else if(lista->cuantos%2==0) lista->mitad=lista->mitad->siguiente;
free(cajita);
}else{
if(lista!=raiz){
if(cajita->valor<=lista->h_a_padre->valor) lista->h_a_padre=lista->h_a_padre->siguiente;
}else {
if(lista->cuantos%2!=0 && a>(lista->mitad->valor)) lista->mitad=lista->mitad->siguiente; //
if(lista->cuantos%2==0 && a<=(lista->mitad->valor)) lista->mitad=lista->mitad->anterior; //
}
cajita->siguiente->anterior=cajita->anterior;
cajita->anterior->siguiente=cajita->siguiente;
lista->cuantos--;
contador--;
free(cajita);
}
}
if(lista2==NULL)
lista2=lista;
int var=lista2->dos_tercios-1;
while(lista2->cuantos< var && lista2!=raiz){
if(a==3283){pintar();system("pause"); }
//caso en el que se puede reducir otro nivel llenando la raiz a cuantos = 2*orden
if(raiz->cuantos==1 && ((raiz->principio->hijo_menor->cuantos)+(raiz->principio->hijo_mayor->cuantos)== 2*d -1)){
disminuir_nivel();
return;
}
lista3=buscar_vecino2(lista2,var);
if(lista3){
if(lista2->lista_padre==lista3->lista_padre){
recorrer(lista3,lista2);
}else{ //lleno_dos_tercios();
if(raiz->cuantos==1 && var==lista2->dos_tercios){
lleno_dos_tercios(true);
return;
}
recorrer2(lista3,lista2);
}
return ;
}else
{
if(raiz->cuantos==1&&lista2->lista_padre==raiz && var==lista2->dos_tercios){
if(((raiz->principio->hijo_menor->cuantos)+(raiz->principio->hijo_mayor->cuantos)==raiz->principio->hijo_menor->dos_tercios+raiz->principio->hijo_menor->dos_tercios-1)){
pre_disminuir_nivel();
if(raiz->cuantos==1 && ((raiz->principio->hijo_menor->cuantos)+(raiz->principio->hijo_mayor->cuantos)== 2*d -1))
disminuir_nivel();
} else lleno_dos_tercios(true);
return;
}
}
lista3=borrar_lista(lista2,false);
lista2=lista3->lista_padre;
//lleno_dos_tercios();
var=lista2->dos_tercios;
free (lista3);
}
}
cout<principio->hijo_menor->principio->hijo_menor,true);
free(lista_a_borrar);
lista_a_borrar=borrar_lista(raiz->principio->hijo_mayor->principio->hijo_menor,true);
free(lista_a_borrar);
}
//caso en el que se puede reducir otro nivel llenando la raiz a cuantos = 2*orden
void ArbolB::disminuir_nivel(){
caja *mitadauxiliar=NULL;
if(raiz->principio->hijo_menor->cuantos==d)mitadauxiliar=raiz->mitad;
raiz->principio->anterior=raiz->principio->hijo_menor->final;
raiz->principio->hijo_menor->final->siguiente=raiz->principio;
raiz->principio=raiz->principio->hijo_menor->principio;
free(raiz->mitad->hijo_menor);//
raiz->mitad->hijo_menor=raiz->mitad->anterior->hijo_mayor;
if(raiz->mitad->hijo_menor)
raiz->mitad->hijo_menor->padre_clave_der=raiz->mitad;
raiz->final->siguiente=raiz->final->hijo_mayor->principio;
raiz->final->hijo_mayor->principio->anterior=raiz->final;
raiz->final=raiz->final->hijo_mayor->final;
free(raiz->mitad->hijo_mayor);//
raiz->mitad->hijo_mayor=raiz->mitad->siguiente->hijo_menor;
if(raiz->mitad->hijo_mayor){
raiz->mitad->hijo_mayor->padre_clave_izq=raiz->mitad;
raiz->mitad->hijo_menor->lista_siguiente=raiz->mitad->hijo_mayor;
raiz->mitad->hijo_mayor->lista_anterior=raiz->mitad->hijo_menor;
}
raiz->cuantos=2*d;
if(mitadauxiliar==NULL)raiz->mitad=raiz->mitad->siguiente;
lista_ord *p;
p=raiz->principio->hijo_menor;
if(raiz->principio->hijo_menor){
while(p->padre_clave_der){
p->lista_padre=raiz;
p=p->lista_siguiente;
}p->lista_padre=raiz;
}
capacidad=(capacidad-2*d)/(2*d+1);
}
lista_ord * ArbolB::borrar_lista(lista_ord *lista2,bool entra){
lista_ord *lista3,*lista4,*lista_sig; bool caso_especial=false;
//no encontro en el mismo nivel un nodo que tubiera mas de 2/3
para_donde=derecha;
lista3=lista2->lista_padre->principio->hijo_menor;
lista4=lista3->lista_siguiente;
while(lista3->cuantos>1 ){
recorrer(lista3,lista4);
if(lista4->padre_clave_der!=NULL)
lista4=lista4->lista_siguiente;
}
if(lista2==lista3){
if(lista2->cuantos >1)
recorrer(lista3->lista_siguiente,lista3->lista_padre->final->hijo_mayor);
}else
recorrer(lista3->lista_siguiente,lista2);
if(lista2->lista_padre==raiz&&raiz->cuantos==lista2->dos_tercios-1 && lista3->principio->hijo_menor!=NULL){ //cambio*************
caso_especial=true;
lista_sig=lista3->lista_siguiente->principio->hijo_menor;
while(lista3->principio->hijo_menor->cuantos >1){
while(lista_sig->cuantos == 2*d)lista_sig=lista_sig->lista_siguiente;
recorrer2(lista3->principio->hijo_menor,lista_sig);
}
}
if(entra==true){
if(raiz->final->hijo_menor->final->hijo_mayor->cuantos==2*d && raiz->principio->hijo_menor->cuantos >= raiz->principio->hijo_menor->dos_tercios-1){
if(raiz->final->hijo_menor->cuantos < raiz->final->hijo_mayor->cuantos){ para_donde=derecha;
recorrer2(raiz->final->hijo_menor->final->hijo_mayor,raiz->principio->hijo_mayor->final->hijo_mayor);
}
}
else if(raiz->final->hijo_mayor->final->hijo_mayor->cuantos==2*d && raiz->principio->hijo_mayor->cuantos >= raiz->principio->hijo_menor->dos_tercios-1){
if(raiz->final->hijo_mayor->cuantos < raiz->final->hijo_menor->cuantos){ para_donde=izquierda;
if(raiz->final->hijo_mayor->principio->hijo_menor->cuantos!=2*d)
recorrer(raiz->final->hijo_mayor->final->hijo_mayor,raiz->final->hijo_mayor->principio->hijo_menor);
if(raiz->principio->hijo_menor->final->hijo_mayor->cuantos!=2*d)
recorrer2(raiz->final->hijo_mayor->principio->hijo_menor,raiz->principio->hijo_menor->final->hijo_mayor);
}
}
}
lista3->lista_siguiente->principio->anterior=lista3->lista_padre->principio;
lista3->lista_padre->principio=lista3->lista_padre->principio->siguiente;
lista3->lista_padre->principio->anterior->siguiente=lista3->lista_siguiente->principio;
lista3->lista_siguiente->principio=lista3->lista_siguiente->principio->anterior;
lista3->lista_padre->principio->anterior=NULL;
lista3->lista_padre->cuantos--;
lista3->lista_siguiente->cuantos++;
if(lista3->lista_padre==raiz){
if(lista3->lista_padre->cuantos%2==0)lista3->lista_padre->mitad=lista3->lista_padre->mitad->siguiente;
}else if(lista3->lista_padre->h_a_padre!=NULL) lista3->lista_padre->h_a_padre=lista3->lista_padre->h_a_padre->siguiente;
if(lista3->lista_siguiente->cuantos==(2*d-lista->dos_tercios)+1)//
lista3->lista_siguiente->h_a_padre=lista3->lista_siguiente->final; // //
else if(lista3->lista_siguiente->cuantos > (2*d-lista->dos_tercios)+1) //
lista3->lista_siguiente->h_a_padre=lista3->lista_siguiente->h_a_padre->anterior;//
/* if(lista3->lista_siguiente->h_a_padre!=NULL)
lista3->lista_siguiente->h_a_padre=lista3->lista_siguiente->h_a_padre->anterior; */
lista3->lista_siguiente->principio->hijo_menor=lista3->final->hijo_mayor;
lista3->lista_siguiente->principio->hijo_mayor=lista3->lista_siguiente->principio->siguiente->hijo_menor;
if(lista3->lista_siguiente->principio->hijo_menor){
lista3->lista_siguiente->principio->hijo_menor->padre_clave_der=lista3->lista_siguiente->principio;
lista3->lista_siguiente->principio->hijo_menor->padre_clave_izq=NULL;
lista3->lista_siguiente->principio->hijo_mayor->padre_clave_izq=lista3->lista_siguiente->principio;//
lista3->lista_siguiente->principio->hijo_menor->lista_padre=lista3->lista_siguiente;
}
lista3->lista_siguiente->padre_clave_izq=NULL;
if(caso_especial==true){
while(lista3->lista_siguiente->principio->hijo_menor->cuantos > 2){
while(lista_sig->cuantos==2*d)lista_sig=lista_sig->lista_siguiente;
if(lista_sig->lista_padre==lista3->lista_siguiente)
recorrer(lista3->lista_siguiente->principio->hijo_menor,lista_sig);
else recorrer2(lista3->lista_siguiente->principio->hijo_menor,lista_sig);
}
lista3->principio->anterior=lista3->principio->hijo_menor->final;
lista3->principio->hijo_menor->final->siguiente=lista3->principio;
lista3->principio->siguiente=lista3->lista_siguiente->principio->hijo_menor->principio;
lista3->principio->siguiente->anterior=lista3->principio;
lista3->lista_siguiente->principio->hijo_menor->principio=lista3->principio->anterior;
lista3->principio->hijo_mayor=lista3->principio->siguiente->hijo_menor;
lista3->principio->hijo_menor=lista3->principio->anterior->hijo_mayor;
if(lista3->principio->hijo_mayor){
lista3->principio->hijo_mayor->padre_clave_izq=lista3->principio;
lista3->principio->hijo_menor->padre_clave_der=lista3->principio;
lista3->principio->hijo_menor->lista_padre=lista3->lista_siguiente->principio->hijo_menor;
lista3->lista_siguiente->principio->hijo_menor->principio->hijo_menor->lista_padre=lista3->lista_siguiente->principio->hijo_menor;
}
lista3->lista_siguiente->principio->hijo_menor->cuantos+=2;
lista3->lista_siguiente->principio->hijo_menor->h_a_padre=lista3->principio;
free(lista3->lista_siguiente->principio->hijo_menor->lista_anterior);
lista3->lista_siguiente->principio->hijo_menor->lista_anterior=NULL;
lista3->lista_siguiente->lista_anterior=NULL;
return(lista3);
}
para_donde=derecha;
recorrer(lista3->lista_siguiente,lista4->lista_padre->final->hijo_mayor);
lista3->lista_siguiente->principio->anterior=lista3->principio;
lista3->lista_siguiente->principio->anterior->siguiente=lista3->lista_siguiente->principio;
lista3->lista_siguiente->principio=lista3->lista_siguiente->principio->anterior;
lista3->lista_siguiente->cuantos++;
if(lista3->lista_siguiente->cuantos==(2*d-lista->dos_tercios)+1)//
lista3->lista_siguiente->h_a_padre=lista3->lista_siguiente->final; //
else if(lista3->lista_siguiente->cuantos > (2*d-lista->dos_tercios)+1) //
lista3->lista_siguiente->h_a_padre=lista3->lista_siguiente->h_a_padre->anterior;//
lista3->lista_siguiente->principio->hijo_mayor=lista3->lista_siguiente->principio->siguiente->hijo_menor;
if(lista3->lista_siguiente->principio->hijo_menor!=NULL){
lista3->lista_siguiente->principio->hijo_menor->lista_padre=lista3->lista_siguiente;
lista3->lista_siguiente->principio->hijo_mayor->padre_clave_izq=lista3->lista_siguiente->principio;//
}
lista3->lista_siguiente->lista_anterior=lista3->lista_anterior;
if(lista3->lista_anterior!=NULL)
lista3->lista_anterior->lista_siguiente=lista3->lista_siguiente;
return(lista3);
}
void ArbolB::pintar2(){
lista_ord *lista;
caja *p;
lista=raiz;
ofstream salida;
salida.open("arbol.txt");
if(raiz==NULL){
salida<<"NO hay datos "<principio->hijo_menor==NULL){
p=lista->principio;
while(p){
salida<valor<<" ("<repetidos<<") "<siguiente;
}
salida.close();
return;
}
while(true){
while(lista->principio->hijo_menor)
lista=lista->principio->hijo_menor;
p=lista->principio;
while(p){
salida<valor<<" ("<repetidos<<") "<siguiente;
}
while(lista->padre_clave_der){
salida<padre_clave_der->valor<<" ("<padre_clave_der->repetidos<<")"<padre_clave_der->hijo_mayor;
p=lista->principio;
while(p){
salida<valor<<" ("<repetidos<<") "<siguiente;
}
}
while(lista->padre_clave_der==NULL){
if(lista->lista_padre==raiz && lista->padre_clave_izq==raiz->final){
return;
salida.close();
}
lista=lista->lista_padre;
}
salida<padre_clave_der->valor<<" ("<padre_clave_der->repetidos<<")"<padre_clave_der->hijo_mayor;
}
}
void ArbolB::leer_datos(){
int n=1;
char archivo[30];
float num;
ifstream entrada;
cout<<"Favor de proporcionar nombre del archivo: ";
cin.getline(archivo,30);
cout<>num;
cout<>num;
borrar(num);
}
entrada.close();
}
int main(){
int d=2;
ArbolB arbol;
arbol.orden(d);
cout<<"--------------------------------------Arbol B*----------------------------------"<
