🚀 go-pugleaf

Daniel Roziecki (Emssik) wrote:
> 
>  Hejka, sluchajcie, mam prosbe, potrzebuje algorytmy do
> obslugi drzewa binarnego (sortowanie, wyszukiwanie, drzewo
> zrownowazone), gdyby ktos mial to na kompie, to podeslijcie
> mi na maila, lub jesli ktos zna na inecie, jakis adres
> (polsko, lub anglo jezyczny) DOBRY, dotyczacytego
> zagadnienia, to tez prosil bym o informacje, z gory
> dziekuje..
> 
> Aha, gdyby sie ktos pytal, zcemu na liscie dyskusyjnej o C,
> to dla tego,z e mam napisac program na zalizenie wlasnei w C
> :))

Czlowieku, przeciez to podstawy. Jaki bedzie z Ciebie informatyk???


Stanislaw Bochnak

 >Czlowieku, przeciez to podstawy. Jaki bedzie z Ciebie
informatyk???
>
>
>Stanislaw Bochnak

Coz, odpowiem po prostu, ze dobry.. :) Tyle tylko, ze nie
wiem jak Ty, ale ja nie urodzilem sie z glowa pelna
algorytmow.. Wiem, ze to podstawy. ale tak jakos nigdy tego
nie potrzebowalem i studiuje informa wlasnie dla tego, zeby
sie tego dowiedziec, a ze studiuje zaocznie, wiec nie za
wiele dowiaduje sie na wykladach, wiec serdecznie
przepraszam, ze nie urodzilem sie geniuszem i jeszcze raz
prosze o pomoc...

Daniel

Witam,

Daniel Roziecki (Emssik) wrote:
> 
>  >Czlowieku, przeciez to podstawy. Jaki bedzie z Ciebie
> informatyk???
> >
> >
> >Stanislaw Bochnak
> 
> Coz, odpowiem po prostu, ze dobry.. :) Tyle tylko, ze nie
> wiem jak Ty, ale ja nie urodzilem sie z glowa pelna
> algorytmow.. Wiem, ze to podstawy. ale tak jakos nigdy tego

Ja tez nie. Sam je pisalem.

> nie potrzebowalem i studiuje informa wlasnie dla tego, zeby
> sie tego dowiedziec, a ze studiuje zaocznie, wiec nie za

Wiec dowiedziales sie jaka jest specyfikacja drzewa,
a implementacje mozesz napisac sam. Chyba nie oczekujesz, ze
wykladowca napisze Ci kod na tablicy! Ja studiowalem na dziennych
i wlasnie tak to wygladalo. Uwazam zreszta, ze slusznie. Teraz
nie pisze juz drzewa, listy, wektora itd. tylko uzywam STLa,
ale gdy trzeba sprawdzic/zdebuggowac taki kod jestem w stanie
to zrobic!

> wiele dowiaduje sie na wykladach, wiec serdecznie
> przepraszam, ze nie urodzilem sie geniuszem i jeszcze raz

Nie ma za co przepraszac! Takich jest niewielu, a do zaimplementowania 
drzewa naprawde nie trzeba byc geniuszem. 


Stanislaw Bochnak

> prosze o pomoc...
> 




P.S. 
Nie pamietam tytulu, ale zdaje sie Knuth napisal dwutomowe dzielo
o strukturach danych i algorytmach na nich dzialajacych.
Poza tym, chyba byla ta ksiazka tez po polsku "Algorytmy + struktury
danych = program".
Jest jeszcze chyba cos o "strukturach danych w jezyku Pascal", ale nie
pamietam
dokladnie tytulu. Nawet nie wiem, czy jest dobra, ale moze warto
poszukac
w bibliotekach.

Stanislaw Bochnak <S.Bochnak@microTOOL.com.pl_nospam> 
napisal

> P.S. 
> Nie pamietam tytulu, ale zdaje sie Knuth napisal dwutomowe dzielo
> o strukturach danych i algorytmach na nich dzialajacych.
> Poza tym, chyba byla ta ksiazka tez po polsku "Algorytmy + struktury
> danych = program".
> Jest jeszcze chyba cos o "strukturach danych w jezyku Pascal", ale nie
> pamietam
> dokladnie tytulu. Nawet nie wiem, czy jest dobra, ale moze warto
> poszukac
> w bibliotekach.

