Problem z zakresem pamieci/wskaznikami przy rotacji drzewa BST

0

Cześć! Pisze rotację drzewa BST wikipedia. Dla przypadku w ktorym wszystkie liscie istnieją nie ma problemu, przypadkiem problematycznym jest moment gdy, odwołując się do prawego wezła liścia P (oznaczenie jak na wiki, rotacja w prawo) jest on NULL. Tworząc wsk->right = temp nie działa ze względów oczywistych - nie istnieje, natomiast gdy zrobie (*wsk).right=&temp działa, ale po wyjściu z funkcji do której korzeń jest przekazywany przez wskaznik debubugger pokazuje "unable to read memory". Co może być problemem?

//parent_node wskazuje na miejsce wzgledem ktorego ma byc rotacja, z wiki lisc Q
void r_rotation(leaf *root, leaf *main)
{
    leaf *parent_node, *parent;
    leaf temp, temp2;

    parent = return_parent(root, main->key);

    if (parent->key > main->key)parent_node = (*parent).left;
    else parent_node = (*parent).right;

    if (main->left != NULL)
    {
        if (main->left->right != NULL)
        {
            temp2 = *(main->left->right);
            temp = *(main);
            *(parent_node) = *(main->left);
            *(parent_node->right) = temp;
            *(parent_node->right->left) = temp2;
        }
        else
        {
            temp = *(main);
            temp.left = NULL;
            *(parent_node) = *(main->left);
            (*parent_node).right = &temp;
            //cout << parent_node->right->key;
        }
    }
}

Brutalne add_leaf(parent_node, &temp); też nie dało rady.

1

Coś przekombinowałeś. Jest późno więc mogłem się pomylić, ale:

void rotate_right(Node **edge) {
    assert(edge);

    Node *top = *edge;
    assert(top->left);

    Node *left_node = top->left;

    top->left = left_node->right;
    if (left_node->right)
        left_node->right->parrent = top;
    left_node->parrent = top->parrent;

    *edge = left_node;

    left_node->right = top;
    top->parrent = left_node;
}

edge jest wskaźnikiem na wskaźnik do Q (wskaźnikiem na zmienną wewnątrz Node [left albo right] będącą wskaźnikiem na dziecko Q).

0

Zadziałało, naprawdę prosto wow, teraz to tylko 4 linijki :D tylko jest jeszcze jeden problem. Skoro Q jest wskaznikiem na left/right co w przypadku rotacji gdy Q jest korzeniem?

//Edit:

    leaf *wsk = &root;
    if (root.left != NULL)
        r_rotation(&(wsk));
    cout << endl;
    printBT("", "", wsk);

Do funkcji printBT przekazywałem &root zamiast wsk. Już wszystko działa, bardzo dziękuję za pomoc.

0

Cześć, mam kolejny problem. Chciałem zrównoważyć drzewo za pomocą algorytmu DSW.

void to_list(leaf **root)
{
    leaf *top=*root;
    while(top->left!=NULL)r_rotation(&top);
    *root=top;
    if(top->right!=NULL)to_list(&top->right);
}
void rotation_list(leaf **root, int m)
{
    leaf *temp=*root;
    l_rotation(&temp);
    if(m>0)rotation_list(&temp->right,m-1);
    *root=temp;
}
void list_to_avl(leaf **root,int n)
{
    rotation_list(root,n/2-1); //rotuje co drugi lisc, n/2-1 razy
    while(abs(return_diff(*root,0))>1) //return diff zwraca roznice miedzy wysokoscia lewego i prawego poddrzewa, dziala dobrze
    {
        rotation_list(root,(depth(*root)-1)/2); //depth zwraca glebokosc prawego poddrzewa
    }
}

W main najpierw wywołuje to_list potem list_to_avl. Przekształcenie w liste działa dobrze. Przekształcam listę w drzewo nie obliczając tej specjalnej liczby tylko dopóki dla korzenia nie jest zrównoważonego ponieważ mi nie działało, przeczytałem jak działa algorytm i zrobiłem po swojemu. Rotuje co drugi do końca, aż będzie równe, tylko problem jest taki jak widać w załączniku. Wyświetlam własnie te różnice wysokości i prawy liść korzenia ma zbyt duży stopień ;/

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