B-strom – C / C++ – Fórum – Programujte.com

Tak tady jsem totálně bezradný. Teoreticky to zvládám a i překreslit do sešitu, ale jak to mám naimplementovat do C, tak jsem v háji. 3H projíždím google, jestli tam není podobný kód, ale nenašel jsem nic pěkného.

http://pastebin.com/FtQR9MKE

Funkce na porovnání, nebylo co zkazit.
In,Pre,Post-order si nevím rady, protože tam nemám ukazatel left ani right, ale pouze children. Nechápu proč to tak ztěžují v té škole. Jsem z toho dost špatnej.
Funkce na vkládání, tam jsem zkoušel přepsat pseudo kód ze slidů, ale taky neuspěšně.

void splitChild(Node *node, int i){
    int t = 3;
    Node *z = (Node*)malloc(sizeof(Node));
    Node *y = node->children[i];
    z->leaf = y->leaf;
    z->n = t - 1;
    for(int j = 1; j < (t-1); j++){
        z->keys[j] = y->keys[j+t];
    }
    if(y->leaf == false){
        for(int j = 1; j < t; j++){
            z->children[j] = y->children[j+t];
        }
    }
    y->n = t - 1;
    for(int j = node->n+1; j > i+1; j--){
        node->children[j+1] = node->children;
    }
    node->children[i+1] = z;
    for(int j = node->n; j > i; j--){
        node->keys[j+1] = node->keys[j];
    }
    node->keys[i] = y->keys[t];
    node->n = node->n+1;
}

void insertNonFull(Node *node, int k){
    Node *i = node->n;
    int t = 3;
    if(node->leaf == true){
        while(i >= 1 && k < node->keys[i]){
            node->keys[i+1] = node->keys[i];
            i--;
        }
        node->keys[i+1] = k;
        node->n = node->n+1;
    }else{
        while(i >= 1 && k < node->keys[i]){
            i--;
        }
        i++;
        if(node->children[i]->n == 2*t-1){
            splitChild(node, i);
            if(k > node->keys[i]){
                i++;
            }
        }
        insertNonFull(node->children[i], k);
    }
}

void insertBTree(BTree *tree, int key)
{
    Node *node = tree;
    int t = 3;

    if(node->n == 2*t-1){
        Node *s = mallocNode(0, false);
        tree->root = s;
        s->children[1] = node;
        splitChild(s, 1);
        insertNonFull(s, key);
    }else{
        insertNonFull(node, key);
    }
}

Tak nějak má vypadat funkce pro insert, je tam plno chyb a u parametru t si nejsem jist jaká má být hodnota.

Stromy a ADT já rád. Když to nevyřešíš do zítřka, během dne se ti na to podívám :-).

#3 ondrej39
Haldy a Binární vyhledávací stromy jsem docela zvládal a bylo to docela lehké na pochopení, ale červeno černé stromy ty jsem nepobral vůbec. B-stromy si myslím, že umím obstojně tužkou a papírem, ale implementací vůbec. Zatím stále nad tím sedím a čtu slidy a strýčka googla.

#4 Siggi
Mrkni se tady na web na moc hezký vizualizace, pokud jsi ten web ještě neviděl. https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

#5 ondrej39
Tuto stránku znám, ukazoval nám ji i náš cvičící. Je dobré, že si navolíš i preventivní rozdělení, protože to tak musíme používat z přednášky. Jak říkám, ta vizualizace je dobrá a na papíře to zvládnu, horší je to naimplementovat. Proto se více bojím závěrečného implementačního testu než zkoušky, kde je většinou tužka, papír a teorie + něco málo implementace.

#6 Siggi
No hele, nebudu to sám vymýšlet, ale inspiroval bych se touto implementací.

Každopádně už funkci pro rozdělování potomků máš špatně. Ten původní kód je psaný v C++ a funkce splitChild je metoda třídy BTreeNode. To znamená, že jako taková má přístup k atributům objektu, na němž se metoda spouští (void BTreeNode::splitChild(int i, BTreeNode *y)).

Když se podíváš na zdroják té metody, tak tam pracuje se třemi proměnnými typu BTreeNode. První, nejlépe viditelný, je ten y, předávaný jako parametr, druhý je Uzel vytvořený přímo v metodě, uzel z, a třetí uzel je ten objekt, který metodu invokuje, this. Pokud tuto funkci budeš přepisovat do C, tam žádné objekty nejsou, ale ty ten třetí, this, objekt nějak do funkce dostat musíš, a potřebuješ proto ještě další parametr.

#7 ondrej39
 