Jest jeszcze przez WNT wydana A.Drozdek & D.L.Simpson
"Struktury danych w jezyku C"
w/g mnie bardzo przystepnie i przejrzyscie napisana.
Niestety... sa rowniez gotowe przyklady implementacji w C.
Wiec moze troche malo to pedagogiczne w tym kontekscie,
chociaz nie sadze. Wszystko zalezy od czytelnika jak je wykorzysta :))
-- 
Pozdrawiam                                         Adam Karpierz   
mailto:karpierz@intertele.pl
http://www.intertele.pl/users/karpierz 

Coz, wypada mi wiec podziekowac. A wiec THX.. Jednoczesnie
musze przyznac, ze to rzeczywisice jest proste i
implementacje, napisalem sobie samemu bez pomocy literatury,
problem po prostu polegal na tym, ze ja naprawde nie mialem
na to czasu :(( A ze dochodzilem do tego samemu, mam kilka
dodatkowych pytan:

1. Czy za wartosc maksymalna i minimalna mozemy uznac
ostatni (nie zerowy) element danej skrajnej (lewej lub
prawej) galezi drzewa? Wydaje mi sie, ze tak, ale wole sie
upewnic.

2. I pytanie na temat tworzenia drzewa zrownowazonego.
Nigdzie nie moge tego znalezc, a nie jestem pewny, czy moje
rozumienie tego zagadnienia jest prawidlowe. A wiec, w celu
uzyskania takiego drzewka, jesli od razu mam wszystkie dane
(np. w formie tablicy), ktore mam rozmiescic na drzewie,
wyliczam ich srednia arytmetyczna i jako pierwszy element na
drzewie, wstawiam wartosc najblizsza sredniej. Tyle tylko,
ze to ma jeden minus. Co bedzie jesli w tych danych, znajda
sie elementy znacznie odbiegajace w gore, lub w dol od
sredniej? A moze przy obiczaniu takiej sredniej wylaczyc np.
3 najwieksze i 3 najmniejsze elementy zbioru?
    To bylo w miare proste, a jak tworzyc drzewo
zrownowazone w sposob dynamiczny, w momencie, gdy dane,
ktore chce przedstawic w formie drzewa beda sie pojawialy
np. losowo? Czy moge, gdy znam zakres tych danych, np. od 0
do 10000, sztucznie przyjac za moj korzen wartosc 5000 i nie
brac jej pod uwage w trakcie dalszej pracy programu? Tyle
tylko, ze to mi nie daje zadnej gwarancji, ze wszystkie
pojwiajace sie wartosci nie beda jednak np. mniejsze od tej
liczby. I znowu jestem w punkcie wyjscia. Aha, a nie biore
pod uwage, ciaglego przekladania elementow, przy ich
niewielkiej liczbie moze i bylo by to nie najgorsze
rozwiazanie, ale przy bardziej rozbudowanych drzewach,
coz...
    W zasadzie nie jest mi to potrzebne do examu, ale z
samej ciekawosci chcial bym wiedziec, jesli moje pytania
znowu wydadza sie komus dziecinne i smieszne, to
przepraszam. Ale jesli mam byc szczery, to zajmuje sie
programowaniem, glownie w asemblerze od ponad 8 lat i NIGDY
jeszcze nie potrzebowalem do niczego tej wlasnie
struktury... I pewnie wielu, wielu innych, o ktorych mam
nadzieje sie wkrotce dowiem.
    To by bylo na tyle, jeszcze raz dziekuje, za podana
literature, pewnie cos mi sie z tego kiedys przyda, z mojej
strony polecam wszystkim:

 "Perelki oprogramowania"
Jon Bentley
Wydawnictwo Naukowo-Techniczne W-wa 1992

Naprawde warto to przeczytac...

Oki to na tyle.

Daniel

emssik@radom.net
emssik@dino.wsi.edu.pl

Daniel Roziecki (Emssik) wrote:
> 
>  Hejka, sluchajcie, mam prosbe, potrzebuje algorytmy do
> obslugi drzewa binarnego (sortowanie, wyszukiwanie, drzewo
> zrownowazone), gdyby ktos mial to na kompie, to podeslijcie
> mi na maila, lub jesli ktos zna na inecie, jakis adres
> (polsko, lub anglo jezyczny) DOBRY, dotyczacytego
> zagadnienia, to tez prosil bym o informacje, z gory
> dziekuje..
> 
> Aha, gdyby sie ktos pytal, zcemu na liscie dyskusyjnej o C,
> to dla tego,z e mam napisac program na zalizenie wlasnei w C
> :))
> 
> Z gory dziekuje
> 
Niklaus Wirth: "Algorytmy+struktury danych=programy"
Maly.

