Drzewo BST- problem z usuwaniem wierzchołka

Odpowiedz Nowy wątek
2012-03-04 16:28
0

Witam wszystkich, gdyż to mój pierwszy post na tym forum. Aktualnie próbuję zrobić zadanie z serwisu main.edu.pl, a konkretniej to jest to zadanie z potyczek algorytmicznych 05.2002 pt. Trikontenerowiec. Chciałem do tego wykorzystać drzewo BST. Po jego implementacji na próbnych danych wydawało się, że jest wszystko dobrze. Ale nie wiem z jakiego powodu, kiedy buduję drzewo ze zbioru {1,2,3,4,5} poprzez odpowiedni rekurencyjny wybór liczb ze zbioru (tak aby drzewo było zrównoważone), to gdy dochodzi do usunięcia 3, nie usuwa go.

Dokładniej:

Dane wejścia: liczba 1<=m<=500000, liczba 0<=n<=1000000, po czym n par liczb, z których każda para oddzielona jest spacją.

Liczba n oznacza ilość płyt w magazynie. Każda para liczb oznacza jedną płytę. Pierwsza (od lewej) liczba z pary oznacza cenę płyty, a druga jej rozmiar.

Liczba m oznacza ilość prowadnic na płyty na statku. W każdej prowadnicy może znaleźć się tylko jedna płyta.

Program ma policzyć jaka będzie maksymalna wartość ładunku, jaki może zabrać magazynu (w którym jest n płyt) ze sobą statek, na którym jest m prowadnic.

UWAGA: Prowadnice są w pomieszczeniu o skośnym stropie. Efekt jest taki, że jeśli jest m prowadnic, to pierwsza ma rozmiar 1., druga rozmiar 2.,.....,(m-1). prowadnica ma rozmiar (m-1), a m. prowadnica ma rozmiar. Na prowadnice w rozmiarze m, możemy wsadzić płyty o rozmiarze <=m.

Działanie programu:
W teorii program powinien tworzyć zrównoważone drzewo BST. Sortować płyty wedle wartości (od najdroższej), a jeśli są równe wartości to wedle rozmiaru(od najmniejszej). Potem powinien po kolei brać wszystkie płyty i szukać dla nich prowadnicy, w której by się zmieściły, ale jak najmniejszej. Jeśli takową znajdzie to ma usunąć z drzewa wierzchołek o kluczu równym rozmiarowi prowadnicy(czy też rozmiarowi płyty, którą wstawiał).

Proszę nie zwracać uwagi na te bezsensowne cout<<-y. Powstawiałem ich tam tak dużo żeby widzieć gdzie się program wysypuje. Otóż po posortowane płyty wyglądają tak(pierwsza kolumna to wartosc, druga rozmiar):
905 5
897 3
855 2
735 4
617 2
468 4
406 3
301 1
117 5
19 1

Prowadnic na statku jest 5. Drzewo z nich skonstruowany powinno wyglądać tak:
3
/ \
1 4
\ /
2 5

Program wybiera pierwszą płytę poprawnie, wstawia ją w dobre miejsce i usuwa dobry węzeł. Ale gdy bierze już drugą z kolei robi wszystko poprawnie, ale nie usuwa po nim wierzchołka! Później znowu robi wszystko OK, aż do wzięcia płyty (617 2), tam już się wysypuje kompletnie wyrzucając błąd.

Proszę o pomoc, co w moim kodzie jest nie tenteges??? kiedy ręcznie (czyli w argumencie remove wpisuje konkretną liczbę) każe mu usuwać korzeń to robi to poprawnie.
Niżej wklejam kod i naprawdę proszę o pomoc bo to zadanie próbuje zrobić już tydzień i nic....

#include <iostream>
#include <cstdlib>
using namespace std;

struct plyta
{
int wartosc;
int wysokosc;
};

class BST
{
private:
struct node
{
node parent;
node
left;
node right;
int data;
};
node
root;

public:
    BST()
    {
       root = NULL;
    }

