Błędny out w B-Tree

Odpowiedz Nowy wątek
2015-01-23 17:00
0

Cześć. Mam program, który na wyjście wypisuje B-drzewo rzędu 3 w postaci preorder. Jednak patrząc na output i porównując z wizualizacją okazuję się, że program daje zły wynik, mianowicie korzeń niespełnia warunku 2M (gdzie M jest rzędem drzewa). Nie wiem czy błąd nie tkwi w tej linijce if (root.key[0] == 2 * rank-1), ale sugerowałem się algorytmami znalezionymi w internecie. Jednak kiedy zmienię te linijke na if (root.key[0] == 2 * rank) program wyrzuca przekroczenie tablicy. Mógłby ktoś wskazać błąd?
Oto mój kod:

 import java.io.*;
import java.util.*;

class Page { //strona

    int rank;      // rzad drzewa
    int[] key;     // klucze, key[0] - aktualna ilosc kluczy
    Page[] kid;    // dzieci
    boolean leaf;  // TRUE - lisc, FALSE - wezel wewnetrzny

    Page (int rank) {
        this.rank = 3;
    }

    Page (int rank, int n, boolean isLeaf) {
        this.rank = 3;
        key = new int[2 * rank];
        kid = new Page[2 * rank];
        key[0] = n;
        leaf = isLeaf;
    }
}

class BTree {

    int rank;                  // rzad drzewa
    Page root;                 // korzen drzewa
    String searchPath;         // przechowuje strony przebyte do wyszukiwanego elementu
    File BTreeData;            // dane i testy
    Scanner fileScanner;
    FileWriter outFileWriter;

    BTree (String testFilePath, String outFilePath) throws Exception {
        BTreeData = new File (testFilePath);
        fileScanner = new Scanner (BTreeData);
        outFileWriter = new FileWriter (outFilePath);
        rank = 3;
        root = new Page (rank, 0, true);
        searchPath = "";
    }

    void print () throws Exception {

        Queue<Page> pageQueue = new LinkedList ();     // kolejka na kolejne strony
        pageQueue.add (root);                          // pierwszy element
        Page x;                                        // element biezacy
        int i;                                         // iterator strony
        while (!pageQueue.isEmpty ()) {                // dopoki kolejka nie bedzie pusta
            x = pageQueue.poll ();                     // pobieramy pierwszy element
            for (i = 1; i < x.key[0]; i++) {
                System.out.print (x.key[i] + ",");     // wypisanie elementu
                outFileWriter.write (x.key[i] + ",");  // zapisanie elementu na pliku
                if (x.kid[i - 1] != null)              // jezeli dziecko istnieje
                    pageQueue.add (x.kid[i - 1]);      // to je dodajemy do kolejki
            }
            if (x.key[0] != 0) {                       // jezeli powinnismy wypisac ostatni element
                System.out.print (x.key[x.key[0]]+" "); //poziom drzewa
                outFileWriter.write(x.key[x.key[0]] + "");
            }
            if (x.kid[i - 1] != null)                  // jezeli przedostatnie dziecko istnieje
                pageQueue.add (x.kid[i - 1]);          // to je dodajemy do kolejki
            if (x.kid[x.key[0]] != null)               // jezeli ostatnie dziecko istnieje
                pageQueue.add (x.kid[x.key[0]]);       // to je dodajemy do kolejki
            if (!pageQueue.isEmpty ()) {               // jezeli sa jeszcze strony
                System.out.print (" ");                // to stawiamy odstep
                outFileWriter.write (" ");             // to stawiamy odstep
            }
        }
        System.out.println ();
        outFileWriter.write("\r\n");
    }

