I gdzie tu jest ta szybkość drzew binarnych?

Question

Witam! Zastanawiam się gdzie tu jest szybkość drzew binarnych. Drzewa te podobno działają tak, że podczas przechodzenia przez nie, skraca się je o połowę. Ale co w przypadku haseł? Załóżmy, że mam sobie jakieś tam drzewo z rozszerzeniami plików (jest ich w 3.) i wartością jest rozszerzenie a wewnętrzną wartością (?) jest opis rozszerzenia. I gdzie tu teraz jest szybkość BTree? Skoro są to łańcuchy (te rozszerzenia), to nie można ich jakoś po numerować jako id, a podczas porównywania stringów nie można tego jakoś skracać o połowę... Wie ktoś może jak takie coś rozwiązać? Czy byłoby tu przydatne np. zrobić tablicę stringów z tymi rozszerzeniami i index odpowiada id. I na podstawie ID szukać w BTree? Jak by to można było rozwiązać, bo potrzebuję...

Comments

Niestety, nie rozumiem pytania.

Zastanawiam się gdzie tu jest szybkość drzew binarnych

I gdzie tu teraz jest szybkość BTree?

No to BTree czy drzewo wyszukiwania binarnego? To są trochę różne rzeczy.

https://en.wikipedia.org/wiki/Binary_tree

https://en.wikipedia.org/wiki/B-tree

to nie można ich jakoś po numerować jako id

Zakładając że miałeś na myśli drzewa wyszukiwania binarnego: do takich drzew nie trzeba nic numerować, wystarczy relacja mniejsze-większe. Skąd te id wziąłeś?

---

1. Sorry, ale kiedyś ktoś użył skrótu BTree jako skrót do Binary Tree i myślałem, że  to to samo.

2. ID stąd, że przerabiam książkę "C++. Przewodnik dla początkujących" i tam autor używał drzew, które skracały się poprzez ID węzła. Jakoś tak. Że bodajże lewa strona była większa od rodzica a prawa mniejsza i tak to jakoś szło.

3. Jak może być relacja większy mniejszy? I chodzi mi o to, że chciałbym napisać program, który podaje informacje o pliku, czyli: Nazwa, Wielkosc, INFORMACJE O ROZSZERZENIU, ...

 

I jako to ID byłoby rozszerzenie w postaci stringa i jako wartość byłaby informacja w postaci stringa (ale to mniej ważne). I umyśliłem sobie, że może być tablica stringow z tymi WSZYSTKIMI rozszerzeniami i index stringa z rozszerzeniem odpowiadalby int'owemu id w drzewie...

Answer 1

I jako to ID byłoby rozszerzenie w postaci stringa i jako wartość byłaby informacja w postaci stringa (ale to mniej ważne). I umyśliłem sobie, że może być tablica stringow z tymi WSZYSTKIMI rozszerzeniami i index stringa z rozszerzeniem odpowiadalby int'owemu id w drzewie...

Nie potrzebujesz intów, żeby szukać rzeczy w drzewie. Kluczem jak najbardziej może być string.

Jeśli "zwykłe" drzewo i funkcja szukania wygląda tak:

struct Node {
	int key;
	Dane dane;
	Node *left, *right;
};
Node* search(int key, Node * node) {
	if (node == nullptr) return node;
	if (key == node->key) return node;
	return search(key, key < node->key ? node->left : node->right);
}

To dokładnie ten sam kod, tylko ze stringowymi kluczami, będzie też poprawnie działał:

struct Node {
	std::string key;
	Dane dane;
	Node *left, *right;
};
Node* search(const std::string &key, Node * node) {
	if (node == nullptr) return node;
	if (key == node->key) return node;
	return search(key, key < node->key ? node->left : node->right);
}

(BTW, mniej więcej tak w C++ie w bibliotece standardowej funkcjonują std::map<int, Dane> i std::map<std::string, Dane>)

A, jeszcze to:

Jak może być relacja większy mniejszy?

Że bodajże lewa strona była większa od rodzica a prawa mniejsza i tak to jakoś szło.

Sam sobie odpowiedziałeś ;)

Comments

1. Nie rozumiem tych zapisów cos? cosinnego : jeszczecosinnego

2. Ale jak jeden string może być mniejszy od drugiego? Przecież to jest łańcuch znaków... Nie a tu liczb. Chyba, że by pozamieniać wszystkie znaki na index w ASCII i pododawać to wszystko, ale to by była katorga i niektóre wyniki byłyby takie same.

---

1. Nie rozumiem tych zapisów cos? cosinnego : jeszczecosinnego

Wyrażenie warunkowe. Można to dłużej zapisać tak:

Node *next;
if (key < node->key)
	next = node->left;
else
	next = node->right;
return search(key, next);

Ale jak jeden string może być mniejszy od drugiego? 

Dokładnie tak samo, jak są posortowane w książce telefoniczniej, słownikach lub w spisie na końcu podręczników - alfabetycznie ;)

Sam możesz zobaczyć, że to działa, wpisując w programie:

std::string x = "kasia";
std::string y = "tomek";
bool b = x < y; // Kasia jest w ksiazce telefonicznej przed Tomkiem

 

---

O kurde :O. Dziękuję! xD

Answer 2

No tak no to po kolei..

1. Klikamy na dokumentację std::string w bibliotece standardowej i widzimy:

http://en.cppreference.com/w/cpp/string/basic_string

2. Następnie zaglądamy do zaimplementowanych operatorów:

http://en.cppreference.com/w/cpp/string/basic_string/operator_cmp

Jak widać są operatory operator==,!=,<,<=,>,>=(std::basic_string)

3. Wracamy do poprzedniej strony:

http://en.cppreference.com/w/cpp/string/basic_string

4. Jedziemy na koniec strony i klikamy w sekcję "Helper classes":

http://en.cppreference.com/w/cpp/string/basic_string/hash

Już widać że są implementacje funkcji skrótu dla std::string'a.

Dodatkowo warto zapoznać się z: http://scottmeyers.blogspot.de/2015/09/should-you-be-using-something-instead.html

Aby wyciągnąć jakieś wnioski o wydajności kontenerów. Oczywiście to nie jedyne źródła ... ale efekt 5 min szukania.