Daniel Roziecki (Emssik) <emssik@copy_con.perytnet.pl> wrote:
> 2. I pytanie na temat tworzenia drzewa zrownowazonego.
> Nigdzie nie moge tego znalezc, a nie jestem pewny, czy moje
> rozumienie tego zagadnienia jest prawidlowe. A wiec, w celu
> uzyskania takiego drzewka, jesli od razu mam wszystkie dane
> (np. w formie tablicy), ktore mam rozmiescic na drzewie,
> wyliczam ich srednia arytmetyczna i jako pierwszy element na
> drzewie, wstawiam wartosc najblizsza sredniej. Tyle tylko,
> ze to ma jeden minus. Co bedzie jesli w tych danych, znajda
> sie elementy znacznie odbiegajace w gore, lub w dol od
> sredniej? A moze przy obiczaniu takiej sredniej wylaczyc np.
> 3 najwieksze i 3 najmniejsze elementy zbioru?

Odpowiedź: mediana. Inaczej: wartość srodkowa.
Dla _USZEREGOWANEJ_ (posortowanej) N-elementowej tablicy A :
- Jeśli N jest nieparzyste, to bierzemy wartość elementu środkowego.
- Jeśli N jest parzyste, to bierzemy średnią z dwóch elementów środkowych.

Przykład 1:
Tablica uszeregowana: 1 1 2 3 5 8 13 21 34  ---> mediana: 5

Przykład 2:
Tablica uszeregowana: 1 1 2 3 5 8 13 21 34 55 ---> mediana: (5+8)/2 = 6.5

Spróbuj poeksperymentować.

>     To bylo w miare proste, a jak tworzyc drzewo
> zrownowazone w sposob dynamiczny, w momencie, gdy dane,
> ktore chce przedstawic w formie drzewa beda sie pojawialy
> np. losowo? Czy moge, gdy znam zakres tych danych, np. od 0
> do 10000, sztucznie przyjac za moj korzen wartosc 5000 i nie
> brac jej pod uwage w trakcie dalszej pracy programu? Tyle
> tylko, ze to mi nie daje zadnej gwarancji, ze wszystkie
> pojwiajace sie wartosci nie beda jednak np. mniejsze od tej
> liczby. I znowu jestem w punkcie wyjscia.

Znowu rada: poeksperymentuj z medianą.

-- 
-- Andrzej Bort  Silesian Technical Univ., Computer Center, Gliwice, Poland
-- e-mail: bort <AT> polsl.gliwice.pl      Office phone: (+48-32) 230-76-86
-- IRC: Juan       For PGP key look at: http://zeus.polsl.gliwice.pl/~bort/
-- ** The office box said: W'95, NT 4.0 or better.  So I installed Linux **

On Wed, 3 Dec 1997, Daniel Roziecki (Emssik) wrote:

> 1. Czy za wartosc maksymalna i minimalna mozemy uznac ostatni (nie
> zerowy) element danej skrajnej (lewej lub prawej) galezi drzewa? Wydaje
> mi sie, ze tak, ale wole sie upewnic.

Zgadza się.

> 2. I pytanie na temat tworzenia drzewa zrownowazonego. Nigdzie nie moge
> tego znalezc, a nie jestem pewny, czy moje rozumienie tego zagadnienia
> jest prawidlowe. A wiec, w celu uzyskania takiego drzewka, jesli od razu
> mam wszystkie dane (np. w formie tablicy), ktore mam rozmiescic na
> drzewie, wyliczam ich srednia arytmetyczna i jako pierwszy element na
> drzewie, wstawiam wartosc najblizsza sredniej. Tyle tylko, ze to ma
> jeden minus. Co bedzie jesli w tych danych, znajda sie elementy znacznie
> odbiegajace w gore, lub w dol od sredniej? A moze przy obiczaniu takiej
> sredniej wylaczyc np. 3 najwieksze i 3 najmniejsze elementy zbioru?

Należy brać nie średnią, a medianę, czyli element ze środka (jeśli jest
parzysta liczba elementów, to którykolwiek).

> To bylo w miare proste, a jak tworzyc drzewo zrownowazone w sposob
> dynamiczny, w momencie, gdy dane, ktore chce przedstawic w formie drzewa
> beda sie pojawialy np. losowo? Czy moge, gdy znam zakres tych danych,
> np. od 0 do 10000, sztucznie przyjac za moj korzen wartosc 5000 i nie
> brac jej pod uwage w trakcie dalszej pracy programu? Tyle tylko, ze to
> mi nie daje zadnej gwarancji, ze wszystkie pojwiajace sie wartosci nie
> beda jednak np. mniejsze od tej liczby. I znowu jestem w punkcie
> wyjscia. Aha, a nie biore pod uwage, ciaglego przekladania elementow,
> przy ich niewielkiej liczbie moze i bylo by to nie najgorsze
> rozwiazanie, ale przy bardziej rozbudowanych drzewach, coz...

