Červeno-černé stromy (rbbvs) – C / C++ – Fórum – Programujte.com

Zdravím, zase nemůžu najít chybičku, proč mi ten program padá.

typedef enum Color {
    RED, BLACK
} Color;

/**
 * @brief Struktura Node slouzi k reprezentaci uzlu v strome
 * atribut key klic daneho uzlu
 * atribut color muze nabyvat hodnoty 'RED' a 'BLACK'
 * atribut parent je reference na rodice uzlu
 * atribut left je reference na leveho potomka
 * atribut right je reference na praveho potomka
 * */
typedef struct Node {
    int key;
    Color color;
    struct Node* parent;
    struct Node* left;
    struct Node* right;
} Node;

/**
 *  @brief Struktura RedBlackTree slouzi k reprezentaci
 *  binarniho vyhledavaciho stromu
 *  atribut root je reference na korenovy uzel typu Node
 * */
typedef struct RedBlackTree {
    Node* root;
} RedBlackTree;

/**
 * @brief Vykona rotaci doleva kolem uzlu 'rotationRoot' v strome 'tree'
 **/
/*
Kromě funkce rotateLeft už bylo vše předem naimplementováno
Chyba je asi v řádku s tree/*->root*/ = y; bez root to nepadá, ale mám jen jeden
node, což je špatně a s root to padá.
*/
void rotateLeft(RedBlackTree *tree, Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if(y->left != NULL){
        y->left->parent = x;
    }
    y->parent = x->parent;
    if(x->parent == NULL){
        tree/*->root*/ = y;
    }else{
        if(x == x->parent->left){
            x->parent->left = y;
        }else{
            x->parent->right = y;
        }
    }
    y->left = x;
    x->parent = y;
}

Mám nodes od 0 po 6 pod sebou rovnány do prava a když rotuji do leva, tak z 0 (kořen) by měla přijít 1 a mít syny, levého 0 a pravého 2 a ostatní pod sebe a pak rotovat podle node x. Jen mi to někde padá. Ještě všemu tolik rozumím a většinou se učím na příkladech, než teoriích a definicích.

#1 Siggi
Přijde mi, že tam máš zbytečně moc checků. Asi půl roku nazpátek jsem dělal červeno-černý strom v C++ a pro inspiraci jsem použil tento zdrojový kód.

#2 ondrej39
Nene, mám tam stejně checků jako ty, ba naopak máš tam o jeden if více než já a ikdyž jsem to zkusil předělat pro zvědavost podle tebe, tak stále to hází error s tree->root.

void rotateLeft(RedBlackTree *tree, Node *x) {
    Node *y = x->right;
    if(x->parent == NULL){
        tree->root = y;
    }else{
        if(x == x->parent->left){
            x->parent->left = y;
        }else{
            x->parent->right = y;
        }
    }
    if(y != NULL){
        y->parent = x->parent;
    }
    x->right = y->left;
    if(y->left != NULL){
        y->left->parent = x;
    }
    y->left = x;
    x->parent = y;
}

#3 Siggi

Promiň, vypadlo mi, že v té funkci pro rotaci mají funkci pro nahrazení uzlu, kde jsou další ověření.

Hoď sem celou svou implementaci, to, co zatím máš, pravděpodobně máš problém někde jinde. Ta funkce na rotaci mi tehdy úplně normálně fungovala.

P.S. Když už něco programuješ, není úplně od věci používat výstižnější názvy proměnných. Název jako c, x, n, y fakt nikomu nic neřekne.

#4 ondrej39
x y máme přímo v definici rotace, žádné jiné názvy nemám nespecifikované, jen používám to co mám používat.

http://pastebin.com/bUyswzrP

#5 Siggi
Tady se snažíš přistoupit k něčemu, co neexistuje (y->left nejde). Můžeš si do funkce pro rotaci vložit třeba ověření

if (x->left == NULL && x->right == NULL) // rotace je k ničemu
{
	return;
}

V tom tvým testu se snažíš rotovat uzel, pro něhož rotace nemá žádný smysl, jelikož nemá ani jednoho potomka. Proč mi funkce fungovala, protože v tom zdrojáku, který jsem posílal, který implementoval někdo jiný, je pravděpodobně ověřený, že se funkci pro levou rotaci vždycky předá uzel, který pravého potomka má (procházet celý ten kód se mi nechce).

#6 ondrej39
To píšeš o tom prvním kódu a nebo tom druhém co jsem přepsal podle tebe? ... Mě zajímá ten první a ten byl měl být dobře podle pseudokódu co mám ve slidech a padá to kvůli tree->root a ne levému potomku.

Pokud si to tak ovšem myslel.

#7 Siggi
Testoval jsem kód, který jsi poslal na pastebin. Teď už nejsem u PC, mrknu se ti na to když tak zítra.