    bool isEmpty() const { return root==NULL; }
    int wstawiaj_plyty(plyta,node*);
    int wstawiaj(plyta);
    void print_inorder();
    void inorder(node*);
    void insert(int);
    void remove(int);
    void wybierz(int,int);

};

// Smaller elements go left
// larger elements go right
void BST::insert(int d)
{
node t = new node;
node
parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;

// is this a new tree?
if(isEmpty()) root = t;
else
{
    //Note: ALL insertions are as leaf nodes
    node* curr;
    curr = root;
    // Find the Node's parent
    while(curr)
    {
        parent = curr;
        if(t->data > curr->data) curr = curr->right;
        else curr = curr->left;
    }

    if(t->data < parent->data)
       parent->left = t;
    else
       parent->right = t;
}

}

void BST::wybierz( int l, int r)
{
int tmp;
if(l<r)
{
int s=(l+r)/2;
tmp=s;
insert(tmp);
wybierz(l,s-1);
wybierz(s+1,r);
}
if(l==r)
insert(r);
}

void BST::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
return;
}
node curr;
node
parent;
curr = root;

while(curr != NULL)
{
     if(curr->data == d)
     {
        found = true;
        break;
     }
     else
     {
         parent = curr;
         if(d>curr->data) curr = curr->right;
         else curr = curr->left;
     }
}
if(!found)
    return;

     // 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children

// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL

&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}

     //We're looking at a leaf node
     if( curr->left == NULL && curr->right == NULL)
{
    if(parent->left == curr) parent->left = NULL;
    else parent->right = NULL;
             delete curr;
             return;
}

//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
    node* chkr;
    chkr = curr->right;
    if((chkr->left == NULL) && (chkr->right == NULL))
    {
        cout<<endl<<"USUWAM: "<<d;
        curr = chkr;
        delete chkr;
        curr->right = NULL;
    }
    else // right child has children
    {
        //if the node's right child has a left child
        // Move all the way down left to locate smallest element

        if((curr->right)->left != NULL)
        {
            node* lcurr;
            node* lcurrp;
            lcurrp = curr->right;
            lcurr = (curr->right)->left;
            while(lcurr->left != NULL)
            {
               lcurrp = lcurr;
               lcurr = lcurr->left;
            }
    curr->data = lcurr->data;
            delete lcurr;
            lcurrp->left = NULL;
       }
       else
       {
           node* tmp;
           tmp = curr->right;
           curr->data = tmp->data;
       curr->right = tmp->right;
           delete tmp;
       }

    }
     return;
}

}

void BST::print_inorder()
{
inorder(root);
}

void BST::inorder(node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if(p->right) inorder(p->right);
}
else return;
}

int BST::wstawiaj(plyta p)
{
return wstawiaj_plyty(p,root);
}

int BST::wstawiaj_plyty(plyta p, node* x)
{
int tmp=0;
int k;
cout<<endl<<"Zaczynam szukać prowadnicy dla plyty: ("<<p.wartosc<<","<<p.wysokosc<<")";
while((x!=NULL)&&(x->data!=p.wysokosc))
{
cout<<endl<<"$$$$";
cout<<endl<<"Numer ostatniej prowadnicy, w której plyta sie miescila: "<<tmp;
if(x->data>p.wysokosc)
{
cout<<endl<<"Plyta ("<<p.wartosc<<","<<p.wysokosc<<")"<<"miesci sie w prowadnicy nr "<<x->data;
tmp=x->data;
x=x->left;
}
else
{
cout<<endl<<"Plyta ("<<p.wartosc<<","<<p.wysokosc<<")"<<"!NIE! miesci sie w prowadnicy nr "<<x->data;
x=x->right;
}
}
cout<<endl<<"^^^^^";
if(x->data==p.wysokosc)
{
cout<<endl<<"Wszedlem do IFA, gdzie znalazlem dokladnie taka sama prowadnice co plyte";
remove(p.wysokosc);
return p.wartosc;
}
else
{
if(tmp==0)
{

        return tmp;
    }
    else
    {
        remove(tmp);
        return p.wartosc;
    }
}

}

