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.
@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
@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
@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
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.