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 ();
}
}