Sortowanie drzewem binarnym Mariusz: Sortowanie listy dwukierunkowej drzewem binarnym Węzeł listy dwukierunkowej wygląda tak samo jak węzeł drzewa binarnego Różnica między tymi strukturami polega na sposobie wiązania węzłów Wobec powyższego powstał pomysł aby użyć drzewa binarnego do sortowania listy Sortowanie listy dwukierunkowej odbywa się w dwóch etapach • Z węzłów listy dwukierunkowej budujemy drzewo binarne w ten sposób że pierwszy element listy dwukierunkowej wstawiamy do korzenia drzewa binarnego Kolejne elementy wstawiamy następująco Jeśli wartość wartość klucza korzenia poddrzewa jest równa wartości klucza wstawianego węzła to mamy wybór możemy wstawić węzeł albo do lewego poddrzewa albo do prawego poddrzewa jednak proponowałbym abyśmy w swym wyborze byli konsekwentni Jeśli wartość wartość klucza korzenia poddrzewa jest mniejsza od wartości klucza wstawianego węzła to wstawiamy węzeł do prawego poddrzewa Jeśli wartość wartość klucza korzenia poddrzewa jest większa od wartości klucza wstawianego węzła to wstawiamy węzeł do lewego poddrzewa • Przekształcamy drzewo binarne w listę dwukierunkową przechodząc je „ in order” czyli w kolejności L −> P −> R (Lewy potomek −> Rodzic −> Prawy potomek) Dla pewnych danych wejściowych drzewo binarne może się zdegenerować Z obserwacji wynika że przypadek pesymistyczny dla sortowania drzewem binarnym jest przypadkiem optymistycznym dla sortowania przez wstawianie Przypadku pesymistycznego można uniknąć używając zrównoważonego drzewa binarnego Co byście dodali do tego opisu algorytmu Co byście zmienili aby się go względnie dobrze czytało

Dominik: mozesz oszacowac zlozonosc obliczeniowa jak i pamieciowa. porownalbym to rowniez do sortowania przez kopcowanie.

Mariusz: Złożoność pamięciowa zależy od implementacji − od tego czy pozwolimy tworzyć nowe węzły (przy przechodzeniu drzewa wstawiamy utworzone węzły do nowej listy a następnie zwalniamy pamięć na drzewo) − od tego czy użyjemy rekurencji (Jeśli nie uda się nam napisać iteracyjnego odpowiednika pamięć będzie musiała być zarezerwowana na stos wywołań rekursji) Gdy drzewo nam się zdegeneruje otrzymamy złożoność O(n²) W średnim przypadku otrzymamy złożoność O(nlog(n)) Jeśli użyjemy zrównoważonego drzewa binarnego to w przypadku pesymistycznym także otrzymamy złożoność O(nlog(n)) Najbardziej kosztowne jest budowanie drzewa Jeśli drzewo się nam zdegeneruje to dostaniemy coś z sumą kolejnych liczb naturalnych w przeciwnym razie będziemy mieli sumę logarytmów z kolejnych liczb naturalnych co da nam O(log(n!)) Należałoby pokazać że O(log(n!)) jest tego samego rzędu co O(nlog(n))