Forum 1 Grupy Ćwiczeniowej

denciaq

moze ma ktos jakas strone gdzie rotacje w drzewach avl sa objasnione?

vbazyl

[link widoczny dla zalogowanych]

i np 4 odnośnik

boro

fajny aplet pokazujacy istote drzewa AVL

[link widoczny dla zalogowanych]

fala (aka tomek)

A może inaczej... Ma ktoś implementację drzewa AVL i użyczył by kodu? Wink

czart

Wrzuciłem w [link widoczny dla zalogowanych] do katalogu '2 rok'.

Niestety rotacje przy usuwaniu jeszcze nie za dobrze działają ;d

edit1: ok wrzucilem dzialajacego, enjoy

format pliku:

fala (aka tomek)

Strasznie dziwny ten format pliku...
A może ktoś będzie mi w stanie powiedzieć... Jeśli chcem wyliczyć te współczynniki wyważenia... nie da się ich wyliczyć posiadając same współczynniki... trzeba liczyć za każdym razem wysokści poddrzew?

czart

Tylko w dodawaniu da sie po samych współczynnikach raczej. (przynajmniej ja tak zrobilem). Jeśli po dodaniu waga rodzica przechodzi w 0 to znaczy że wysokość drzewa się nie zmieniła. W innym przypadku idziemy w góre po rodzicach w strone korzenia (odpowiednio dodajac 1 lub -1 do wagi) i zatrzymujemy się na pierwszej wadze 0, -2,2(rotacje), lub korzeniu.

W usuwaniu kombinowałem ale doszedłem do wniosku że sie nie da.

Zauważ jeszcze że po rotacjach mamy już określone wagi części wezłów (zerują się)

thrower : czemu dziwny ? Mozna od razu do niego zajrzec i rozrysowac na kartce i sprawadzic ;d

fala (aka tomek)

No widzisz, wszystko pięknie ładnie... Tylko tyle że w treści zadania, przynajmniej w mojej grupie było konkretnie podane jaki ma być ten plik wejściowy -> praktycznie ciurkiem słowa oddzielone spacjami.
Dodatkowo było zaznaczone że nie można stosować wskaźnika na rodzica, co troszke komplikuje sprawę... jednak zaraz może uda mi się jakoś rozwiązać to przy pomocy stosu, tak jak koszelew sugerowała...
mam tylko właśnie problem z tym jak wyliczać wagi poszczególnych wierzchołków...
no bo ok, dodaje nowy wierzchołek i ustawiam mu wagę na 0, tylko tak teraz nie bardzo mogę wpaść na pomysł w jaki sposób mam zrealizować to uaktualnianie wcześniejszych wierzchołków... wiem że jak jest po lewej to +1 jak po prawej to -1...
no tylko teraz co, wziąć element poprzedni i sprawdzić czy z prawej czy z lewej jest ten nowy element... a jak dalej? szczerze mówiąc to nie bardzo wiem jak to zrobić z samych współczynników no bo może być np też taka sytucja:

czart

Jesli masz stos = sciezke po ktorej szedles wstawiajac element to bierzesz pierwszy element ze stosu i sprawdzasz

elem->l == wstawiony_element => jest wstawiony z lewej
elem->r == wstawiony_element => jest wstawiony z prawej

edit:
Jak wiesz z ktorej strony zostal wstawiony "cofasz sie na drzewie", uaktualniasz wage i lecisz dalej, chbya ze nowa waga wyniosla 0 (wtedy konczymy dzialanie wstawiania bo wysokosc drzewa sie nie zmienila), -2,2 (bo wtedy trzeba wykonac rotacje, po ktorej tez od razu konczymy wstawianie)

Z kim masz asd ze nie mozesz miec wskaznik na rodzica ?

edit2:
jesli wskaznik1==wskaznik2 zwraca true to znaczy ze pokazuja na ten sam obiekt

Linka · Dołączył: 13 Mar 2007 Posty: 98 Przeczytał: 0 tematów Ostrzeżeń: 0/5

Mamy z Borowską :/ @#$%&

fala (aka tomek)

fala (aka tomek)

Pi3p^20n3 rotacje... ;/ wagi już mi chyba dobrze ustawia, ale na rotacjach wykłada się popisowo :]
może ma ktoś inserta z rotacjami w C napisanego?

fala (aka tomek)

denciaq, weź zapodaj to co ona ci tam kazała przerobić żeby sprawdzić czy drzewo działa... najlepiej kod z jakimś komentarzem co i jak... z gory dzieki wielkie

Dudi

ja zrobiłem tak:

fala (aka tomek)

Ja to u siebie miałem zrobione tak jak było w wykładzie p. Koszelew, wagi ustawiałem po prostu ręcznie dla odpowiednich węzłów, tak jak na tamtych rysunkach było...

[link widoczny dla zalogowanych]
Tutaj jest to zajebiście rozpisane, tylko trzeba wziać poprawkę że + i - odwrotnie trzeba brać (bo tutaj odwrotnie są wzięte wagi).
Szukać gdzieś tak w połowie wysokości na środku strony tabelek (wcześniej są przeprowadzone wyliczenia i wyprowadzone wzorki w jaki sposób się te wagi zmieniają)