Forum

drzewo bst

[+] Twoje konto

Subskrybuj kanał najnowszych wypowiedzi w tym temacie

Wątek Forum > Porady > Programowanie > drzewo bst

Idź do strony:1
Ocena: (Ocen: 0)
Wypowiedzi 1 - 2 z 2
 Gość ulotnachwila87 Kopiuj nick (83.142.12.*)
Wypowiedź dodana: 14 września 2007, 15:50:46
« Opcje

nie rozumiem jak tworzy sie drzewo bst.. chodzi mi nie o napsianie programu a sam fakt zrozumienia problemu.. wszedzie jest to jakos niejasno omówione.

wiec przechodze do meritum:
mam ciag 20 30 50 40, 70 60 100 90 80 i 150.. :-/ i mam stworzyc drzewo bst.. to sa moje wypociny prosilabym o wyjasnienei i skorygowanie:

http://s158.photobucket.com/albums/t113/ulotnachwila87/?action=view&current=beztytuu-1.jpg

 Gość REKLAMA Kopiuj nick (*->*)
Wypowiedź dodana: 14 września 2007, 15:50:47

AvatarAdministrator Dżyszla Mężczyzna Kopiuj nick (83.2.108.*) |  
Wypowiedź dodana: 14 września 2007, 21:01:05 | Wypowiedź edytowana Ostatnio edytowana: 14 września 2007, 21:04:34 po raz 1-wszy przez: Dżyszla
« Opcje

Optymalnym drzewem binarnym jest takie, które ma równomierną rozłożoną ilość gałęzi. Wtedy - szukając - łatwo i najszybciej dotrzemy do interesującej nas wartości. Właśnie najprościej oprzeć to o przypadek szukania - sprawdzamy liczbę - czy szukana jest większa? - idziemy w prawo, jak nie - w lewo.

Tworzenie optymalnego drzewa jest dość proste: rozpisujemy sobie wszystkie liczby w kolejności. Następnie bierzemy środkową. To będzie nasz korzeń. Do niej wiążemy środkowe z tak podzielonego przedziału. Operację powtarzamy aż do pojedynczych liczb:
Załóżmy, że mamy:
1 3 5 6 8 10 13 16

Środkową jest tu 6 (8 liczb / 2 = 4. liczba)
Tak 6 stało się naszym korzeniem i mamy teraz dwa podzbiory:
(1) 1 3 5
(2) 8 10 13 16

Z lewego wyznaczamy znów środkową i dopisujemy jako lewą gałąź:

Kod:

6
/
3

Teraz lewy zbiór podzielił się na dwa pojedyncze:
(1.1) 1
(1.2) 5

Te liczby staną się liśćmi - dopisujemy mniejszy na lewo, większy na prawo.

Kod:

6
/
3
/ \
1 5

Analogicznie prawy zbiór (2) - środkowa to 10 (lub 13 - tu jest dowolna sprawa) - otrzymujemy dwa kolejne podzbiory:
(2.1) 8
(2.2) 13 16
lewy staje się liściem, a prawy rozdzielimy jeszcze węzeł i liść. cały efekt wygląda tak:

Kod:

6
/ \
3 10
/ \ / \
1 5 8 13
\
16

Teraz chcąc szybko wyszukać, czy liczba 8 znajduje się w drzewie:
1. 6 ? 8 -> 6 < 8 => idziemy w prawo
2. 10 ? 8 -> 10 > 8 => idziemy w lewo
3. 8 ? 8 -> 8 = 8 => znaleźliśmy!

W porównaniu przeszukanie całego zbioru wyglądało by tak:
1. 1 = 8? - NIE
2. 3 = 8? - NIE
3. 5 = 8? - NIE
4. 6 = 8? - NIE
5. 8 = 8? - TAK

Tak więc widzimy, jaki zysk dało nam poruszanie się po drzewie - dokonaliśmy małej ilości porównań.

Dobrą analogią jest szukanie w książce telefonicznej - otwierasz ją w pewnym miejscu - jest ono dla Ciebie korzeniem - patrzysz, czy szukane nazwisko jest w kolejności alfabetycznej wcześniej czy dalej (mniejsze/większe). W zależności od wyboru idziesz na strony wcześniejsze lub dalsze od miejsca podziału (szukasz w lewym lub prawym podzbiorze). W ten sposób realizujesz właśnie zasadę drzewa binarnego.


mgr inż. Dżyszla

Nie odpisuję na problemy zgłaszane na e-mail lub PW!

Także dzięki firmie Netlook.pl możesz za darmo korzystać z tej strony!

 
Idź do strony:1

[+] Pokaż/odśwież listę czytających i monitorujących ten wątek

Podobne tematy:
Tytuł wątkuDziałWypowiedziWyświetleńOcenaOstatnia wypowiedź

Nowa wypowiedź

Nowa wypowiedź
Nie jesteś zalogowany; będziesz traktowany jako gość!
Zaloguj Zaloguj
Nick (gość): | Przepisz ten kod [?]: eaeb3:
Tekst:

 
* Wysyłając formularz wyrażasz zgodę na przetwarzanie przekazanych danych w zakresie wskazanym w Regulaminie

Subskrybuj kanał najnowszych wypowiedzi w tym temacie


Chcesz mieć też takie forum na swojej stronie? Napisz!

Strona istnieje od 25.01.2001
Ta strona używa plików Cookie.
Korzystając z niej wyrażasz zgodę na przetwarzanie danych a zakresie podanym w Polityce Prywatności.
 
archive To tylko kopia strony wykonana przez robota internetowego! Aby wyświetlić aktualną zawartość przejdź do strony.
Ładowanie...

Optymalizowane dla przeglądarki Firefox
© Copyright 2001-2018 Dawid Najgiebauer. Wszelkie prawa zastrzeżone.
Ostatnia aktualizacja podstrony: 3.06.2018 10:28
Wszystkie czasy dla strefy czasowej: Europe/Warsaw