witam,
w jaki sposób proponujecie utworzenie drzewa powiedzmy binarnego w C++
0
0
Najprosciej? Tak:
map<klucz,wartosc> drzewko;
0
a w sposób taki, że piszę strukturę - chodzi mi o propozycję
0
Struktura z dwoma wskaznikami na te struktury -> left i right ;p
0
o_O Ban na wikipedię, googla i myślenie?
template <class T>
class BST{
Node<T>* root;
};
template <class T>
class Node{
Node<T>* left;
Node<T>* right;
T value;
};
?
@down w sumie racja, Node można wepchnąć spokojnie do środka
0
@Shalom, ja bym dał nawet:
template <typename T>
class BST {
class Node {
Node *left, *right;
T value;
} *root;
};
0
ok, zagnieżdżone klasy,(myślę że dobry sposób) ale po co?
skoro można to zrobić nawet jedną strukturą.
w takim razie w jaki sposób tworzyć obiekt klasy(pojedynczy węzeł, nazwą klasy "zewnętrznej" czy nazwą klasy zagnieżdżonej - a może efektywniej będzie robić klasę jedną z szablonem bez zagnieżdżeń?
0
root będzie obiektem klasy, Node - proponujecie, aby był zarezerwowany jako korzeń, zaś obiekty klasy Node jako podrzędne węzły
0
root to wskaźnik na obiekt klasy Node, tak jak każdy inny węzeł. Klasa BST reprezentuje obiekt całego drzewa, w końcu chciałeś C++, więc dostałeś propozycję obiektową.
0
w takim razie wskaźnik root nie jest mi potrzebny, bo po co?
na jakiej zasadzie odbywa się takie dodawanie do drzewa węzłów, przecież mogę ustawić dla obiektu *parent wskaźniki left i right
class Tree{
public:
Tree *left, *right;
int value;
};
main(){
Tree *parent, *lSyn, *pSyn;
parent = new Tree; //musze przydzielic pamiec
pSyn = new Tree;
lSyn = new Tree;
parent->left=lSyn; //podczepiam lewy węzeł
parent-> right = pSyn;// podczepiam prawy węzeł
teraz pasowałoby żeby pSyn tez miał potomków, powiedzmy na razie tylko lewego -znow musze tworzyc obiekt
jak zrealizować elastyczne dodawanie elementów, tak aby same wiedziały gdzie sie podczepic, nie wiem czy się jasno wyrazilem, ale zaproponujcie jakąs metodę :)
pozdrawiam
}
0
A czym się różni twoje rozwiazanie od naszego? Tylko tym że u ciebie zarówno drzewo jak i węzeł to Tree, bo jest trochę nielogiczne...
Lekcja na dziś: zasada jednej odpowiedzialności.
Jak to jak dodawać elementy? o_O Druga lekcja na dziś: drzewa BST, drzewa AVL, drzewa RB, drzewa Splay
W wersji najprostszej -> BST po prostu porównujesz sobie klucz wstawianego elementu z kluczem elementu na którym aktualnie jesteś i jeśli jest mniejszy to idziesz w lewo a jak większy to w prawo. Jak trafisz wreszcie ci koniec to wstawiasz.
http://qmatica.com/DataStructures/Trees/BST.html
http://people.ksp.sk/~kuko/bak/
0
Nasze się różni tym, że można je ładnie popakować i opisać funkcjami by mieć na przyszłość taką strukturę już gotową.
@Shalom: to że węzeł potraktujemy też jako drzewo jest jakoby częściowo logiczne, gdyż każdy węzeł jest jakoby nowym drzewem.
0
wielkie dzięki za linka, zaczynam rozumieć. Drzewo BST jest binarne drzewo poszukiwań, pewnie dlatego, że szybko można znaleźć szukaną wartość liczbową, zapewnia to struktura drzewa BST, o co chodzi z SPL, RB itd czy są to jakieś odmiany drzew binarnych a może odmiany drzew BST?
0
BST = Binary Search Tree, wiec odmiana drzewa binarnego to w zasadzie to samo co odmiana drzewa BST...
Masz w pierwszym aplecie który podałem trzy wersje drzewa -> AVL czyli drzewa zrównoważone (różnica w wysokości nie moze być większa niż 1 poziom), RB czyli drzewa czerwono-czarne też zrównoważone ale w inny sposób -> na każdej ścieżce korzeń-liść jest tyle samo węzłów czarnych, Splay to drzewa które reorganizują drzewo poprzez wyciągnięcie do korzenia elementu który nas interesuje -> dzięki temu elementy często używane są blisko korzenia i szybciej można do nich dojść.
Szybkość znalezienia klucza w drzewie zrównoważonym to log(n), bo tyle też ma wysokość drzewa.
0
Drzewo BST jest binarne drzewo poszukiwań, pewnie dlatego, że szybko można znaleźć szukaną wartość liczbową, zapewnia to struktura drzewa BST
Nic nie zapewnia niestety, pesymistyczna złożoność daje O(n) czyli tak samo jak w tablicy albo liście. To czy będziesz miał pecha do złożoności zależy od danych jakie dostarczasz a przede wszystkim ich kolejności - np. jeśli dodasz kolejno 1, 2, 3, 4, 5, 6 to otrzymasz "drzewo":
1
* 2
* 3
* 4
* 5
* 6
* *
Złożoność O(log(n)) dają bardziej złożone struktury o jakich wspomniał Shalom (tzn RB i AVL dają, o Splay jak żyję nie słyszałem więc nie wiem).
0
postanowiłem spróbować drzewo BST wypełnić liczbami z tablicy:
struct Node{
struct Node *left, *right;
Node(){
left = NULL;
right = NULL;
}
int value;
}*root; //wskaznik na korzen
w funkcji main()
int tablica[10] = {1,2,56,78,1,4,2,100,7489, 8};
root = new Node;
root->value = 5; //początkowa wartość dla korzenia
for(int i =0; i < 10; ++i )
{
Node *node;
node = new Node;
node->value = tablica[i];
add(node);
}
oraz definicja funkcji add
int add(struct Node *node)
{
struct Node *tmp; //tymczasowe, zeby przechować korzen, a potem zagłębiac się w coraz niższe poziomy drzewa
tmp = root;
if(tmp->value > node->value )
if(tmp->left == NULL) // jest miejsce
tmp->left = node;
else
add(tmp->left); // nie ma miejsca, wiec rekurencyjnie schodzę poziom w dol
else
if(tmp->right == NULL)
tmp->right = node;
else
add(tmp->right);
}
oto co udało mi się napisać, coś jest nie tak, z rekurencja, bo się zapętla, proszę o naprowadzenie mnie, co poprawić, aby zaczęło działać
0
Omg. Myślisz coś? Rozpisz sobie na kartce co właściwie napisałeś. Wywolujesz add(NOWY_ELEMENT) a następnie w rekurencji zawsze wywołujesz add(ROOT->left) albo add(ROOT->right).
Zresztą po co rekurencja? Tak trudno napisać:
int add(struct Node *node)
{
struct Node *tmp, * prev;
tmp = prev = root;
if(root == NULL)
root = node;
else{
while(tmp != NULL){
prev = tmp;
if(tmp->value > node->value ){
tmp=tmp->left;
else
tmp=tmp->right;
}
if(tmp->value > node->value ){
prev->left = node;
else
prev->right = node;
}
}
}
(pisane z palca, moze być błąd)
0
dalej jest coś nie tak
void add(struct Node *node)
{
struct Node *tmp, * prev;
tmp = prev = root;
if(root == NULL)
root = node;
else
{
while(tmp != NULL)
{
prev = tmp;
if(tmp->value > node->value)
tmp=tmp->left;
else
tmp=tmp->right;
if(tmp->value > node->value) // tu jakis błąd
prev->left = node;
else //lub tu
prev->right = node;
}
}
}
aplikacja zakańcza działanie, nie wiem dlaczego
0
Ajj nie domknąłem sobie bracketów, mówiłem przecie ze pisane z palca. Rozumiesz w ogóle kod ktory podałem? o_O
int add(struct Node *node)
{
struct Node *tmp, * prev;
tmp = prev = root;
if(root == NULL)
{
root = node;
}
else
{
while(tmp != NULL)
{
prev = tmp;
if(tmp->value > node->value )
{
tmp=tmp->left;
}
else
{
tmp=tmp->right;
}
}
if(prev->value > node->value )
{
prev->left = node;
}
else
{
prev->right = node;
}
}
}