Drzewo BST - prośba o wskazanie błędów i pomoc w ich rozwiązaniu

0

witam
otoz dla cwiczen pisze sobie w c++ klase drzewo BST i mam takie pytanie do bardziej doswiadczonych programistow: czy przy odwolywaniu sie do elementow (ale takze przesylaniu ich do funkcji, metod) wektora (ktory zawiera elementy klasy wezel) wykorzystywac indexy tych elementow czy lepiej korzystac ze wskaznikow do klasy wezel. Wektor ten jest elementem skladowym tej klasy,

interesuje mnie czym roznilyby sie te dwa podejscia (szybkosc dzialania i inne roznice).
z gory dzieki za odp ;)

1
template <class T>
class BST_tree {
private:
      struct node {
              node *left;
              node *right;
              T val;
              node () : left(nullptr), right(nullptr) { }
              node (T value) : left(nullptr), right(nullptr), val(value) { }
      };
      node *root;
      ..........
}

Tak najsensowniej by to wyglądało bez własnego komparatora i alokatora. Osobiście odradzam stosowania wektora tutaj. Po pierwsze: szybkość i pamięc. Oczywistym jest, ze rozwiązanie up jest pod tymi względami lepsze. Po drugie: wektor tutaj jest imo bugable.
Oczywiście struktura node jest Twoja i tylko Twoja. Z użytkownikiem komunikujesz sie poprzez T, tzn: zwracasz mu T, przyjmujesz od niego T, itd. a wewnątrz funkcji tworzysz sobie node i na tym działasz.

3
pingwindyktator napisał(a):

Osobiście odradzam stosowania wektora tutaj. Po pierwsze: szybkość i pamięc.

A o czymś takim jak cache-friendly data structure słyszał? To nie BST ale widziałeś boost::flat_set, przeglądałeś kod Loki/eastl?

0

To bardzo zależy od tego jak będziesz używał tego drzewa. Czy ma się rozrastać, czy ma się zmniejszać, jakiej objętości typ danych węzeł trzyma i w jaki sposób (czy na stosie czy na stercie). A jak jeszcze okaże się się pracujesz w deficycie pamięci albo na węzłach tylko do odczytu albo konieczne jest "upychanie" w pamięci... to skończy się na własnym alokatorze pamięci :-/
Podaj więcej szczegółów. Ogólnie.. najpierw implementacja a na podstawie sposobu używania i ograniczeń, optymalizacja :-)

0

interesuje mnie czym roznilyby sie te dwa podejscia (szybkosc dzialania i inne roznice).

w 32-bitowym kodzie nie spodziewałbym się mierzalnej różnicy w wydajności.
w 64-bitowym, jeśli wskaźnik ma 64 bity a indeks miałby 32 - teoretycznie mała różnica może się pojawić, z powodu większego obciążenia cache procesora. ale tak tylko gdybam - faktyczna różnica może się okazać zupełnie nieistotna.

0

Uzywanie pointerow moze zablokowac pewne optymalizacje [patrz pointer aliasing]

0

moglby ktos obejrzec moj kod i go ocenic -oczywiscie jesli ma troche czasu. ;)
z gory zaznaczam jestem licealistą i w wielu miejscach moglem porobic glupie bledy - wiec prosze, jesli mozna bez hate'u. jesli widzisz co jest zle to pisz wprost, chcialbym wiedziec co napisalem zle, gdzie sa braki w mojej wiedzy, itd.
bede wdzieczny za kazdy konstruktywny komentarz ;)

#include <iostream>
#include <vector>

using namespace std;

struct tx
{
    string text;
    int key;

    tx()
    {
        text="";
        key=0;
    }

    tx(string t)
    {
        text=t;
        key=0;
        for(int i=0;i<text.length();i++)
        {
            key+=text[i];
        }
    }
};

template <class T>
class BST_tree {
private:
    struct node
    {
        node *p;
        node *left;
        node *right;
        T value;
        int key;

        node(T val,int k=0) : p(0), left(0), right(0)
        {
            key=k;
            value=val;
        }
    };

    node *root;

