Drzewo BST, suma elementów drzewa

Odpowiedz Nowy wątek
2011-12-23 19:05
kamil
0

Witam,
mam taką oto klasę:


class node
{
public:
    int data;
    node* left;
    node* right;
    int sum; // przechowuje sume elementow

    node();
    node(int);
    ~node();
};

Potrzebuję napisać funkcję Suma(), która policzy mi sumę elementów w danym drzewie BST w czasie średnim O(logn) (czyli rekurencja po całym drzewie odpada). Moja prowadząca powiedziała, żeby przechowywać sumę elementów w osobnym polu klasy jednak nie wiem w jaki sposób miałoby to pomóc i bynajmniej jak to zrobić.

Mam do dyspozycji jeszcze funkcję insert:


void insert(node* root, int val)
{
    node* p;
    node* r;

    r = root; p = NULL;
    while(r != NULL)
    {
        if(r -> data == val) return;
        p = r;
        if(r -> data < val) r = r -> right;
        else r = r -> left;
    }
    r = new node;
    r -> data = val;
    if(p == NULL) root = r;
    else
    {
        if(p -> data < val) p -> right = r;
        else p -> left = r;
    }
}

Napisałem taką metodę:


void node::setSum()
{
    int s = 0;
    if(left != NULL) s += left->data;
    if(right != NULL) s += right->data;
    sum = s;
}

Ale nie działa poprawnie, bo wywołanie root->setSum() sumuje mi nie to co potrzebuję :/

Byłbym wdzięczny za pomoc,
pozdrawiam

Pozostało 580 znaków

2011-12-23 19:22
0

Drzewo ma n elementów. Nie da się ich zsumować (rozumiem że chodzi tu o wartości przechowywane w węzłach) w czasie mniejszym niż n i ktokolwiek kto uważa inaczej jest po prostu śmieszny. Opcje są więc dwie: nie zrozumiałeś polecenia albo prowadząca nie uważała na matematyce.
Chyba że chodziło o to żeby na przykład przechowywać informacje o tym jaka jest suma poddrzew dla danego węzła, wtedy po dodaniu nowego węzła wyliczenie nowej sumy faktycznie zabierze nam O(logn) czasu, bo po dodaniu liścia trzeba iść w górę aż do korzenia i aktualizować sumy.
Podsumowując: zamiast wstawić bezużyteczny kod, napisz dokładnie JAKIE JEST POLECENIE.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2011-12-23 19:23

Pozostało 580 znaków

2011-12-23 19:28
kamil
0
Shalom napisał(a)

Chyba że chodziło o to żeby na przykład przechowywać informacje o tym jaka jest suma poddrzew dla danego węzła, wtedy po dodaniu nowego węzła wyliczenie nowej sumy faktycznie zabierze nam O(logn) czasu, bo po dodaniu liścia trzeba iść w górę aż do korzenia i aktualizować sumy.

Dosłownie o to chodzi, przepraszam, że niejasno się wyraziłem.

Pozostało 580 znaków

2011-12-23 20:12
0

No to aktualizacja tego powinna następować w chwili dodawania nowego węzła. W chwili kiedy wchodzisz do danego węzła dodajesz wartość z tego dodawanego węzła do sumy dla tego węzła.
Twoja funkcja setSum żeby była poprawna musiałby robić:

        int s = 0;
        if(left != NULL) s += left->sum;
        if(right != NULL) s += right->sum;
        sum = s;

Przy czym żeby jej używać to musiałbyś wywoływać ją od liścia do korzenia a nie widzę żeby twój node znał wskazanie na rodzica, a bez tego nie da się tak przechodzić drzewa.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2011-12-23 21:57
uuu
0

albo wykorzystać pole statyczne i w konstruktorze inkrementować je, a wywołując destruktor dekrementować.

Pozostało 580 znaków

2011-12-23 22:25
kamil
0

Poprawiłem klasę, dodając wskaźnik na rodzica, a czy mógłbyś opisać w jaki sposób przechodzić po drzewie? Kod postaram się napisać samodzielnie, ale sama idea nie jest dla mnie jasna.

Dzięki

Pozostało 580 znaków

2011-12-24 00:01
0

Ok w chwili dodawania nowego elementu (tzn na samym końcu metody insert, jak już jesteś na samym dole drzewa) robisz coś takiego:

  • załóżmy że wartość dla tego nowe węzła jest w zmiennej value
  • suma w tym nowym węźle = value (bo suma dla liścia to jest tylko to co on sobie sam przechowuje)
  • następnie przeskakujesz na rodzica tego elementu i robisz suma+=value (bo suma zwiększyła się o ten nowy węzeł)
  • powtarzasz poprzedni krok aż rodzic == NULL (czyli aż doszliśmy do korzenia)
    Średnia wysokość drzewa to logn, więc od liscia do korzenia wykonamy maksymalnie tyle skoków (średnia, bo drzewo nie jest zrównoważone!).

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2011-12-24 00:01

Pozostało 580 znaków

2011-12-24 00:18
kamil
0

Napisałem taką funkcję:


void insert(node** root, int val)
{
    node* temp, *prev;
    prev = new node;
    temp = find(*root, &prev, val);
    if (temp != NULL)
        return;
    temp = new node;
    temp->left = temp->right = NULL;
    temp->data = val;
    temp->sum = val; // suma w nowym wezle to wartość przechowywana w tym wezle

    if (prev == NULL) // jezeli rodzic jest pusty...
    {
        *root = temp; // ...to nowy wezel uczyn korzeniem.
    }
    else
    {
        if (prev->data < val)
        {
            prev->right = temp;
            prev->sum += prev->right->data;
        }
        else
        {
            prev->left = temp;
            prev->sum += prev->left->data;
        }
    }
}

Gdy wywołam w mainie:

node* root = NULL;

    insert(&root,5);
    insert(&root,7);
    insert(&root,11);

To dodaje mi tylko 5 i 7, natomiast pomija 11...

PS. funkcji find nie wrzucam, bo jest w porządku i wiadomo jak działa.

Pozostało 580 znaków

2011-12-24 00:30
0

Ale to jest bez sensu. Co ten find() niby zwraca skoro node który do niego przekazujesz nie ma ustawionej wartości? o_O
Co to niby jest:

prev = new node;

?
Nic nie zrozumiałeś! Tamta funkcja była dobra! Miałeś dopisać tylko kilka linijek na końcu! Poza tym aktualizowanie wartości sumy masz robić OD LIŚCIA DO KORZENIA! I masz aktualizować TYLKO o wartość TEGO JEDNEGO, NOWEGO WĘZŁA a nie o wartość w węźle który jest synem.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2011-12-24 00:31

Pozostało 580 znaków

2011-12-24 00:52
kamil
0

Czy jest sens unosić się tak? Na zajęciach dostałem taki plik, który miałem zmodyfikować:


#include <stdlib.h>
#include <iostream>

using namespace std;

//struktura obrazujaca wezel
typedef struct _node
{
    int data;
    struct _node* left;
    struct _node* right;
}node;

//wyszukiwanie elementu w drzewie
//root - korzen drzewa
//prev - pod ta zmienna zostanie zapisany rodzic wyszukiwanego wezla (jezeli wystepuje w drzewie)
//val - wyszkiwana wartosc
node* find(node* root, node** prev, int val)
{
    *prev = NULL;
    node* temp = root;
    while( temp != NULL)
    {
        if (temp->data == val)
            return temp;
        *prev = temp;
        if (temp->data < val)
            temp = temp->right;
        else
            temp = temp->left;
    }
    return NULL;
}

//wstawianie elementu do drzewa
//root - korzen drzewa
//val - wstawiana wartosc
void insert(node** root, int val)
{
    node* temp, *prev;
    prev = (node*)malloc(sizeof(prev));
    temp = find(*root, &prev, val);
    if (temp != NULL)
        return;
    temp = (node*)malloc(sizeof(node));
    temp->left = temp->right = NULL;
    temp->data = val;
    if (prev == NULL)
    {
        *root = temp;
    }
    else
    {
        if (prev->data < val)
            prev->right = temp;
        else
            prev->left = temp;
    }
}

//wypisywanie drzewa
//root - korzen
void print(node* root)
{
    if(root == NULL)
        return;
    print(root->left);
    cout<<root->data<<endl;
    print(root->right);
}

Prowadząca powiedziała, żeby wiele nie zmieniać, a tamta wcześniejsza wersja insert() była z innego źródła. Wolę pracować na tej, żeby nie było potem problemów.

Pozostało 580 znaków

2011-12-24 01:50
0
#include <stdlib.h>
#include <iostream>

using namespace std;

typedef struct _node
{
    int data;
    int sum;
    struct _node* left;
    struct _node* right;
    struct _node* parent;
} node;

node* find(node* root, node** prev, int val)
{
    *prev = NULL;
    node* temp = root;
    while( temp != NULL)
    {
        if (temp->data == val)
            return temp;
        *prev = temp;
        if (temp->data < val)
            temp = temp->right;
        else
            temp = temp->left;
    }
    return NULL;
}

void insert(node** root, int val)
{
    node* temp, *prev;
    temp = find(*root, &prev, val);
    if (temp != NULL)
    {
        return;
    }
    temp = (node*)malloc(sizeof(node));
    temp->left = temp->right = temp->parent = NULL;
    temp->data = val;
    temp->sum = val;
    if (prev == NULL)
    {
        *root = temp;
    }
    else
    {
        temp->parent = prev;
        if (prev->data < val)
        {
            prev->right = temp;
        }
        else
        {
            prev->left = temp;
        }
    }
    node* upstream = prev;
    while(upstream != NULL)
    {
        upstream->sum+=val;
        upstream = upstream->parent;
    }
}

void print(node* root)
{
    if(root == NULL)
        return;
    print(root->left);
    cout<<root->data<<" "<<root->sum<<endl;
    print(root->right);
}

int main()
{
    node* root = NULL;
    for(int i=1;i<10;i++){
        insert(&root,i);
    }
    print(root);
    // ładnie byłoby to wszystko potem zwolnić...
    return 0;
}

A za alokowanie pamięci tutaj:

prev = (node*)malloc(sizeof(prev));
temp = find(*root, &prev, val);

Powinna być chłosta dla tego kto to napisał. Doskonały przykład z serii "jak zrobić wyciek pamięci". Alokujemy sobie pamięć po to tylko żeby za chwilę o niej zapomnieć bo pod ten wskaźnik zaraz przypisujemy coś innego ;]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

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