Jest coś, co się nazywa drzewo AVL. W skrócie: Jest to takie drzewo BST
(czyli posortowane), dla którego w każdym wierzchołku wysokości obu
poddrzew różnią się najwyżej o jeden. Dzięki temu wysokość jest
logarytmicznego rzędu względem liczby wierzchołków, a można zachowywać tę
własność niewielkim nakładem kosztów (w logarytmicznym czasie przy
wstawianiu i również w logarytmicznym przy usuwaniu elementu). W każdym
wierzchołku pamiętamy dodatkowo różnicę wysokości obu poddrzew (-1, 0,
+1). Po wstawieniu elementu jeśli w którymś wierzchołku ta różnica
zwiększy się do dwóch, trzeba poprawić drzewo przez sprytne "przekręcenie"
kilku elementów (i ich poddrzew jako całości) zachowując przy tym ich
kolejność. Przy usuwaniu trzeba wsadzić wartość z pewnego liścia do
usuwanego wierzchołka i usunąć ten liść, po czym podobnie poprawić różnice
wysokości.

Pytania raczej pasowałyby na pl.comp.programming, gdzie ustawiam
Followup-To.

--
                                QRCZAK
    __("<             Marcin Kowalczyk
    \__/             qrczak@knm.org.pl
     ^^      http://kki.net.pl/qrczak/

Daniel Roziecki (Emssik) (emssik@copy_con.perytnet.pl) wrote:
: Coz, wypada mi wiec podziekowac. A wiec THX.. Jednoczesnie
: musze przyznac, ze to rzeczywisice jest proste i
: implementacje, napisalem sobie samemu bez pomocy literatury,
: problem po prostu polegal na tym, ze ja naprawde nie mialem
: na to czasu :(( A ze dochodzilem do tego samemu, mam kilka
: dodatkowych pytan:
Ja nauczylem sie struktur danych korzystajac z Internetu.
W USA duzo wykladow jest wywieszonych na WWW w dosyc przystepnej 
postaci.

: 2. I pytanie na temat tworzenia drzewa zrownowazonego.
: Nigdzie nie moge tego znalezc, a nie jestem pewny, czy moje
: rozumienie tego zagadnienia jest prawidlowe. A wiec, w celu
: uzyskania takiego drzewka, jesli od razu mam wszystkie dane
: (np. w formie tablicy), ktore mam rozmiescic na drzewie,
: wyliczam ich srednia arytmetyczna i jako pierwszy element na
: drzewie, wstawiam wartosc najblizsza sredniej. Tyle tylko,
: ze to ma jeden minus. Co bedzie jesli w tych danych, znajda
: sie elementy znacznie odbiegajace w gore, lub w dol od
: sredniej? A moze przy obiczaniu takiej sredniej wylaczyc np.
: 3 najwieksze i 3 najmniejsze elementy zbioru?
W ten sposob tworzy sie drzewo PRAWIE zrownowazone. Tak to sie
nazywa. Nie mamy prawie idealnego zrownowazenia, ale proces
rownowazenia wymaga malych nakladow obliczeniowych. Pisalem
na kolokwium taki program.

:     To bylo w miare proste, a jak tworzyc drzewo
: zrownowazone w sposob dynamiczny, w momencie, gdy dane,
: ktore chce przedstawic w formie drzewa beda sie pojawialy
: np. losowo? Czy moge, gdy znam zakres tych danych, np. od 0
: do 10000, sztucznie przyjac za moj korzen wartosc 5000 i nie
: brac jej pod uwage w trakcie dalszej pracy programu? Tyle
: tylko, ze to mi nie daje zadnej gwarancji, ze wszystkie
: pojwiajace sie wartosci nie beda jednak np. mniejsze od tej
: liczby. I znowu jestem w punkcie wyjscia. Aha, a nie biore
: pod uwage, ciaglego przekladania elementow, przy ich
: niewielkiej liczbie moze i bylo by to nie najgorsze
: rozwiazanie, ale przy bardziej rozbudowanych drzewach,
: coz...
Odpowiedz znajdziesz w algorytmie 'drzewa samokorygujace sie'.
Jest on opisany w ksiazce 'Algorytmy w jezyku C', czy jakos tak.
Ksiazka z zolta okladka.

--
---------------------------------
     Robert Kolaczynski
           M I S
  http://www.webcorp.com.pl