    // inny format niz print, tylko na wyjscie
    void print2 () {
        Queue<Page> pageQueue = new LinkedList ();     // kolejka na kolejne strony
        pageQueue.add (root);                          // pierwszy element
        pageQueue.add (new Page (0));                  // element oznaczajacy nowa rzad (nowa linie)
        Page x;                                        // element biezacy
        while (!pageQueue.isEmpty ()) {                // dopoki kolejka nie bedzie pusta
            x = pageQueue.poll ();                     // pobieramy pierwszy element
            if (x.rank == 0) {                         // jezeli ma byc nowa linia
                if (!pageQueue.isEmpty ())             // jezeli sa jeszcze elementy
                    pageQueue.add (new Page (0));      // oznaczamy nowa linie
                System.out.println ();                 // wypisujemy biezaca
            }
            else {                                     // wypisujemy strone
                System.out.print ("< ");
                for (int i = 1; i <= x.key[0]; i++) {
                    System.out.print (x.key[i] + " ");
                    if (x.kid[i - 1] != null)          // jezeli dziecko istnieje
                        pageQueue.add (x.kid[i - 1]);  // to je dodajemy do kolejki
                }
                System.out.print ("> ");
                if (x.kid[x.key[0]] != null)           // jezeli ostatnie dziecko istnieje
                    pageQueue.add (x.kid[x.key[0]]);   // to je dodajemy do kolejki
            }
        }
    }

    void search (int x) {   // x - wyszukiwana wartosc
        search2 (x, root);  // zaczynamy szukanie od korzenia
    }

    void search2 (int x, Page p) {                       // x - szukana wartosc, p - aktuanie przeszukiwana strona
        searchPath += "< ";                              // poczatek nowej strony
        for (int i = 1; i <= p.key[0]; i++) {
            searchPath += p.key[i] + " ";                // elementy nowej strony
        }
        searchPath += "> ";                              // koniec strony
        int i = 1;
        while (i <= p.key[0] && x > p.key[i]) {          // szukanie mniejszego lub rownego elementu
            ++i;
        }
        if (i <= p.key[0] && x == p.key[i]) {            // jezeli znalezlismy element
            System.out.println (searchPath + p.key[i]);  // wypisujemy droge i element
            searchPath = "";                             // reset drogi
            return;
        }
        if (p.leaf) {                                    // jezeli nie ma juz wiecej stron
            System.out.println ("Element nie zostal znaleziony");
            searchPath = "";
        }
        else                                             // jezeli sa jeszcze strony
            search2 (x, p.kid[i - 1]);                   // przechodzimy do kolejnej
    }

    void splitChild (Page parent, int i, Page child) {          // i - pozycja na ktora wstawimy element z dziecka do rodzica
        Page newChild = new Page (rank, rank - 1, child.leaf);  // nowa strona w drzewie
        for (int j = 1; j <= rank - 1; j++) {
            newChild.key[j] = child.key[j + rank];              // kopiowanie drugiej polowy elementow
        }
        if (!child.leaf)
            for (int j = 1; j <= rank; j++) {
                newChild.kid[j - 1] = child.kid[j + rank - 1];  // kopiowanie drugiej polowy dzieci
            }
        child.key[0] = rank - 1;                                // zmniejszenie ilosci elementow
        for (int j = parent.key[0]; j >= i; j--) {
            parent.kid[j + 1] = parent.kid[j];                  // przesuniecie dzieci rodzica, miejsce dla nowego elementu
        }
        parent.kid[i] = newChild;                               // nowe dziecko rodzica
        for (int j = parent.key[0]; j >= i; j--) {
            parent.key[j + 1] = parent.key[j];                  // przesuniecie wartosci, miejsce dla nowego elementu
        }
        parent.key[i] = child.key[rank];                        // nwstawienie nowego elementu
        ++parent.key[0];                                        // zwiekszenie ilosci o nowy element
    }

