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;
}