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 [?]: d272e:
Tekst:

 

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
Helion.pl  
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-2017 Dawid Najgiebauer. Wszelkie prawa zastrzeżone.
Ostatnia aktualizacja podstrony: 22.09.2014 12:12
Wszystkie czasy dla strefy czasowej: Europe/Warsaw