    boolean insertNonfull (Page insertPage, int x) {                // x - wstawiana wartosc, insertPage - niepelna strona
        int i = insertPage.key[0];
        while (i >= 1 && x < insertPage.key[i]) {                   // szukanie potencjalnego miejsca badz elementu
            --i;
        }
        if (i != 0 && x == insertPage.key[i]) {                     // jezeli element jest juz w drzewie
            System.out.println ("Element (" + x + ") znajduje sie juz w drzewie.");
            return false;
        }
        if (insertPage.leaf) {                                      // jezeli lisc to wstawiamy
            for (int j = insertPage.key[0]; j > i; j--) {
                insertPage.key[j+1] = insertPage.key[j];          // przesuniecie elementow
            }
            insertPage.key[i + 1] = x;                              // wstawienie nowego elementu
            ++insertPage.key[0];
            return true;// zwiekszenie ilosci elementow
        }
        else {
            ++i;
            if (insertPage.kid[i - 1].key[0] == 2 * rank-1) {     // jezeli potomek jest zapelniony
                splitChild (insertPage, i, insertPage.kid[i - 1]);  // dzielimy go z pomoca rodzica
                if (x > insertPage.key[i])                          // jezeli nowy element z potomka byl mniejszy
                    ++i;                                            // przesuwamy pozycje
            }
            return insertNonfull (insertPage.kid[i - 1], x);        // probujemy wstawic do potomka
        }
    }

    boolean insert (int x) {                           // x - wstawiana wartosc
        if (root.key[0] == 2 * rank-1) {             // jezeli korzen jest pelny
            Page newRoot = new Page (rank, 0, false);  // tworzymy nowa strone
            newRoot.kid[0] = root;                     // aktualny korzen jest jej potomkiem
            root = newRoot;                            // nowa stronazostaje korzeniem
            splitChild (root, 1, newRoot.kid[0]);      // dzielimy elementy starego korzenia
            return insertNonfull (newRoot, x);         // probujemy wstawic do juz niepelnego korzenia
        }
        else                                           // w korzeniu sa jeszcze miejsca
            return insertNonfull (root, x);            // probujemy wstawic do niepelnego korzenia
    }

    // Usuwanie elementu i jego prawego dziecka
    void deleteRight (Page pageToChange, int i) {           // i - indeks usuwanego elementu
        int j;
        for (j = i; j < pageToChange.key[0]; j++) {
            pageToChange.key[j] = pageToChange.key[j + 1];  // przesuniecie wartosci o jeden w lewo od konca
            pageToChange.kid[j] = pageToChange.kid[j + 1];  // przesuniecie dzieci o jeden w lewo od konca
        }
        --pageToChange.key[0];                              // zmniejszenie ilosci elementow
    }

    // Usuwanie elementu i jego lewego dziecka
    void deleteLeft (Page pageToChange, int i) {        // i - indeks elementu do usuniecia
        pageToChange.kid[i - 1] = pageToChange.kid[i];  // usuwamy lewe dziecko nadpisujac je prawym
        deleteRight (pageToChange, i);                  // reszta operacji pokrywa sie z funkcja deleteRight
    }

    int searchMax (Page actualPage) {  // wyszukiwanie maksymalnego elementu w poddrzewie o korzeniu actualPage
        if (actualPage.leaf)
            return actualPage.key[actualPage.key[0]];              // ostatni a zarazem najwiekszy element
        else
            return searchMax (actualPage.kid[actualPage.key[0]]);  // przejscie pietro nizej do wiekszych elementow
    }

    int searchMin (Page actualPage) {  // wyszukiwanie minimalnego elementu w poddrzewie o korzeniu actualPage
        if (actualPage.leaf)
            return actualPage.key[1];              // ostatni a zarazem najmniejszy element
        else
            return searchMin (actualPage.kid[0]);  // przejscie pietro nizej do mniejszych elementow
    }