#8 ondrej39
On je ve směs stejný až na ten jeden if, který jsem předtím přidával co jsem viděl u tvého odkazu.
Přes všechny podmínky to projde až po ten tree a nevím, jestli za to může on.
Prohledával jsem internet a spousta lidí to má napsáno jako já a nevím proč by jim to fungovalo a mně ne :D.

#9 Siggi
A zkoušel sis to odkrokovat? Podívat se, kde přesně ti to padá? Přímo v té funkci pro rotaci?

#10 ondrej39
To píšu skoro v každém komentu :D

if(x->parent == NULL){
    tree/*->root*/ = y;   <- když oddělám ten koment, tak mi to spadne, když to tam nemám, nedělá to nic a vymaže mi to všechny node

#11 Siggi
Tak ono je nejen dobrý vědět, kde ti to padá, ale také proč to na daném místě padá. Každopádně seš si jistej, že ti to padá v místě s tím kořenem?

1) Když tam nechám ten komentář, tak mi to nejde ani zkompilovat, protože RedBlackTree* != Node* (nevím, jestli jsi výrazem "nedělá to nic" myslel toto), 2) když ten komentář teda oddělám, padá to ne v tom místě, ale jinde, konkrétně Zde (máš stejnej problém, jako v té funkci ze zdrojáku, který jsem posílal, odkazuješ se na y->left, ale y je NULL, protože x je Node* bez potomků).

Prostě k checku s kořenem se to ani nedostane.

#12 ondrej39
Tree->root je to samé co holé X, protože bere odkaz z tree->root a x->right je pravý potomek, což by mělo být 1, tree root je 0.

Zatím přemýšlím, co s tím.

#13 Siggi
No hele, máš ten main...

int _tmain(int argc, _TCHAR* argv[])
{
	testRotateLeft(); // hned tato funkce způsobuje padání
	testRotateRight();
	testInsert();
	testSearch();
	testIsCorrectRBTree();
	
	return 0;
}

a ve funkci testRotateLeft() ti tedy probíhá ta levá rotace, tj. nachází se tam kód, který volá tu funkci rotateLeft(RedBlackTree*, Node*). Nejprve se tedy ve funkci testRotateLeft() vytvoří nevyvážený strom

RedBlackTree *tree = initUnbalancedTreeRight();

Připojen obrázek.

a provede se rotace kolem rootu tohoto stromu, neboli funkci pro rotaci předáváš strom, tree, a uzel tree->root.

rotateLeft(tree, tree->root);

a tím získáš tento strom

Připojen obrázek.

Poté v kódu vybíráš uzel

Node *rnode = tree->root->right;

tedy rnode je pointer na uzel s číslem 2, a kolem tohoto uzlu provádíš zase levou rotaci

rotateLeft(tree, rnode);

a vznikne ti strom

Připojen obrázek.

a do této doby je taky ještě všechno OK. Ale teď přijde problém. Další vybíraný uzel je totiž
 uzel číslo 0

Node *rnode = tree->root->left;

a jak si můžeš všimnout z obrázku, uzel s číslem 0 nemá ani jednoho potomka. Ty se následně kolem tohoto uzlu snažíš provést levou rotaci

rotateLeft(tree, rnode);

a přesně tady ti to padá. Protože v té funkci pro rotaci (jak už jsem tady několikrát psal) se odkazuješ na něco, co prostě neexistuje.

Mám dojem, že tady v tomto místě, kde máš

Node *rnode = tree->root->left;

si chtěl ve skutečnosti mít

Node *rnode = tree->root->right;

Když kód takhle upravíš, měl by normálně fungovat.

#14 ondrej39
Testy já neovlivňuji, jen implementaci té funkce. Pokud tam mají oni left, tak proto mají nějaký důvod. Ale je to divné.

Ještě mrknu na fórum, jestli se někdo nepřepsal.
Bohužel, žádné cvičící nenahlásil chybu, takže to tak má být.

#15 Siggi
Ten test, jak je napsanej, je napsanej blbě. V tom testu se té funkci prostě předává uzel, pro něhož rotaci nelze provést, a zároveň ve funkci pro rotaci nemáš žádné ověření, co se bude dělat, když ta rotace nejde. Proto to spadne.

#16 ondrej39
Přidal jsem tam check if

    if(rotationRoot->right == NULL){
        return 0;
    }

Jestli je rotovaný node nulový, ať ukončí operaci, ale je to funkce VOID, takže mi tam hlásí warning, šlo by to nějak elegantněji?

#17 Siggi
Oddělej tu nulu u returnu.

if ( rotationRoot->right == NULL ) {
	return;
}

#18 ondrej39
Díky za pomoc.