🚀 go-pugleaf

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/