void scal(plyta t[], int l, int s, int r)
{
int i=l;
int j=s+1;
int k=0;
plyta tmp[r-l+1];

while(i<=s&&j<=r)
{
    if(t[i].wartosc>t[j].wartosc)
    {
        tmp[k]=t[i];
        i++;
    }
    else
    {
        if(t[i].wartosc==t[j].wartosc)
        {
            if(t[i].wysokosc<=t[j].wysokosc)
            {
                tmp[k]=t[i];
                i++;
            }
            else
            {
                tmp[k]=t[j];
                j++;
            }
        }
        else
        {
            tmp[k]=t[j];
            j++;
        }
    }
    k++;
}

while(i<=s)
{
    tmp[k]=t[i];
    i++;
    k++;
}

while(j<=r)
{
    tmp[k]=t[j];
    j++;
    k++;
}
int a=0;
for(int n=l;n<=r;n++)
{
    t[n]=tmp[a];
    a++;
}

}

void merge_sort(plyta t[], int l, int r)
{
if(l<r)
{
int s=(l+r)/2;
cout<<endl<<"lewy="<<l;
cout<<endl<<"prawy="<<r;
cout<<endl<<"srodek="<<s;
merge_sort(t,l,s);
merge_sort(t,s+1,r);
scal(t,l,s,r);
for(int i=l;i<=r;i++)
{
cout<<endl<<t[i].wartosc<<" "<<t[i].wysokosc;
}
cout<<endl<<"-----------------------";
}
}

int main()
{
BST prowadnice;
int n,m,suma=0;
cin>>m>>n;
plyta t[n];
for(int i=0;i<n;i++)
{
cin>>t[i].wartosc>>t[i].wysokosc;
}
cout<<endl<<"\\\";
merge_sort(t,0,n-1);
cout<<endl<<"\\\";
for(int i=0;i<n;i++)
{
cout<<endl<<t[i].wartosc<<" "<<t[i].wysokosc;
}
prowadnice.wybierz(1,m);
prowadnice.print_inorder();
cout<<endl<<"-------------";
for(int i=0;i<n;i++)
{
cout<<endl<<"usiluje wstawic: "<<t[i].wartosc<<" "<<t[i].wysokosc;
suma=suma+prowadnice.wstawiaj(t[i]);
cout<<endl<<"suma="<<suma<<endl<<"*";
prowadnice.print_inorder();
}
cout<<endl<<"suma ostateczna="<<suma;

return 0;

}

Pozostało 580 znaków

2012-03-04 18:14
0

Prowadnic na statku jest 5. Drzewo z nich skonstruowany powinno wyglądać tak:
3
/ \
1 4
\ /
2 5

Drzewo nie powinno tak wyglądać, tylko tak:
3
/ \
1 4
\ \
2 5

Poza tym, ja zrobiłbym to mniej więcej tak:

BST::node* find( BST::node* root, const int d )
{
    if( !root )
        return NULL;

    BST::node* temp;
    if( root->data == d )
        return root;
    else if( root->data > d )
        temp = find( root->left, d );
    else
        temp = find( root->right, d );

    return temp;
}

void BST::remove( const int d )
{
    node* curr = find( root, d );

    if( curr && curr->right )
    {
        node* temp = curr->right;
        while( temp->left )
            temp = temp->left;

        temp->left = curr->left;
        root = curr->right;
    }
    else
        root = curr->left;

    delete curr;
}

Tłumacząc kod "na misia" wydaje się, że działa prawidłowo, ale nie daję 100% gwarancji, kod jest pisany na sucho bez sprawdzenia jego działania.

EDIT: PoEbało mi się, działa tylko dla roota. Dla pozostałych węzłów nie działa. Zaraz coś wykminię.


Gdy się nie wie, co się robi, to dzieją się takie rzeczy, że się nie wie, co się dzieje ;-)
edytowany 4x, ostatnio: MJay, 2012-03-04 18:31

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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