Červeno-černé stromy (rbbvs) – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Siggi0
Návštěvník
17. 4. 2015   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 46.229.123.–
Reklama
Reklama
ondrej39+1
Věrný člen
17. 4. 2015   #2
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
17. 4. 2015   #3
-
0
-

#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;
}
Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
17. 4. 2015   #4
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
17. 4. 2015   #5
-
0
-

#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

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
17. 4. 2015   #6
-
0
-

#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).

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
17. 4. 2015   #7
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
17. 4. 2015   #8
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
17. 4. 2015   #9
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
17. 4. 2015   #10
-
0
-

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

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
17. 4. 2015   #11
-
0
-

#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

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
18. 4. 2015   #12
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
18. 4. 2015   #13
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
18. 4. 2015   #14
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
18. 4. 2015   #15
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
18. 4. 2015   #16
-
0
-

#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.

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
18. 4. 2015   #17
-
0
-

#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?

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
18. 4. 2015   #18
-
0
-

#17 Siggi
Oddělej tu nulu u returnu.

if ( rotationRoot->right == NULL ) {
	return;
}
Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
21. 4. 2015   #19
-
0
-

#18 ondrej39
Díky za pomoc.

Nahlásit jako SPAM
IP: 46.229.123.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 140 hostů

Podobná vlákna

Stromy — založil Misiak

C# WPF černé okno — založil pr0gr4mm3r

Černé editační pole — založil Mesik

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý