Borro archivo de prueba que ya esta al gas supongo.

diff --git a/src/blocksorting/Btree.cpp b/src/blocksorting/Btree.cpp
deleted file mode 100644 (file)
index 027d84e..0000000
--- a/src/blocksorting/Btree.cpp
+++ /dev/null
@@ -1,389 +0,0 @@
-#include <iostream.h>\r
-#include <stdlib.h>\r
-\r
-#define TAMANO 1000\r
-\r
-struct stclave {\r
-   int valor;\r
-   long registro;\r
-};\r
-\r
-class bnodo {\r
-  public:\r
-   bnodo(int nClaves); // Constructor\r
-   ~bnodo();           // Destructor\r
- \r
-  private:\r
-   int clavesUsadas;   // Claves usadas en el nodo\r
-   stclave *clave;     // Array de claves del nodo\r
-   bnodo **puntero;    // Array de punteros a bnodo\r
-   bnodo *padre;       // Puntero a nodo padre\r
-\r
-  friend class btree;\r
-};\r
-\r
-typedef bnodo *pbnodo;\r
-\r
-bnodo::bnodo(int nClaves)\r
-{\r
-   clavesUsadas = 0;\r
-   clave = new stclave[nClaves];\r
-   puntero = new pbnodo[nClaves+1];\r
-   padre = NULL;\r
-}\r
-\r
-bnodo::~bnodo()\r
-{\r
-   delete[] clave;\r
-   delete[] puntero;\r
-}\r
-\r
-class btree {\r
-  public:\r
-   btree(int nClv);\r
-   ~btree();\r
-   long Buscar(int clave);\r
-   bool Insertar(stclave clave);\r
-   void Borrar(int clave);\r
-   void Mostrar();\r
-\r
-  private:\r
-   stclave *lista;\r
-   pbnodo *listapunt;\r
-   void Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2);\r
-   void BorrarClave(pbnodo nodo, int valor);\r
-   void BorrarNodo(pbnodo nodo);\r
-   void PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre);\r
-   void PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre);\r
-   void FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre);\r
-   void Ver(pbnodo nodo);\r
-   int nClaves, nodosMinimos;\r
-   pbnodo Entrada;\r
-};\r
-\r
-btree::btree(int nClv) : nClaves(nClv)\r
-{\r
-   lista = new stclave[nClaves+1];\r
-   listapunt = new pbnodo[nClaves+2];\r
-   nodosMinimos = nClaves/2; // ((nClaves+1)/2)-1;\r
-   Entrada = NULL;\r
-}\r
-\r
-btree::~btree()\r
-{\r
-   delete[] lista;\r
-   delete[] listapunt;\r
-   // Destruir árbol, algoritmo recursivo:\r
-   BorrarNodo(Entrada);\r
-}\r
-\r
-void btree::BorrarNodo(pbnodo nodo)\r
-{\r
-   int i;\r
-\r
-   if(!nodo) return;\r
-   for(i = 0; i <= nodo->clavesUsadas; i++) BorrarNodo(nodo->puntero[i]);\r
-   delete nodo;\r
-}\r
-\r
-void btree::Mostrar()\r
-{\r
-   cout << "arbol" << endl;\r
-   Ver(Entrada);\r
-   cout << "-----" << endl;\r
-}\r
-\r
-void btree::Ver(pbnodo nodo)\r
-{\r
-   int i;\r
-\r
-   if(!nodo) return;\r
-   for(i = 0; i < nodo->clavesUsadas-1; i++) cout << nodo->clave[i].valor << "-";\r
-   if(nodo->clavesUsadas) cout << nodo->clave[i].valor << " [";\r
-   if(nodo->padre) cout << (nodo->padre)->clave[0].valor; else cout << "*";\r
-   cout << "]" << endl;\r
-   for(i = 0; i <= nodo->clavesUsadas; i++) Ver(nodo->puntero[i]);\r
-}\r
-\r
-long btree::Buscar(int clave)\r
-{\r
-   pbnodo nodo = Entrada;\r
-   int i;\r
-\r
-   while(nodo) {\r
-      i = 0;\r
-      while(i < nodo->clavesUsadas && (nodo->clave[i].valor < clave)) i++;\r
-      if(nodo->clave[i].valor == clave) return nodo->clave[i].registro;\r
-      else nodo = nodo->puntero[i];\r
-   }\r
-   return -1L;\r
-}\r
-\r
-bool btree::Insertar(stclave clave)\r
-{\r
-   pbnodo nodo, padre;\r
-   int i;\r
-\r
-   // Asegurarse de que la clave no está en el árbol\r
-   padre = nodo = Entrada;\r
-   while(nodo) {\r
-      padre = nodo;\r
-      i = 0;\r
-      while(i < nodo->clavesUsadas && (nodo->clave[i].valor < clave.valor)) i++;\r
-      if(nodo->clave[i].valor == clave.valor && i < nodo->clavesUsadas) return false;\r
-      else nodo = nodo->puntero[i];\r
-   }\r
-   nodo = padre;\r
-   Inserta(clave, nodo, NULL, NULL);\r
-   return true;\r
-}\r
-\r
-void btree::Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2)\r
-{\r
-   pbnodo padre, nuevo;\r
-   int i, j;\r
-   bool salir = false;\r
-\r
-   // Insertar nueva clave en nodo:\r
-   do {\r
-      if(!nodo)\r
-      {\r
-         nodo = new bnodo(nClaves);\r
-         nodo->clavesUsadas = 0;\r
-         nodo->padre = NULL;\r
-         Entrada = nodo;\r
-      }\r
-      padre = nodo->padre;\r
-      if(nodo->clavesUsadas == nClaves) // overflow\r
-      {\r
-         // Nodo derecho\r
-         nuevo = new bnodo(nClaves);\r
-         // Construye lista ordenada:\r
-         i = 0;\r
-         while(nodo->clave[i].valor < clave.valor && i < nClaves) {\r
-            lista[i] = nodo->clave[i];\r
-            listapunt[i] = nodo->puntero[i];\r
-            i++;\r
-         }\r
-         lista[i] = clave;\r
-         listapunt[i] = hijo1;\r
-         listapunt[i+1] = hijo2;\r
-         while(i < nClaves) {\r
-            lista[i+1] = nodo->clave[i];\r
-            listapunt[i+2] = nodo->puntero[i+1];\r
-            i++;\r
-         }\r
-         // Dividir nodos:\r
-         // Nodo izquierdo:\r
-         nodo->clavesUsadas = nClaves/2;\r
-         for(j = 0; j < nodo->clavesUsadas; j++) {\r
-            nodo->clave[j] = lista[j];\r
-            nodo->puntero[j] = listapunt[j];\r
-         }\r
-         nodo->puntero[nodo->clavesUsadas] = listapunt[nodo->clavesUsadas];\r
-\r
-         // Nodo derecho:\r
-         nuevo->clavesUsadas = nClaves - nodo->clavesUsadas;\r
-         for(j = 0; j < nuevo->clavesUsadas; j++) {\r
-            nuevo->clave[j] = lista[j+(nClaves/2)+1];\r
-            nuevo->puntero[j] = listapunt[j+(nClaves/2)+1];\r
-         }\r
-         nuevo->puntero[nuevo->clavesUsadas] = listapunt[nClaves+1];\r
-\r
-         for(j = 0; j <= nodo->clavesUsadas; j++)\r
-            if(nodo->puntero[j]) (nodo->puntero[j])->padre = nodo;\r
-         for(j = 0; j <= nuevo->clavesUsadas; j++)\r
-            if(nuevo->puntero[j]) (nuevo->puntero[j])->padre = nuevo;\r
-\r
-         clave = lista[nClaves/2];\r
-         hijo1 = nodo;\r
-         hijo2 = nuevo;\r
-         nodo = padre;\r
-      }\r
-      else\r
-      {\r
-         // Inserta nueva clave en su lugar:\r
-         i = 0;\r
-         if(nodo->clavesUsadas > 0) {\r
-            while(nodo->clave[i].valor < clave.valor && i < nodo->clavesUsadas) i++;\r
-            for(j = nodo->clavesUsadas; j > i; j--)\r
-               nodo->clave[j] = nodo->clave[j-1];\r
-            for(j = nodo->clavesUsadas+1; j > i; j--)\r
-               nodo->puntero[j] = nodo->puntero[j-1];\r
-         }\r
-         nodo->clavesUsadas++;\r
-         nodo->clave[i] = clave;\r
-         nodo->puntero[i] = hijo1;\r
-         nodo->puntero[i+1] = hijo2;\r
-         if(hijo1) hijo1->padre = nodo;\r
-         if(hijo2) hijo2->padre = nodo;\r
-         salir = true;\r
-      }\r
-   } while(!salir);\r
-}\r
-\r
-void btree::Borrar(int valor)\r
-{\r
-   pbnodo nodo;\r
-   bool encontrado = false;\r
-   int i;\r
-\r
-   // Busca el nodo que contiene la clave, si existe\r
-   nodo = Entrada;\r
-   while(nodo && !encontrado) {\r
-      i = 0;\r
-      while(i < nodo->clavesUsadas && (nodo->clave[i].valor < valor)) i++;\r
-      if(nodo->clave[i].valor == valor && i < nodo->clavesUsadas) encontrado = true;\r
-      else nodo = nodo->puntero[i];\r
-   }\r
-   if(encontrado) BorrarClave(nodo, valor);\r
-}\r
-\r
-void btree::BorrarClave(pbnodo nodo, int valor)\r
-{\r
-   pbnodo actual, derecha, izquierda, padre;\r
-   int posClavePadre, pos, i;\r
-\r
-   // Buscar posición dentro de lista de claves:\r
-   pos = 0;\r
-   while(nodo->clave[pos].valor < valor) pos++;\r
-\r
-   // ¿Está la clave en un nodo hoja?\r
-   if(nodo->puntero[0]) { // No, se trata de un nodo intermedio\r
-      // Buscar actual del valor siguiente:\r
-      actual = nodo->puntero[pos+1];\r
-      while(actual->puntero[0]) actual = actual->puntero[0];\r
-      // Intercambiar con el valor siguiente:\r
-      nodo->clave[pos] = actual->clave[0];\r
-      // La posición de la clave a borrar en ahora la 0:\r
-      pos = 0;\r
-   } else actual = nodo;\r
-\r
-   // Borrar clave\r
-   for(i = pos; i < actual->clavesUsadas; i++)\r
-      actual->clave[i] = actual->clave[i+1];\r
-   actual->clavesUsadas--;\r
-\r
-   if(actual == Entrada && actual->clavesUsadas == 0) {\r
-      delete actual;\r
-      Entrada = NULL;\r
-      return;\r
-   }\r
-\r
-   // ¿Es el número de claves mayor que el mínimo para el nodo?\r
-   if(actual == Entrada || actual->clavesUsadas >= nodosMinimos) return;\r
-\r
-   do {\r
-      // El número de claves es menor que el mínimo:\r
-      // Buscar nodos a derecha e izquierda:\r
-      padre = actual->padre;\r
-      for(posClavePadre = 0;\r
-         padre->puntero[posClavePadre] != actual;\r
-         posClavePadre++);\r
-      if(posClavePadre > 0)\r
-         izquierda = padre->puntero[posClavePadre-1];\r
-      else izquierda = NULL;\r
-      if(posClavePadre < padre->clavesUsadas)\r
-         derecha = padre->puntero[posClavePadre+1];\r
-      else derecha = NULL;\r
-\r
-      // Intentar pasar una clave de un nodo cercano:\r
-      if(derecha && derecha->clavesUsadas > nodosMinimos)\r
-         PasarClaveDerecha(derecha, padre, actual, posClavePadre);\r
-      else if(izquierda && izquierda->clavesUsadas > nodosMinimos)\r
-         PasarClaveIzquierda(izquierda, padre, actual, posClavePadre-1);\r
-      // Si no fue posible, fundir con un nodo cercano y una clave de padre:\r
-      else if(derecha) // Usar nodo derecho\r
-         FundirNodo(actual, padre, derecha, posClavePadre);\r
-      else             // Usar el nodo izquierdo\r
-         FundirNodo(izquierda, padre, actual, posClavePadre-1);\r
-      // Vuelta a empezar:\r
-      actual = padre;\r
-   } while(actual && actual != Entrada && actual->clavesUsadas < nodosMinimos);\r
-}\r
-\r
-void btree::PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre)\r
-{\r
-   int i;\r
-\r
-   nodo->clave[nodo->clavesUsadas] = padre->clave[posClavePadre];\r
-   nodo->clavesUsadas++;\r
-   padre->clave[posClavePadre] = derecha->clave[0];\r
-   nodo->puntero[nodo->clavesUsadas] = derecha->puntero[0];\r
-   if(derecha->puntero[0]) derecha->puntero[0]->padre = nodo;\r
-   for(i = 0; i < derecha->clavesUsadas; i++) derecha->clave[i] = derecha->clave[i+1];\r
-   for(i = 0; i <= derecha->clavesUsadas; i++) derecha->puntero[i] = derecha->puntero[i+1];\r
-   derecha->clavesUsadas--;\r
-}\r
-\r
-void btree::PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre)\r
-{\r
-   int i;\r
-\r
-   for(i = nodo->clavesUsadas; i > 0; i--) nodo->clave[i] = nodo->clave[i-1];\r
-   for(i = nodo->clavesUsadas+1; i > 0; i--) nodo->puntero[i] = nodo->puntero[i-1];\r
-   nodo->clavesUsadas++;\r
-   nodo->clave[0] = padre->clave[posClavePadre];\r
-   padre->clave[posClavePadre] = izquierda->clave[izquierda->clavesUsadas-1];\r
-   nodo->puntero[0] = izquierda->puntero[izquierda->clavesUsadas];\r
-   if(nodo->puntero[0]) nodo->puntero[0]->padre = nodo;\r
-   izquierda->clavesUsadas--;\r
-}\r
-\r
-void btree::FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre)\r
-{\r
-   int i;\r
-\r
-   izquierda->clave[izquierda->clavesUsadas] = padre->clave[posClavePadre];\r
-   padre->clavesUsadas--;\r
-   for(i = posClavePadre; i < padre->clavesUsadas; i++) {\r
-      padre->clave[i] = padre->clave[i+1];\r
-      padre->puntero[i+1] = padre->puntero[i+2];\r
-   }\r
-   izquierda->clavesUsadas++;\r
-   for(i = 0; i < derecha->clavesUsadas; i++)\r
-      izquierda->clave[izquierda->clavesUsadas+i] = derecha->clave[i];\r
-   for(i = 0; i <= derecha->clavesUsadas; i++) {\r
-      izquierda->puntero[izquierda->clavesUsadas+i] = derecha->puntero[i];\r
-      if(derecha->puntero[i]) derecha->puntero[i]->padre = izquierda;\r
-   }\r
-   izquierda->clavesUsadas += derecha->clavesUsadas;\r
-   if(padre == Entrada && padre->clavesUsadas == 0) { // Cambio de entrada\r
-      Entrada = izquierda;\r
-      Entrada->padre = NULL;\r
-      delete padre;\r
-      padre = NULL;\r
-   }\r
-   delete derecha;\r
-}\r
-\r
-int main()\r
-{\r
-   int matriz[TAMANO];\r
-   btree arbol(500);\r
-   stclave clave;\r
-   int i;\r
-
-//   srand(time(NULL));
-   for(i = 0; i < TAMANO; i++) {
-      do {
-         matriz[i] = rand()%10000;
-         clave.valor = matriz[i];
-         clave.registro = i;
-      } while(!arbol.Insertar(clave));
-   }
-
-   cout << "mostrar: " << endl;
-   arbol.Mostrar();
-
-   cout << "Buscar elemento 23: " << matriz[23] << " posicion: " <<\r
-     arbol.Buscar(matriz[23]) << endl;\r
-
-   for(i = 0; i < TAMANO; i++) {\r
-      cout << "Borrar: [" << i << "]: " << matriz[i] << endl;\r
-      arbol.Borrar(matriz[i]);\r
-//      arbol.Mostrar();\r
-   }\r
-   arbol.Mostrar();\r
-   return 0;\r
-}\r