void splitChild(Node **node, int i){
    int t = 2;
    Node *z = (Node*)malloc(sizeof(Node));
    Node *y = (*node)->children[i];
    z->leaf = y->leaf;
    z->n = t - 1;

    for(int j = 0; j < (t-1); j++){
        z->keys[j] = y->keys[j+t];
    }
    if(y->leaf == false){
        for(int j = 0; j < t; j++){
            z->children[j] = y->children[j+t];
        }
    }
    y->n = t - 1;
    for(int j = (*node)->n; j >= (i+1); j--){
        (*node)->children[j+1] = (*node)->children[j];
    }
    (*node)->children[i+1] = z;
    for(int j = (*node)->n; j > i; j--){
        (*node)->keys[j+1] = (*node)->keys[j];
    }
    (*node)->keys[i] = y->keys[t-1];
    (*node)->n = (*node)->n+1;
}

void insertNonFull(Node **node, int key){
    int i = (*node)->n;
    int t = 2;
    if((*node)->leaf == true){
        while(i >= 1 && (*node)->keys[i] > key){
            (*node)->keys[i+1] = (*node)->keys[i];
            i--;
        }
        (*node)->keys[i+1] = key;
        (*node)->n = (*node)->n+1;
    }else{
        while(i >= 1 && (*node)->keys[i] > key){
            i--;
        }
        i++;
        if((*node)->children[i]->n == 2*t-1){
            splitChild(*node, i);
            if((*node)->keys[i] < key){
                i++;
            }
        }
        insertNonFull((*node)->children[i], key);
    }
}
void insertBTnode(Node **node, int key){
    int t = 2;
    if(*node == NULL){
        *node = mallocNode(t, true);
        (*node)->keys[0] = key;
        (*node)->n = 1;
    }else{
        if((*node)->n == 2*t-1){
            Node *s = (Node*)malloc(sizeof(Node));
            *node = s;
            s->leaf = false;
            s->n = 0;
            s->children[1] = *node;
            splitChild(s, 1);
            insertNonFull(s, key);
        }else{
            insertNonFull(*node, key);
        }
    }
}

void insertBTree(BTree *tree, int key)
{
    insertBTnode(&tree->root, key);
}

Chyba u funkce insertNonFull u  (*node)->keys[i+1] = key; ... stejnak se v tom ztrácím

#8 Siggi
Tak to jsem vyřešil. U těch pomocných jsem oddělal ukazatel na ukazatel a nechal jen jeden, ale dál už jsem nepokročil.

Už mi to nepřemýšlí, zítra zase na to kouknu.

void splitChild(Node *node, int i){
    int t = 2;
    Node *y = node->children[i];
    Node *z = mallocNode(t, y->leaf);
    z->n = (t - 1);

    for(int j = 0; j < (t-1); j++){             // nejpravejsi prvek na rozdeleni
        z->keys[j] = y->keys[j+t];
    }
    if(node->leaf == false){
        for(int j = 0; j < t; j++){
            z->children[j] = y->children[j+t];
        }
    }
    y->n = (t - 1);
    for(int j = node->n; j >= (i+1); j--){
        node->children[j+1] = node->children[j];
    }
    node->children[i+1] = z;
    for(int j = node->n; j > i; j--){
        node->keys[j+1] = node->keys[j];
    }
    node->keys[i] = y->keys[t-1];
    node->n = node->n+1;
}

void insertNonFull(Node *node, int key){
    int i = node->n-1;
    int t = 2;
    if(node->leaf == true){
        while(i >= 0 && node->keys[i] > key){
            node->keys[i+1] = node->keys[i];
            i--;
        }
        node->keys[i+1] = key;
        node->n = node->n+1;
    }else{
        while(i >= 0 && node->keys[i] > key){
            i--;
        }
        if(node->children[i+1]->n == 2*t-1){
            splitChild(node, (i+1));
            if(node->keys[i+1] < key){
                i++;
            }
        }
        insertNonFull(node->children[i+1], key);
    }
}
void insertBTnode(Node **root, int key){
    int t = 2;
    Node *node = *root;

    if(*root == NULL){
         *root = mallocNode(t, true);
        (*root)->keys[0] = key;
        (*root)->n = 1;
    }else{
        if(node->n == 2*t-1){
            Node *s = mallocNode(t, false);
            *root = s;
            s->children[0] = node;
            splitChild(s, 0);
            insertNonFull(s, key);
        }else{
            insertNonFull(node, key);
        }
    }
}

void insertBTree(BTree *tree, int key)
{
    insertBTnode(&tree->root, key);
}

už fakt nevím

Čas vypršel.