Witam, mam pytanie odnośnie struktury B drzewa
struct btreeNode *child[MAX + 1] Czy to oznacza tablicę wskaźników do "dzieci" ? Ale nie mam pojęcia po co jest użyta druga tablica tab[MAX + 1] i zmienna count
#define MAX 4
#define MIN 2
struct treeNode {
int tab[MAX + 1], count;
struct btreeNode *child[MAX + 1];
};
struct treeNode *root;
Fuj, zmienne różnych typów powinny być deklarowane w osobnych wyrażeniach. Nie wiadomo co mają oznaczać te wartości, bo są fatalnie nazwane. Zapytaj autora kodu.
B tree jest dobzre opisane tutaj:
https://www.geeksforgeeks.org/introduction-of-b-tree-2/
albo tutaj:
https://opendatastructures.org/ods-java/14_2_B_Trees.html
Ale wszędzie tam są B drzewa do których wprowadza się liczby a jeśli chce wprowadzić inne dane?
A po co Miałbyś używać czegoś innego niż liczby, jako klucze?
Jakie klucze, chodziło mi o inne dane niż liczby np imiona itp
Możesz używać wszystkiego co ma jakiś porządek, znaków i stringów też.
Czyli do takiego drzewa mogę wprowadzać dane tylko które mają jakiś porządek ?
Render125 napisał(a):
Czyli do takiego drzewa mogę wprowadzać dane tylko które mają jakiś porządek ?
Z definicji:
B-drzewo – drzewiasta struktura danych, przechowująca klucze w pewnym porządku i powiązane z nimi dane,
Za wikipedią
Inaczej, jak Chcesz tam przechowywać dowolne dane, to Zrób sobie strukturkę klucz - wartość.
Jakoś nadal nie rozumiem : /
Render125 napisał(a):
Jakoś nadal nie rozumiem : /
W B-drzewie można umieszczać tylko dane które posiadają porządek (relację większy <), ponieważ dane w B-drzewie są posortowane żeby można było się po tym drzewie poruszać.
Jeśli posiadasz dane które nie posiadają porządku, można próbować w sztuczny sposób ten porządek wprowadzić, lub trzeba użyć innej struktury do przechowywania danych, np listy (listy par) lub tablicy haszującej
W jakim sposób wprowadzić można sztuczny porządek np dodając do danych miejsce na liczby które będą ten porządek tworzyły?
Btw B-drzewa i drzewa wielokierunkowe to to samo?
Render125 napisał(a):
Btw B-drzewa i drzewa wielokierunkowe to to samo?
Polecam wikipedię:
TL;DR - nie, to nie to samo
A jeśli napisałbym taką strukturę?
struct node {
// dane
int liczba_wezlow;
struct node *tablica[liczba_wezlow];
}
To mam strukturę która może mieć określoną przez użytkownika liczbę wskaźników na poddrzewa itp i nie musi być uporządkowana, to jest dobrze?
Nie, to nie jest nawet poprawny C albo C++. A struktura i tak musi być uporządkowana z definicji.
Dlaczego nie poprawny?
A co, Twoim zdaniem, robi struct node *tablica[liczba_wezlow];? Jakiej jest długości?
Deklaruje tablicę wskaźników do następnych poddrzew. A będzie ich tyle ile wpisze użytkownik wcześniej.
No to tak to nie działa — tablice są tworzone od razu, a ich rozmiar musi być znany w momencie kompilacji. Nie mogą poczekać, aż jakaś wartość zostanie ustawiona, za wyjątkiem VLA z C, ale nawet to nie ma tutaj zastosowania: odwołujesz się bowiem do liczba_wezlow z tej samej struktury, który nie jest zainicjalizowany w ogóle.
A jeśli bym użył jakieś struktury dynamicznej? Np listy zamiast tablicy
To już byłoby poprawne, ale jeszcze wciąż musisz pamiętać o tym, żeby jakoś „powiedzieć” tej strukturze, jak duża ma być ta lista — ona sama tego nie odgadnie, a że wszystkie pola struktury są robione „na raz”, nie ma możliwości wykorzystania wartości nadanej przy tworzeniu jednego parametru przy tworzeniu innego¹. Chcesz zatem mieć albo funkcję inicjalizującą (jak to się robiło w C), albo użyć klasy z odpowiednim konstruktorem, który zrobi co trzeba (C++).
¹ Edycja: da się tylko wtedy, jak ta wartość jest statyczna.
Najłatwiej chyba będzie użyć klasy vector w C++ a funkcja inicjalizująca to po prostu osobna funkcja gdzie inicjalizuje listę?
Jak piszesz w C++, a nie w C, to chcesz to mieć w klasie z odpowiednim konstruktorem. Ale tak, std::vector pasuje raczej dobrze, a funkcja inicjalizująca to funkcja która inicjalizuje, jak sama nazwa wskazuje. ;)
W języku C napisałem to mniej więcej w ten sposób :
struct data
{
//dane
};
struct list_node
{
struct data;
struct list_node *next;
};
struct family_tree
{
struct list_node *links;
};
A w języku C++
struct tree_node
{
//dane
vector<tree_node> links;
}