[Algorytmy] Suma zbiorów jako BST

piter1389 · Post autor: **piter1389** » 29 gru 2011, o 11:27

Mam problem z takim zadaniem:

Dane są dwa zbiory A i B, reprezentowane jako drzewa binarnych poszukiwań. Zaproponuj algorytm, który znajduje sumę tych zbiorów w postaci drzewa BST. Koszt algorytmu powinien być liniowy względem liczby elementów w danych zbiorach.

Rozwiązanie powinno zawierać

specyfikację zadania,
opis słowny metody rozwiązania,
algorytm rozwiązujący (ew. jego implementację),
analizę kosztu i
analizę poprawności algorytmu względem podanej specyfikacji.

Nie mam pomysłu jak zrobić te zadanie... proszę o pomoc.

Mistrz · Post autor: **Mistrz** » 29 gru 2011, o 13:34

Koncepcyjnie najprostsze będzie chyba coś takiego:
1. Wyciągasz z drzewa zbiór A do postaci tablicy posortowanej rosnąco
2. Tak samo ze zbiorem B
3. Scalasz te dwie tablice tak, żeby wynik był posortowaną rosnąco tablicą
4. Budujesz z tej tablicy drzewo BST
Każdy z tych czterech kroków ma co najwyżej liniową złożoność czasową i pamięciową. I każdy pewnie wiesz jak zrealizować?

piter1389 · Post autor: **piter1389** » 29 gru 2011, o 13:39

No właśnie wiem czy będę wiedział... te algorytmy wgl mi nie leżą. :/

Mistrz · Post autor: **Mistrz** » 29 gru 2011, o 13:44

Czy hasło "porządek infiksowy" coś Ci mówi?

piter1389 · Post autor: **piter1389** » 29 gru 2011, o 14:02

wogóle mi nie mówi;p

Mistrz · Post autor: **Mistrz** » 29 gru 2011, o 14:28

To oznacza, że masz spore braki w podstawach i ciężko będzie Ci dać jakąś konkretną wskazówkę do tego zadania. Nadrób te braki. Możesz zacząć np. tu: - coś o drzewach, w szczególności o tym w jakim porządku można je obchodzić. Podpowiedź ode mnie do tego zadania jest taka, że jak przechodzisz drzewo BST w porządku infiksowym to odwiedzasz elementy po kolei od najmniejszego do największego, albo na odwrót.

W informatyce często bywa tak, że aby rozwiązać jakiś problem wystarczy sprowadzić go do jakiegoś prostszego zagadnienia, które już umiemy rozwiązać. Ciężko będzie Ci robić zadania bardziej złożone, jeżeli nie umiesz jeszcze zrobić prostych zadań, takich jak "Wypisz z danego drzewa BST wszystkie elementy w porządku malejącym. Koszt algorytmu powinien być liniowy względem rozmiaru drzewa".