Drzewo BST, suma elementów drzewa

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

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.

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.

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.

0

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

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

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!).
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.

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.

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.

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

0

Też jestem raczej zwolennikiem dbania by nie doszło do wycieków pamięci, no ale kod nie mój, więc nie będę już tego poprawiał, bo nie o to chodziło w poleceniu. Dzięki za pomoc!

Pozdrawiam.

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