    void inorder_tree_walk(node *x)
    {
        if(x!=0)
        {
            inorder_tree_walk((*x).left);
            cout<<(*x).key<<" ";
            inorder_tree_walk((*x).right);
        }
    }

    void preorder_tree_walk(node *x)
    {
        if(x!=0)
        {
            cout<<(*x).key<<" ";
            inorder_tree_walk((*x).left);
            inorder_tree_walk((*x).right);
        }
    }

    void postorder_tree_walk(node *x)
    {
        if(x!=0)
        {
            inorder_tree_walk((*x).left);
            inorder_tree_walk((*x).right);
            cout<<(*x).key<<" ";
        }
    }

    node *tree_search(int k,node *x)
    {
        while(x!=0 && k!=(*x).key)
        {
            if(k<(*x).key)
                x=(*x).left;
            else
                x=(*x).right;
        }
        return x;
    }

    node *tree_minimum(node *x)
    {
        while((*x).left!=0)
            x=((*x).left);
        return x;
    }

    node *tree_maximum(node *x)
    {
        while((*x).right!=0)
            x=((*x).right);
        return x;
    }

    node *tree_successor(node *x)
    {
        if((*x).right!=0)
            return tree_minimum((*x).right);
        node *y;
        y=(*x).p;

        while(y!=0 && x==(*y).right)
        {
            x=y;
            y=(*y).p;
        }
        return y;
    }

    node *tree_predecessor(node *x)
    {
        if((*x).left!=0)
            return tree_maximum((*x).left);
        node *y;
        y=(*x).p;

        while(y!=0 && x==(*y).left)
        {
            x=y;
            y=(*y).p;
        }
        return y;
    }

    void tree_insert(node *z)
    {
        node *y;
        y=0;
        node *x;
        x=root;

        while(x!=0)
        {
            y=x;
            if((*z).key<(*x).key)
                x=(*x).left;
            else
                x=(*x).right;
        }

        (*z).p=y;

        if(y==0)
        {
            root=z;
        }
        else if((*z).key<(*y).key)
            (*y).left=z;
        else
            (*y).right=z;
    }


public:
    BST_tree()
    {
        root=0;
    }

    void inorder_tree_walk()
    {
        inorder_tree_walk(root);
    }

    void postorder_tree_walk()
    {
        postorder_tree_walk(root);
    }

    void preorder_tree_walk()
    {
        preorder_tree_walk(root);
    }

    T tree_search(int key)
    {
        node *x;
        x=tree_search(key,root);
        return (*x).value;
    }

    T tree_minimum()
    {
        node *x;
        x=tree_minimum(root);
        return (*x).T;
    }

    T tree_maximum()
    {
        node *x;
        x=tree_maximum(root);
        return (*x).T;
    }

    T tree_successor(int key)
    {
        node *x;
        x=tree_successor(tree_search(key));
        return (*x).T;
    }

    T tree_predecessor(int key)
    {
        node *x;
        x=tree_predecessor(tree_search(key));
        return (*x).T;
    }

    void tree_insert(T nw,int key=0)
    {
        node z(nw,key);
        node *x;
        x=&z;
        tree_insert(x);
    }


};

int main()
{

    BST_tree<tx>Tree;

    tx a("aaa");
    tx b("bbb");
    tx c("ccc");
    tx d("ddd");
    tx e("eee");
    tx f("fff");
    tx g("ggg");
    tx h("hhh");

    Tree.tree_insert(a,a.key);
    Tree.tree_insert(b,b.key);
    Tree.tree_insert(c,c.key);
    Tree.tree_insert(d,d.key);
    Tree.tree_insert(e,e.key);
    Tree.tree_insert(f,f.key);
    Tree.tree_insert(g,g.key);
    Tree.tree_insert(h,h.key);

    tx x;
    x=Tree.tree_search(443);
    cout<<x.key<<x.text;

    Tree.preorder_tree_walk();

    return 0;
}


 

w mainie gdy uruchamiam tree_search to wywala mi jakies krzaczki w konsoli, a preorder_tree_walk wywala mi blad.
z gory dzieki za pomoc ;)

