Witam (pisasłem wcześniej o tym ale już poprawiłem problem, i zmieniłem classy, gdyż są jeszcze dlamnie za trudne:/), i mam problem bo wszystko ładnie się kompiluje ale ostatecznie nie działa wyskakuje [Linker error] Unresolved external '__InitVCL........
[Linker error] Unresolved external '__ExitVCL........
Proszę FACHOWCÓW chociaż o rzucenie okiem :)
/*
--------------------------------------------------------------------------------
rbt_unit.cpp
--------------------------------------------------------------------------------
*/
#include "rbt.h"
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
RBnode * a=0;
int n;
cin>>n;
for(int i=0;i<n;i++)
{ RBinsert(a,i);
a->red=false;
RBprzechodzi(a);
hb(a);
cout<<endl;
}
cout<<szukaj(a,15)->key<<endl;
for(int i=1;i<n;i++)
{ cout<<"usuwam "<< i<<endl;
RBdel(a,i);
cout<<"usunięte "<< i<<endl;
RBprzechodzi(a);
cout<<endl;
}
system("pause"); return 0;
}
/*
--------------------------------------------------------------------------------
rbt.cpp
--------------------------------------------------------------------------------
*/
#include <cstdlib>
#include <iostream>
#include "rbt.h"
using namespace std;
RBnode* szukaj(RBnode * a, int x)
{while(a && a->key !=x)
a= x<a->key ? a->left : a->right;
return a;
}
void RBprzechodzi (RBnode *a)
{if(a)
{ cout<<(a->red? '(' : '[');
RBprzechodzi(a->left);
cout<< a->key ;
RBprzechodzi (a->right);
cout<<(a->red ? ')' : ']');
}
}
int hb(RBnode *a)
{if(a)
return !a->red + max( hb(a->left), hb(a->right) );
else
return 0;
}
int minkey(RBnode * a)
{ while(a->left) a=a->left;
return a->key;
}
void rot_r(RBnode *&a)
{bool kolor=a->red;
a->red=a->left->red;
a->left->red=kolor;
RBnode * n=a->left;
a->left=n->right;
n->right=a;
a=n;
}
void rot_l(RBnode *&a)
{bool kolor=a->red;
a->red=a->right->red;
a->right->red=kolor;
RBnode * n=a->right;
a->right=n->left;
n->left=a;
a=n;
}
// RBinsert(a,x) zwraca następujące wartości
// 0 - wszystko jest ok
// 1 - po wstawieniu 'x' węzeł 'a' stał się czerwony, ale ma czarne dzieci
// 2 - po wstawieniu 'x' węzły 'a' oraz 'a->l' są czerwone
// 3 - po wstawieniu 'x' węzły 'a' oraz 'a->r' są czerwone
// dzięki temu wiadomo jak po wywołaniu RBinsert poprawiać drzewo
int RBinsert(RBnode *& a,int x)
{ if(a==NULL)
{a=new RBnode(x);
return 1;
}
if( x < a -> key )
{int res=RBinsert(a->left,x);
if(res) //
{if(a->right && a->right->red)
{if(res>1) // przypadek 1 (przekolorowanie)
{a->left->red=a->right->red=false; a->red=true; return 1;
}
}
else
switch(res)
{case 2:rot_l(a->left); //przypadek 2
case 3:rot_r(a);return 0; //przypadek 3
case 1:if(a->red) return 3;
}
}
}
else
{int res=RBinsert(a->right,x);
if(res)
{if(a->left && a->left->red)
{if(res>1) //przypadek 1 (przekolorowanie)
{a->right->red=a->left->red=false; a->red=true; return 1;
}
}
else
switch(res)
{case 3:rot_r(a->right); //przypadek 2
case 2:rot_l(a);return 0; //przypadek 3
case 1:if(a->red) return 2;
}
}
}
return 0; // oznacza, że wszystko jest już ok
}
// poprawianie drzwa w przypadkach (b) (c) lub (d)
// zwraca 1 jeśli po poprawieniu węzeł a jest podwójnie czarny
int fix_l(RBnode * &a )
{ RBnode * t=a->right;
if(! (t->left && t->left->red)&& ! (t->right && t->right ->red) ) //przypadek (b)
{ t->red=true; // przekolorowanie
if(! a->red ) // jeśli 'a' był czarny
return 1; // to teraz będzie podwójnie czarny
else
a->red=false; //jeśli był czerwony, to staje się czarny
}
else
{
if (! (t->right && t->right->red) ) // przypadek (c)
rot_r(a->right); // sprowadzamy do przypadku (d)
rot_l(a); // przypadek (d)
a->right->red=false;
}
return 0; // w pozostałych przypadkach algorytm kończy działanie
}
// poprawianie drzwwa w przypadkach (b) (c) lub (d)
// zwraca 1 jeśli po poprawieniu węzeł a jest podwójnie czarny
int fix_r(RBnode * &a )
{ RBnode * t=a->left;
if( !(t->right && t->right->red) && !(t->left && t->left->red) ) //przypadek (b)
{ t->red=true; //przekolorowanie
if(! a->red ) // jeśli 'a' był czarny
return 1; // to teraz będzie podwójnie czarny
else
a->red=false; //jeśli był czerwony, to staje się czarny
}
else
{if (! (t->left && t->left->red)) // przypadek (c)
rot_l(a->left); // sprowadzamy do przypadku (d)
rot_r(a); // przypadek (d)
a->left->red=false;
}
return 0;
}
// zwraca 1 jeśli węzeł 'a' po usunięciu 'x' stał się "podwójnie czarny"
int RBdel(RBnode *& a, int x)
{int res=-1;
if(! a){cout<< x <<" not in tree "<<endl; return 0;}
if (x<a->key)
{res=RBdel(a->left,x);
if(res) // a->l jest teraz podwójnie czarny
{if(a->right->red) // przypadek (a)
{rot_l(a); // sprowadzamy do jednego
fix_l(a->left); // pozostałych przypadków
return 0;
}
else
return fix_l(a); // pozostałe przypadki
}
}
else
if (x>a->key)
res=RBdel(a->right,x);
else // x == a->key więc usuwamy a
if(a->left && a->right) // ale jest dwójka dzieci
{a->key=minkey(a->right); // więc zamazuję klucz 'a' jego następnikiem
res=RBdel(a->right,a->key); // i usuwam następnika
}
if(res>0) // a->r jest teraz podwójnie czarny
{if(a->left->red) // przypadek (a)
{rot_r(a); // sprowadzamy do jednego
fix_r(a->right); // z pozostałych przypadków
return 0;
}
else
return fix_r(a); // pozostałe przypadki
}
if(res<0) // x==a->key oraz 'a' ma co najwyżej 1 dziecko
{ // przeprowadzamy teraz faktyczne usunięcie węzła 'a'
bool isred=a->red; // zapamiętuję kolor usuwanego węzła
RBnode* t=a; // oraz jego adres
a=(a->left ? a-> left : a->right); // adopcja potomka przez dziadka
delete t; // zwolnienie pamięci
if( a && a->red) // jeśli potomek usuniętego jest czerwony
{a->red=isred; // to dziedziczy kolor usuniętego ojca
return 0; // i wszystko jest ok
}
else
return isred==false; // jeśli usunięty węzeł był czarny,
// a jego dziecko jest czarne (lub NULL)
// to a jest teraz podwójnie czarny
}
return 0; // w pozostałych przypadkach wszystko jest ok
}
/*
--------------------------------------------------------------------------------
rbt.h
--------------------------------------------------------------------------------
*/
#ifndef rb_H
#define rbt_H
template <class T>
inline T max(T a,T b)
{ return a>b ? a: b;
}
struct RBnode
{ int key;
bool red;
RBnode *left;
RBnode *right;
RBnode(int x):key(x),red(true),left(0),right(0){} ;
};
int minkey(RBnode * a);
void rot_r(RBnode *&a);
void rot_l(RBnode *&a);
int fix_l(RBnode * &a );
int fix_r(RBnode * &a );
RBnode *create_node( int x );
void RBprzechodzi (RBnode *a);
int hb(RBnode *a);
int RBinsert(RBnode *& a,int x) ;
int RBdel(RBnode *& a, int x);
RBnode *szukaj(RBnode * a, int x);
#endif/*
--------------------------------------------------------------------------------
rbt.h
--------------------------------------------------------------------------------
*/
#ifndef rb_H
#define rbt_H
template <class T>
inline T max(T a,T b)
{ return a>b ? a: b;
}
struct RBnode
{ int key;
bool red;
RBnode *left;
RBnode *right;
RBnode(int x):key(x),red(true),left(0),right(0){} ;
};
int minkey(RBnode * a);
void rot_r(RBnode *&a);
void rot_l(RBnode *&a);
int fix_l(RBnode * &a );
int fix_r(RBnode * &a );
RBnode *create_node( int x );
void RBprzechodzi (RBnode *a);
int hb(RBnode *a);
int RBinsert(RBnode *& a,int x) ;
int RBdel(RBnode *& a, int x);
RBnode *szukaj(RBnode * a, int x);
#endif