[Algorytmy][C] Etykiety drzewa BST

adams1604 · Post autor: **adams1604** » 21 gru 2011, o 22:58

Zaproponuj algorytm, który bada czy dany skończony ciąg, o elementach należących do pewnego zbioru liniowo uporządkowanego Et, może być ciągiem etykiet drzewa BST zapisanych w porządku preorder i jeśli jest to możliwe, tworzy takie drzewo BST.

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.

Ma ktoś jakieś pomysły na rozwiązanie ?

miodzio1988 · Post autor: **miodzio1988** » 21 gru 2011, o 23:01

Implementacja to pikuś, więc powiedzmy sobie co jest ważne.

Kiedy mówimy, że dany ciąg może być ciągiem etykiet drzewa BST ?

Z wykładu powinieneś to wiedzieć. Z notatek. Zatem?

paladin · Post autor: **paladin** » 22 gru 2011, o 01:36

Rekursja. Pierwszy element musi być korzeniem (w końcu to preorder), a po nim musi nastąpić najpierw lewe podrzewo, a potem prawe. Na obu należy osobno wywołać rekursję, tylko jak odróżnić, gdzie kończy się lewe, a zaczyna prawe? Pomyśleć o własności BST

Uwaga do mojego poprzednika: Twój post wygląda trochę, jakbyś wziął gotowy szablon ("powinieneś mieć (...) w notatkach z wykładu") i przekleił do niego pytanie bez zrozumienia. Akurat to zadanie ma małe szanse być rozwiązywanym na typowym wykładzie, a to dlatego, że nie jest na tyle ważne, żeby marnować cenny czas

adams1604 · Post autor: **adams1604** » 27 gru 2011, o 13:03

Więc mamy, że pierwszym elementem jest wierzchołek. Etykiety z lewego podrzewa muszą być mniejsze od korzenia, a etykiety z prawego podrzewa większe od korzenia?

Czyli na poczatku mamy ciąg uporządkowany zapisany w porządku preorder ? Czyli np: 10,24,34,45,55,60?

abc666 · Post autor: **abc666** » 27 gru 2011, o 13:53

adams1604, przeczytaj pierwsze słowo w poście paladina. Pierwsza etykieta idzie do korzenia. Jeśli następny dany element jest mniejszy od korzenia, idziesz do lewego poddrzewa. Gdzie trafi ten wierzchołek jeśli patrzysz tylko na to poddrzewo?

adams1604 · Post autor: **adams1604** » 27 gru 2011, o 14:40

Pierwsza etykieta to będzie korzeń. Następnie jeśli element jest mniejszy od korzenia to bedzie to lewa etykieta tego wierchołka. Wiec mamy lewe poddrzewo. Postepujemy zdognie z reguła preorder. I tak np przykladowy ciag liczb: 8 5 2 1 6 9 10 11 jest bedzie drzewem BST a ciag liczb: 4 5 2 1 3 nie bedzie drzewem BST bo 5>4 i nie moze byc w lewym poddrzewiu wiercholka 4.

Nie wiem dokladnie jak nalezy interpretowac takie zadania. Jakie bedzie koszt takich dzialan ?

abc666 · Post autor: **abc666** » 27 gru 2011, o 15:02

bo 5>4 i nie moze byc w lewym poddrzewiu wiercholka 4.

Nie chodzi o to, że \(\displaystyle{ 5>4}\). Po prostu \(\displaystyle{ 5}\) zostanie umieszczona w prawym poddrzewie, a lewe będzie puste. Chodzi tutaj o to, że po \(\displaystyle{ 5}\) mamy elementy mniejsze od \(\displaystyle{ 4}\), które powinny być w lewym poddrzewie, ale my już dotarliśmy do prawego.