1
  1. Staraj się używac list inicjalizacyjnych
  2. 0 jako NULL nie jest dobrym pomysłem. Standard mówi, zeby używać nullptr
void preorder_tree_walk (node *x) {
        if (x != 0) {
            cout << (*x).key << " ";
            inorder_tree_walk((*x).left);
            inorder_tree_walk((*x).right);
        }
    }
  1. (*x).left to utrudnianie sobie życia. Użyj x->left
  2. To wszystko jest źle zaprojektowane. Nie powinieneś trzymać dwóch rodzaji każdej z funkcji.
  3. Przez punkt 5 masz głupoty w kodzie, np:
    node *tree_maximum(node *x)
    {
        while((*x).right!=0)
            x=((*x).right);
        return x;
    }

wcale nie zwraca maximum dla x != root, a nazwa tak sugeruje

T tree_minimum () {
        node *x;
        x = tree_minimum(root);
        return (*x).T;
    }

czym jest x->T ?

  1. void tree_insert (T nw, int key = 0)
    Przyjmuj nw przez referencje, bo jeśli T jest bardzo dużym obiektem, to zostanie on skopiowany. Ewentualnie możesz dopisać move operator do node
void tree_insert (T nw, int key = 0) {
        node z(nw, key);
        node *x;
        x = &z;
        tree_insert(x);
    }

niepotrzebnie mieszasz.
10. node *tree_search (int k, node *x) może zwrócić nullptr, natomiast Ty w dwóch miejscach odwołujesz sie do pól wskaźnika, który ta funkcja zwróciła. nullptr jednak nie zawiera tych pól i nie mozesz zrobic nullptr->value, to oczywiste chyba.

0

napisalem nowy kod i mam problem.
wklejam kod

#include <iostream>
#include <stack>

using namespace std;

struct st
{
    string text;
};

template<class T>
class BST_Tree
{
private:
    struct node
    {
        node *left;
        node *right;
        node *p;
        T value;
        T* pointer_value;
        int key;

        node(T &val,int k=0) : left(nullptr), right(nullptr), p(nullptr), value(val), key(k), pointer_value(&value) {}
    };

    node *root;

public:
    BST_Tree() : root(nullptr) {}

    void tree_value_insert(T &nw_val,int k)
    {
        node *y;
        y=nullptr;
        node *x;
        x=root;
        node z(nw_val,k);

        while(x)
        {
\\tresc tej petli nigdy sie nie wykonuje i nie wiem dlaczego

            y=x;
            if(z.key<x->key)
            {
                x=x->left;
            }
            else
            {
                x=x->right;
            }
        }
        z.p=y;

        if(!y)
        {
            root=&z;
        }
        else if(z.key<y->key)
        {
//tresc tego elseif tez sie nie wykonuje i nie wiem dlaczego
            y->left=&z;
        }
        else
        {
            y->right=&z;
        }
    }



};

int main()
{
    BST_Tree<st>Tr;

    st a,b,c,d,e,f;

    a.text="a";
    b.text="b";
    c.text="c";
    d.text="d";
    e.text="e";
    f.text="f";

    Tr.tree_value_insert(a,10);
    Tr.tree_value_insert(b,1);
    Tr.tree_value_insert(c,0);
    Tr.tree_value_insert(d,2);
    Tr.tree_value_insert(e,12);
    Tr.tree_value_insert(f,11);

    st *g;
    g=Tr.tree_key_search(1);
    if(g)
        cout<<g->text;



    return 0;
}

 

w kodzie oznaczylem miejsca z problemem komentarzem co nie dziala, moglby mi to ktos wytlumaczyc i lub powiedziec jak naprawic?

1

Nie możesz przypisywać referencji do zmiennej lokalnej.

0
 

#include <iostream>
#include <stack>

using namespace std;

struct st
{
    string text;
};

template<class T>
class BST_Tree
{
private:
    struct node
    {
        node *left;
        node *right;
        node *p;
        T value;
        T* pointer_value;
        int key;

        node(T &val,int k=0) : left(nullptr), right(nullptr), p(nullptr), value(val), key(k), pointer_value(&value) {}
    };

