src/blocksorting/Btree.cpp

   1 #include <iostream.h>\r
   2 #include <stdlib.h>\r
   3 \r
   4 #define TAMANO 1000\r
   5 \r
   6 struct stclave {\r
   7    int valor;\r
   8    long registro;\r
   9 };\r
  10 \r
  11 class bnodo {\r
  12   public:\r
  13    bnodo(int nClaves); // Constructor\r
  14    ~bnodo();           // Destructor\r
  15  \r
  16   private:\r
  17    int clavesUsadas;   // Claves usadas en el nodo\r
  18    stclave *clave;     // Array de claves del nodo\r
  19    bnodo **puntero;    // Array de punteros a bnodo\r
  20    bnodo *padre;       // Puntero a nodo padre\r
  21 \r
  22   friend class btree;\r
  23 };\r
  24 \r
  25 typedef bnodo *pbnodo;\r
  26 \r
  27 bnodo::bnodo(int nClaves)\r
  28 {\r
  29    clavesUsadas = 0;\r
  30    clave = new stclave[nClaves];\r
  31    puntero = new pbnodo[nClaves+1];\r
  32    padre = NULL;\r
  33 }\r
  34 \r
  35 bnodo::~bnodo()\r
  36 {\r
  37    delete[] clave;\r
  38    delete[] puntero;\r
  39 }\r
  40 \r
  41 class btree {\r
  42   public:\r
  43    btree(int nClv);\r
  44    ~btree();\r
  45    long Buscar(int clave);\r
  46    bool Insertar(stclave clave);\r
  47    void Borrar(int clave);\r
  48    void Mostrar();\r
  49 \r
  50   private:\r
  51    stclave *lista;\r
  52    pbnodo *listapunt;\r
  53    void Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2);\r
  54    void BorrarClave(pbnodo nodo, int valor);\r
  55    void BorrarNodo(pbnodo nodo);\r
  56    void PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre);\r
  57    void PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre);\r
  58    void FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre);\r
  59    void Ver(pbnodo nodo);\r
  60    int nClaves, nodosMinimos;\r
  61    pbnodo Entrada;\r
  62 };\r
  63 \r
  64 btree::btree(int nClv) : nClaves(nClv)\r
  65 {\r
  66    lista = new stclave[nClaves+1];\r
  67    listapunt = new pbnodo[nClaves+2];\r
  68    nodosMinimos = nClaves/2; // ((nClaves+1)/2)-1;\r
  69    Entrada = NULL;\r
  70 }\r
  71 \r
  72 btree::~btree()\r
  73 {\r
  74    delete[] lista;\r
  75    delete[] listapunt;\r
  76    // Destruir árbol, algoritmo recursivo:\r
  77    BorrarNodo(Entrada);\r
  78 }\r
  79 \r
  80 void btree::BorrarNodo(pbnodo nodo)\r
  81 {\r
  82    int i;\r
  83 \r
  84    if(!nodo) return;\r
  85    for(i = 0; i <= nodo->clavesUsadas; i++) BorrarNodo(nodo->puntero[i]);\r
  86    delete nodo;\r
  87 }\r
  88 \r
  89 void btree::Mostrar()\r
  90 {\r
  91    cout << "arbol" << endl;\r
  92    Ver(Entrada);\r
  93    cout << "-----" << endl;\r
  94 }\r
  95 \r
  96 void btree::Ver(pbnodo nodo)\r
  97 {\r
  98    int i;\r
  99 \r
 100    if(!nodo) return;\r
 101    for(i = 0; i < nodo->clavesUsadas-1; i++) cout << nodo->clave[i].valor << "-";\r
 102    if(nodo->clavesUsadas) cout << nodo->clave[i].valor << " [";\r
 103    if(nodo->padre) cout << (nodo->padre)->clave[0].valor; else cout << "*";\r
 104    cout << "]" << endl;\r
 105    for(i = 0; i <= nodo->clavesUsadas; i++) Ver(nodo->puntero[i]);\r
 106 }\r
 107 \r
 108 long btree::Buscar(int clave)\r
 109 {\r
 110    pbnodo nodo = Entrada;\r
 111    int i;\r
 112 \r
 113    while(nodo) {\r
 114       i = 0;\r
 115       while(i < nodo->clavesUsadas && (nodo->clave[i].valor < clave)) i++;\r
 116       if(nodo->clave[i].valor == clave) return nodo->clave[i].registro;\r
 117       else nodo = nodo->puntero[i];\r
 118    }\r
 119    return -1L;\r
 120 }\r
 121 \r
 122 bool btree::Insertar(stclave clave)\r
 123 {\r
 124    pbnodo nodo, padre;\r
 125    int i;\r
 126 \r
 127    // Asegurarse de que la clave no está en el árbol\r
 128    padre = nodo = Entrada;\r
 129    while(nodo) {\r
 130       padre = nodo;\r
 131       i = 0;\r
 132       while(i < nodo->clavesUsadas && (nodo->clave[i].valor < clave.valor)) i++;\r
 133       if(nodo->clave[i].valor == clave.valor && i < nodo->clavesUsadas) return false;\r
 134       else nodo = nodo->puntero[i];\r
 135    }\r
 136    nodo = padre;\r
 137    Inserta(clave, nodo, NULL, NULL);\r
 138    return true;\r
 139 }\r
 140 \r
 141 void btree::Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2)\r
 142 {\r
 143    pbnodo padre, nuevo;\r
 144    int i, j;\r
 145    bool salir = false;\r
 146 \r
 147    // Insertar nueva clave en nodo:\r
 148    do {\r
 149       if(!nodo)\r
 150       {\r
 151          nodo = new bnodo(nClaves);\r
 152          nodo->clavesUsadas = 0;\r
 153          nodo->padre = NULL;\r
 154          Entrada = nodo;\r
 155       }\r
 156       padre = nodo->padre;\r
 157       if(nodo->clavesUsadas == nClaves) // overflow\r
 158       {\r
 159          // Nodo derecho\r
 160          nuevo = new bnodo(nClaves);\r
 161          // Construye lista ordenada:\r
 162          i = 0;\r
 163          while(nodo->clave[i].valor < clave.valor && i < nClaves) {\r
 164             lista[i] = nodo->clave[i];\r
 165             listapunt[i] = nodo->puntero[i];\r
 166             i++;\r
 167          }\r
 168          lista[i] = clave;\r
 169          listapunt[i] = hijo1;\r
 170          listapunt[i+1] = hijo2;\r
 171          while(i < nClaves) {\r
 172             lista[i+1] = nodo->clave[i];\r
 173             listapunt[i+2] = nodo->puntero[i+1];\r
 174             i++;\r
 175          }\r
 176          // Dividir nodos:\r
 177          // Nodo izquierdo:\r
 178          nodo->clavesUsadas = nClaves/2;\r
 179          for(j = 0; j < nodo->clavesUsadas; j++) {\r
 180             nodo->clave[j] = lista[j];\r
 181             nodo->puntero[j] = listapunt[j];\r
 182          }\r
 183          nodo->puntero[nodo->clavesUsadas] = listapunt[nodo->clavesUsadas];\r
 184 \r
 185          // Nodo derecho:\r
 186          nuevo->clavesUsadas = nClaves - nodo->clavesUsadas;\r
 187          for(j = 0; j < nuevo->clavesUsadas; j++) {\r
 188             nuevo->clave[j] = lista[j+(nClaves/2)+1];\r
 189             nuevo->puntero[j] = listapunt[j+(nClaves/2)+1];\r
 190          }\r
 191          nuevo->puntero[nuevo->clavesUsadas] = listapunt[nClaves+1];\r
 192 \r
 193          for(j = 0; j <= nodo->clavesUsadas; j++)\r
 194             if(nodo->puntero[j]) (nodo->puntero[j])->padre = nodo;\r
 195          for(j = 0; j <= nuevo->clavesUsadas; j++)\r
 196             if(nuevo->puntero[j]) (nuevo->puntero[j])->padre = nuevo;\r
 197 \r
 198          clave = lista[nClaves/2];\r
 199          hijo1 = nodo;\r
 200          hijo2 = nuevo;\r
 201          nodo = padre;\r
 202       }\r
 203       else\r
 204       {\r
 205          // Inserta nueva clave en su lugar:\r
 206          i = 0;\r
 207          if(nodo->clavesUsadas > 0) {\r
 208             while(nodo->clave[i].valor < clave.valor && i < nodo->clavesUsadas) i++;\r
 209             for(j = nodo->clavesUsadas; j > i; j--)\r
 210                nodo->clave[j] = nodo->clave[j-1];\r
 211             for(j = nodo->clavesUsadas+1; j > i; j--)\r
 212                nodo->puntero[j] = nodo->puntero[j-1];\r
 213          }\r
 214          nodo->clavesUsadas++;\r
 215          nodo->clave[i] = clave;\r
 216          nodo->puntero[i] = hijo1;\r
 217          nodo->puntero[i+1] = hijo2;\r
 218          if(hijo1) hijo1->padre = nodo;\r
 219          if(hijo2) hijo2->padre = nodo;\r
 220          salir = true;\r
 221       }\r
 222    } while(!salir);\r
 223 }\r
 224 \r
 225 void btree::Borrar(int valor)\r
 226 {\r
 227    pbnodo nodo;\r
 228    bool encontrado = false;\r
 229    int i;\r
 230 \r
 231    // Busca el nodo que contiene la clave, si existe\r
 232    nodo = Entrada;\r
 233    while(nodo && !encontrado) {\r
 234       i = 0;\r
 235       while(i < nodo->clavesUsadas && (nodo->clave[i].valor < valor)) i++;\r
 236       if(nodo->clave[i].valor == valor && i < nodo->clavesUsadas) encontrado = true;\r
 237       else nodo = nodo->puntero[i];\r
 238    }\r
 239    if(encontrado) BorrarClave(nodo, valor);\r
 240 }\r
 241 \r
 242 void btree::BorrarClave(pbnodo nodo, int valor)\r
 243 {\r
 244    pbnodo actual, derecha, izquierda, padre;\r
 245    int posClavePadre, pos, i;\r
 246 \r
 247    // Buscar posición dentro de lista de claves:\r
 248    pos = 0;\r
 249    while(nodo->clave[pos].valor < valor) pos++;\r
 250 \r
 251    // ¿Está la clave en un nodo hoja?\r
 252    if(nodo->puntero[0]) { // No, se trata de un nodo intermedio\r
 253       // Buscar actual del valor siguiente:\r
 254       actual = nodo->puntero[pos+1];\r
 255       while(actual->puntero[0]) actual = actual->puntero[0];\r
 256       // Intercambiar con el valor siguiente:\r
 257       nodo->clave[pos] = actual->clave[0];\r
 258       // La posición de la clave a borrar en ahora la 0:\r
 259       pos = 0;\r
 260    } else actual = nodo;\r
 261 \r
 262    // Borrar clave\r
 263    for(i = pos; i < actual->clavesUsadas; i++)\r
 264       actual->clave[i] = actual->clave[i+1];\r
 265    actual->clavesUsadas--;\r
 266 \r
 267    if(actual == Entrada && actual->clavesUsadas == 0) {\r
 268       delete actual;\r
 269       Entrada = NULL;\r
 270       return;\r
 271    }\r
 272 \r
 273    // ¿Es el número de claves mayor que el mínimo para el nodo?\r
 274    if(actual == Entrada || actual->clavesUsadas >= nodosMinimos) return;\r
 275 \r
 276    do {\r
 277       // El número de claves es menor que el mínimo:\r
 278       // Buscar nodos a derecha e izquierda:\r
 279       padre = actual->padre;\r
 280       for(posClavePadre = 0;\r
 281          padre->puntero[posClavePadre] != actual;\r
 282          posClavePadre++);\r
 283       if(posClavePadre > 0)\r
 284          izquierda = padre->puntero[posClavePadre-1];\r
 285       else izquierda = NULL;\r
 286       if(posClavePadre < padre->clavesUsadas)\r
 287          derecha = padre->puntero[posClavePadre+1];\r
 288       else derecha = NULL;\r
 289 \r
 290       // Intentar pasar una clave de un nodo cercano:\r
 291       if(derecha && derecha->clavesUsadas > nodosMinimos)\r
 292          PasarClaveDerecha(derecha, padre, actual, posClavePadre);\r
 293       else if(izquierda && izquierda->clavesUsadas > nodosMinimos)\r
 294          PasarClaveIzquierda(izquierda, padre, actual, posClavePadre-1);\r
 295       // Si no fue posible, fundir con un nodo cercano y una clave de padre:\r
 296       else if(derecha) // Usar nodo derecho\r
 297          FundirNodo(actual, padre, derecha, posClavePadre);\r
 298       else             // Usar el nodo izquierdo\r
 299          FundirNodo(izquierda, padre, actual, posClavePadre-1);\r
 300       // Vuelta a empezar:\r
 301       actual = padre;\r
 302    } while(actual && actual != Entrada && actual->clavesUsadas < nodosMinimos);\r
 303 }\r
 304 \r
 305 void btree::PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre)\r
 306 {\r
 307    int i;\r
 308 \r
 309    nodo->clave[nodo->clavesUsadas] = padre->clave[posClavePadre];\r
 310    nodo->clavesUsadas++;\r
 311    padre->clave[posClavePadre] = derecha->clave[0];\r
 312    nodo->puntero[nodo->clavesUsadas] = derecha->puntero[0];\r
 313    if(derecha->puntero[0]) derecha->puntero[0]->padre = nodo;\r
 314    for(i = 0; i < derecha->clavesUsadas; i++) derecha->clave[i] = derecha->clave[i+1];\r
 315    for(i = 0; i <= derecha->clavesUsadas; i++) derecha->puntero[i] = derecha->puntero[i+1];\r
 316    derecha->clavesUsadas--;\r
 317 }\r
 318 \r
 319 void btree::PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre)\r
 320 {\r
 321    int i;\r
 322 \r
 323    for(i = nodo->clavesUsadas; i > 0; i--) nodo->clave[i] = nodo->clave[i-1];\r
 324    for(i = nodo->clavesUsadas+1; i > 0; i--) nodo->puntero[i] = nodo->puntero[i-1];\r
 325    nodo->clavesUsadas++;\r
 326    nodo->clave[0] = padre->clave[posClavePadre];\r
 327    padre->clave[posClavePadre] = izquierda->clave[izquierda->clavesUsadas-1];\r
 328    nodo->puntero[0] = izquierda->puntero[izquierda->clavesUsadas];\r
 329    if(nodo->puntero[0]) nodo->puntero[0]->padre = nodo;\r
 330    izquierda->clavesUsadas--;\r
 331 }\r
 332 \r
 333 void btree::FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre)\r
 334 {\r
 335    int i;\r
 336 \r
 337    izquierda->clave[izquierda->clavesUsadas] = padre->clave[posClavePadre];\r
 338    padre->clavesUsadas--;\r
 339    for(i = posClavePadre; i < padre->clavesUsadas; i++) {\r
 340       padre->clave[i] = padre->clave[i+1];\r
 341       padre->puntero[i+1] = padre->puntero[i+2];\r
 342    }\r
 343    izquierda->clavesUsadas++;\r
 344    for(i = 0; i < derecha->clavesUsadas; i++)\r
 345       izquierda->clave[izquierda->clavesUsadas+i] = derecha->clave[i];\r
 346    for(i = 0; i <= derecha->clavesUsadas; i++) {\r
 347       izquierda->puntero[izquierda->clavesUsadas+i] = derecha->puntero[i];\r
 348       if(derecha->puntero[i]) derecha->puntero[i]->padre = izquierda;\r
 349    }\r
 350    izquierda->clavesUsadas += derecha->clavesUsadas;\r
 351    if(padre == Entrada && padre->clavesUsadas == 0) { // Cambio de entrada\r
 352       Entrada = izquierda;\r
 353       Entrada->padre = NULL;\r
 354       delete padre;\r
 355       padre = NULL;\r
 356    }\r
 357    delete derecha;\r
 358 }\r
 359 \r
 360 int main()\r
 361 {\r
 362    int matriz[TAMANO];\r
 363    btree arbol(500);\r
 364    stclave clave;\r
 365    int i;\r
 366
 367 //   srand(time(NULL));
 368    for(i = 0; i < TAMANO; i++) {
 369       do {
 370          matriz[i] = rand()%10000;
 371          clave.valor = matriz[i];
 372          clave.registro = i;
 373       } while(!arbol.Insertar(clave));
 374    }
 375
 376    cout << "mostrar: " << endl;
 377    arbol.Mostrar();
 378
 379    cout << "Buscar elemento 23: " << matriz[23] << " posicion: " <<\r
 380      arbol.Buscar(matriz[23]) << endl;\r
 381
 382    for(i = 0; i < TAMANO; i++) {\r
 383       cout << "Borrar: [" << i << "]: " << matriz[i] << endl;\r
 384       arbol.Borrar(matriz[i]);\r
 385 //      arbol.Mostrar();\r
 386    }\r
 387    arbol.Mostrar();\r
 388    return 0;\r
 389 }\r