    // Wstawia strone prawa do lewej z wartoscia srodkowa - x
    void mergeRightToLeft (Page leftPage, int x, Page rightPage) {
        int i;
        ++leftPage.key[0];                                  // nowy element w stronie
        int leftSize = leftPage.key[0];
        leftPage.key[leftSize] = x;                         // wstawienie nowego elementu x
        leftPage.kid[leftSize] = rightPage.kid[0];          // przepisanie pierwszego dziecka
        for (i = 1; i <= rightPage.key[0]; i++) {
            leftPage.key[i + leftSize] = rightPage.key[i];  // przepisanie wszystkich wartosci
            leftPage.kid[i + leftSize] = rightPage.kid[i];  // przepisanie pozostalych dzieci
        }
        leftPage.key[0] += rightPage.key[0];                // zwiekszenie ilosci elementow
    }

    // Wstawiamy nowa wartosc i nowe dziecko na poczatek strony
    void insertFront (Page insertPage, Page newKid, int x) {
        int i;
        for (i = insertPage.key[0]; i >= 1; i--) {      // tworzenie miejsca na poczatku
            insertPage.key[i + 1] = insertPage.key[i];  // przesuniecie wartosci w prawo
            insertPage.kid[i + 1] = insertPage.kid[i];  // przesuniecie dzieci w prawo
        }
        insertPage.kid[i + 1] = insertPage.kid[i];      // przesuniecie ostatniego dziecka
        insertPage.key[1] = x;                          // nowa wartosc
        insertPage.kid[0] = newKid;                     // nowe dziecko
        ++insertPage.key[0];                            // zwiekszenie ilosci elementow
    }

    // Wstawiamy nowa wartosc i nowe dziecko na koniec strony
    void insertRear (Page insertPage, Page newKid, int x) {
        ++insertPage.key[0];                         // zwiekszamy ilsoc elementow
        insertPage.key[insertPage.key[0]] = x;       // wartosc na odpowiednie (ostatnie) miejsce
        insertPage.kid[insertPage.key[0]] = newKid;  // dziecko na odpowiednie (ostatnie) miejsce
    }

    boolean delete (int x) {
        return delete2 (root, x);  // zaczynamy usuwanie od korzenia
    }