    node *root;

public:
    BST_Tree() : root(nullptr) {}

    T* tree_key_search(int k) //ma zwracac wskaznik do obiektu stalego
    {
        if(root==nullptr)
        {
            return nullptr;
        }

        node *x;
        x=root;

        while(x!=nullptr && k!=x->key)
        {
            if(k < x->key)
            {
                x=x->left;
            }
            else
            {
                x=x->right;
            }
        }
        if(x)
            return x->pointer_value;
        return nullptr;
    }

    void inorder_tree_walk()
    {
        stack<node*>S;
        node *cp;

        cp=root;

        while(!S.empty() || cp!=nullptr)
        {
            if(cp!=nullptr)
            {
                S.push(cp);
                cp=cp->left;
            }
            else
            {
                cp=S.top();
                S.pop();
                //tu przetwarzam wezel
                cout<<cp->key<<" ";


                cp=cp->right;
            }
        }
    }

    void preorder_tree_walk()
    {
        stack<node*>S;
        node *v;

        v=root;

        S.push(v);

        while(!S.empty())
        {
            v=S.top();
            S.pop();
            //tu przetwarzam wezel
            cout<<v->key<<" ";

            if(v->right)
                S.push(v->right);
            if(v->left)
                S.push(v->left);
        }
    }

    void postorder_tree_walk()
    {
        stack<node*>S;

        S.push(root);

        node *cp,*pp,*up;

        pp=nullptr;

        while(!S.empty())
        {
            cp=S.top();
            if(pp==nullptr || pp->left==cp || pp->right=cp)
            {
                if(cp->left)
                    S.push(cp->left);
                else if(cp->right)
                    S.push(cp->right);
            }
            else if(cp->left==pp)
            {
                if(cp->right)
                    S.push(cp->right);
            }
            else
            {
                up=S.top();
                S.pop();

                cout<<up->key<<" ";
            }
        pp=cp;
        }

    }

    T* tree_key_minimum()
    {
        node *x;
        x=root;
        while(x->left)
            x=x->left;

        return x->pointer_value;
    }

    T* tree_key_maximum()
    {
        node *x;
        x=root;

        while(x->right)
            x=x->right;

        return x->pointer_value;
    }

    void tree_value_insert(T &nw_val,int k)
    {
        node *y;
        y=nullptr;
        node *x;
        x=root;
        node z(nw_val,k);

        while(x)
        {
            y=x;
            if(z.key<x->key)
            {
                x=x->left;
            }
            else
            {
                x=x->right;
            }
        }
        z.p=y;

        if(!y)
        {
            root=&z;
        }
        else if(z.key<y->key)
        {
            y->left=&z;
        }
        else
        {
            y->right=&z;
        }
    }



};

int main()
{
    BST_Tree<st>Tr;

    st a,b,c,d,e,f;

    a.text="a";
    b.text="b";
    c.text="c";
    d.text="d";
    e.text="e";
    f.text="f";

    Tr.tree_value_insert(a,10);
    Tr.tree_value_insert(b,1);
    Tr.tree_value_insert(c,0);
    Tr.tree_value_insert(d,2);
    Tr.tree_value_insert(e,12);
    Tr.tree_value_insert(f,11);

    st *g;
    g=Tr.tree_key_search(10);
    if(g)
        cout<<g->text;

    return 0;
}


1

No przecież nadal masz tam referencję do zmiennej lokalnej w tree_value_insert.

1
node z(nw_val,k);
.... 
if(!y)
{
    root=&z;
}

z jest zmienną lokalną, więc zniknie po wyjściu z metody. Czyli Twój root będzie wskazywać na nicość.

Przy okazji nie wiem czemu piszesz coś takiego:

node *y;
y=nullptr;

zamiast

node* y = nullptr;

które jest krótsze (fakt), ładniejsze (moja opinia) i poprawniejsze (zawsze należy inicjalizować zmienną przy deklaracjidefinicji jeśli to możliwe).

0

dzieki wszystkim w koncu dziala ;) jak bede mial jakies dalsze problemy to napisze bo znajac zycie na tym sie nie skonczy ;)

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