[harnasiek]

#informatyka #studbaza #algorytmy #strukturadanych #programowanie

Czy jest jakaś ogólne zasada tworzenia BST?
bo w książce Cormena w rozdziale o bst nie znalazłem nic, a widzę że ludzie na yt tworzą drzewa metodą inorder.

[ZdeformowanyKreciRyj]

@harnasiek: nie ma takiej zasady bo dla danego zbioru drzew bst może być wiele różnych, wszystko zależy od tego co chcesz uzyskać. W najbardziej trywialnym przypadku wstawiając nowy element po prostu schodzisz z korzenia do liści porównując wstawiany element z wartością w aktualnie rozpatrywanym wierzchołku i idziesz w prawo albo w lewo a jak już nie możesz iść dalej to wstawiasz w tym miejscu nowy wierzchołek

[harnasiek]

@ZdeformowanyKreciRyj: czyli jak mam wejściową tablicę np [56,3,6,23,4,34,12,14] to idę od lewej do prawej i tworzę drzewo tak? I wtedy korzeniem będzie 56 i według zasady kolejne elementy porównuje i wstawiam albo na lewo albo na prawo

[ZdeformowanyKreciRyj]

@harnasiek: można tak zrobić i dostaniesz legitne bst z tym że zauważ że jak te dane Ci się odpowiednio ułożą (będą posortowane) to zamiast drzewa zbudujesz sobie taką długa ścieżkę co z punktu widzenia szybkiego wyszukiwania nie jest zbyt korzystne. Dlatego są różne sposoby balansowania drzew bst tak żeby właśnie ich maksymalna glebokosc nie byla zbyt duża

[harnasiek]

@ZdeformowanyKreciRyj: to akurat wiem, że posortowane to najgorsza opcja