🚀 go-pugleaf

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 **