    boolean delete2 (Page actualPage, int x) {  // x - usuwana wartosc
        int i = 1;
        while (i <= actualPage.key[0] && x > actualPage.key[i]) {  // iteracja po stronie, szukanie wartosci
            ++i;
        }
        if (i <= actualPage.key[0] && x == actualPage.key[i])      // jezeli element jest na stronie
            if (actualPage.leaf) {                                 // ktora jest lisciem
                deleteRight (actualPage, i);                       // usuwamy element
                return true;                                       // koniec algorytmu
            }
            else {                                                 // wezel wewnetrzny
                Page leftChild = actualPage.kid[i - 1];            // lewe dziecko usuwanego pola
                Page rightChild = actualPage.kid[i];               // prawe dziecko usuwanego pola
                if (leftChild.key[0] >= rank) {                    // mozemy usuwac w lewym dziecku
                    int max = searchMax (leftChild);               // maksymalny element lewego poddrzewa
                    actualPage.key[i] = max;                       // podstawienie nowej wartosci
                    return delete2 (leftChild, max);               // usuniecie tej wartosci z poddrzewa
                }
                else if (rightChild.key[0] >= rank) {              // mozemy usuwac w prawym dziecku
                    int min = searchMin (rightChild);              // minimalny element prawego poddrzewa
                    actualPage.key[i] = min;                       // podstawienie nowej wartosci
                    return delete2 (rightChild, min);              // usuniecie tej wartosci z poddrzewa
                }
                else {                                             // za mala ilosc elementow w obu potomkach
                    mergeRightToLeft (leftChild, x, rightChild);   // laczymy obu potomkow z usuwana wartoscia
                    deleteRight (actualPage, i);                   // usuwamy wartosc i prawego potomka ktory jest juz w lewym
                    return delete2 (leftChild, x);                 // usuwamy wartosc z poddrzewa
                }
            }
        else {                                                 // element nie znajduje sie na stronie
            if (actualPage.leaf)                               // jezeli koniec drzewa
                return false; // konczymy z niepowodzeniem
            --i;                                               // indeks potomka w ktorym moze znajdowac sie usuwany element
            Page ourPage = actualPage.kid[i];                  // podejrzana o zawieranie elementu strona
            Page leftNeighbor = new Page (rank);               // lewy sasiad (jezeli bedzie istnial)
            Page rightNeighbor = new Page (rank);              // prawy sasiad (jezeli bedzie istnial)
            if (i > 0)                                         // lewy sasiad istnieje
                leftNeighbor = actualPage.kid[i - 1];
            if (i < actualPage.key[0])                         // prawy sasiad istnieje
                rightNeighbor = actualPage.kid[i + 1];
            if (ourPage.key[0] == rank - 1)                                        // jezeli za malo elementow na stronie
                if (i > 0 && leftNeighbor.key[0] >= rank) {                        // jezeli lewy sasiad ma odp. duzo elem.
                    // przesuwamy odpowiednie elementy i dziecko
                    insertFront (ourPage, leftNeighbor.kid[leftNeighbor.key[0]], actualPage.key[i]);
                    actualPage.key[i] = leftNeighbor.key[leftNeighbor.key[0]];
                    --leftNeighbor.key[0];
                    return delete2 (ourPage, x);                                   // kontynuujemy usuwanie elementu x
                }
                else if (i < actualPage.key[0] && rightNeighbor.key[0] >= rank) {  // jezeli prway sasiad ma odp. duzo elem.
                    // przesuwamy odpowiednie elementy i dziecko
                    insertRear (ourPage, rightNeighbor.kid[0], actualPage.key[i + 1]);
                    actualPage.key[i + 1] = rightNeighbor.key[1];
                    deleteLeft (rightNeighbor, 1);
                    return delete2 (ourPage, x);                                   // kontynuujemy usuwanie elementu x
                }
                else if (i > 0) {                                                  // istnieje lewy sasiad
                    mergeRightToLeft (leftNeighbor, actualPage.key[i], ourPage);   // scalamy nasza strone do lewego sasiada 
                    deleteRight (actualPage, i);                                   // usuwamy nasza strone
                    if (actualPage.key[0] == 0)                                    // jezeli korzen jest pusty
                        root = actualPage.kid[0];                                  // przesuwamy korzen nizej
                    return delete2 (leftNeighbor, x);                              // kontynuujemy usuwanie x
                }
                else {                                                                 // istnieje prawy sasiad
                    mergeRightToLeft (ourPage, actualPage.key[i + 1], rightNeighbor);  // scalamy go do naszej strony
                    deleteRight (actualPage, i + 1);                                   // usuwamy prawego sasiada
                    if (actualPage.key[0] == 0)                                        // jezeli korzen jest pusty
                        root = actualPage.kid[0];                                      // przesuwamy korzen nizej
                    return delete2 (ourPage, x);                                       // kontynuujemy usuwanie x
                }
            else                                                                       // mozemy usuwac z naszej strony
                return delete2 (ourPage, x);                                           // kontynuujemy usuwanie x
        }
    }

    void runTests () throws Exception {
        String order;  // znak funkcji do wykonania
        int argument;  // argument wykonywanej funkcji

        while (fileScanner.hasNext ()) {
            order = fileScanner.next ();
            argument = fileScanner.nextInt ();
            switch (order) {
                case "s":
                    search (argument);
                    break;
                case "i":
                    insert (argument);
                    print ();
                    break;
                case "d":
                    delete (argument);
                    print ();
                    break;
            }
        }
        outFileWriter.close ();
    }
}

public class Main {

    public static Scanner fileScanner;

    public static void main (String[] args) throws Exception {

        System.out.println ("Rząd drzewa = 3");
        BTree data1 = new BTree ("Dane/input3.txt", "Wyniki/out1.txt");
        data1.runTests ();
    }
}

Pozostało 580 znaków

2015-01-23 17:11
1

Serio łudzisz się że ktoś będzie poświecał czas na analizę tego? o_O Odpal debuger i klikaj, innej rady nie ma.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0