Pa, ako znas sta je rekurzija (btw za one koji ne znaju: kucaj na googlu "recursion" pa klikni na "did you mean: recursion" :) - to je jedan od googleovih easter egg-ova) onda ti dodje nekako prirodno da znas kad treba da je upotrebis..
Recimo, taj pomenuti zadatak bih odmah krenuo da radim pomocu rekurzije, jer ne znam koliko duboko stablo moze da bude. Naravno, rekurzija moze da se izbegne ali kao sto rekoh u tim slucajevima je rekurzija "prirodno" resenje koje se prosto samo namece.
Evo kako bih ja razmisljao da sam dobio taj zadatak:
1. zamislim (nacrtam ako treba) to binarno stablo:
Code:
+---+
1 | |
+-+-+
|
+-------------+-------------+
| |
+-+-+ +-+-+
2 | | | |
+-+-+ +-+-+
| |
+--------+--------+ +--------+
| | |
+-+-+ +-+-+ +-+-+
3 | * | | | | |
+---+ +-+-+ +-+-+
| |
+--------+ +--------+
| |
+-+-+ +-+-+
4 | * | | * |
+---+ +---+
* Koristim [code][/code] tagove da bi se drvo lepo "iscrtalo". Brojevima su oznaceni nivoi (dubina) stabla, zvezdicama (*) su oznaceni listovi.
2. u zadatku se trazi "visina najnizeg lista (sa najmanjom razdaljinom od korena)" (ja sam navikao da tu "visinu" nazivam "dubinom", ali je to svejedno), ako pogledamo "sliku" to je list na trecem nivou (ovaj skroz levo). Zasto? Pa zato sto je on najblizi korenu od sva tri lista. Razdaljinu nekog cvora (list je isto cvor, samo bez dece) dobijemo tako sto brojimo cvorove krecuci se uz stablo sve do korena:
Uzmimo da su nam ova tri lista oznacena sa A, B i C (gledajuci sliku, sa leva na desno), krenemo redom:
- A = 1 (A je list na 3. nivou)
- "pogledamo" iznad u hijerarhiji da li postoji parent cvor, postoji, uvecamo A za 1, A je sada 2
- sada pogledamo da li taj parent node ima svog parenta, ima, uvecamo A za 1, A je sada 3
- sada opet pogledamo da li taj poslednji element koji smo gledali ima parenta, nema. Znaci stigli smo do korena stabla, pamtimo da je A = 3
- istim postupkom dobijamo B = 4 i da je isto tako C = 4 (na istom su nivou)
Posto je A manji i od B i od C dolazimo do zakljucka da je A onaj list koji se trazi u zadatku (zapravo, trazi se samo na kojoj dubini se on nalazi, ne sam list, tj vrednost koju sadrzi..)
3. Dakle, sada samo ovaj postupak kojim smo "peske" dosli do resenja treba da uoblicimo u algoritam. Kljucna stvar u postupku je da smo krenuli od listova, ne od korena (odozdo, ne odozgo), to je poenta rekurzije, razmisljas odozdo na gore, spolja ka unutra. Dalje, u zadatku pise da dobijamo referencu na koren drveta, sto znaci da moramo prvo da dodjemo od korena do svih listova pa onda da vratimo dubinu najblizeg.
Ako zamislimo sledece situacije:
Code:
1
====================================== (a)
+---+
1 | |
+---+
====================================== (b)
+-+-+
1 | |
+-+-+
|
+--------+
|
+-+-+
2 | |
+---+
====================================== (c)
+-+-+
1 | |
+-+-+
|
+--------+--------+
| |
+-+-+ +-+-+
2 | | | |
+---+ +-+-+
====================================== (d)
Vidimo da drvo moze da bude prazno (a) odnosno da je root == null, zatim, drvo moze da ima samo koren (b), ili samo jedno dete (c) ili oba deteta (d). Ova cetiri slucaja su dovoljna, jer ako bilo koji cvor u stablu posmatramo kao koren (mozemo da kazemo da je to koren podstabla) primeticemo da (b), (c) i (d) slucajevi vaze i kod tog cvora.
Sad imamo sve potrebne informacije da napisemo rekurzivni algoritam (znaci poenta je da se nadje najmanji skup svojstava koji vazi za svaki clan strukture kroz koju cemo se prosetati rekurzijom).
1. korak:
Code (java):
public int najvisiList(Node root) {
if (root == null) return 0; // slucaj pod (a)
}
2. korak:
Code (java):
public int najvisiList(Node root) {
if (root == null) return 0; // slucaj pod (a)
if (root.l == null && root.d == null) return 1; // slucaj pod (b)
}
3. korak:
Code (java):
public int najvisiList(Node root) {
if (root == null) return 0; // slucaj pod (a)
if (root.l == null && root.d == null) return 1; // slucaj pod (b)
// slucaj pod (c)
if (root.l != null && root.d == null) { // imamo samo levo dete
return 1 + najvisiList(root.l); // dodajemo 1 da bi uracunali i nivo na kome se nalazi trenutni cvor koji posmatramo
}
if (root.l == null && root.d != null) { // imamo samo desno dete
return 1 + najvisiList(root.d);
}
}
4. korak:
Code (java):
public int najvisiList
(Node root
) {
if (root
== null) return 0; // slucaj pod (a)
if (root.
l == null && root.
d == null) return 1; // slucaj pod (b)
// slucaj pod (c)
if (root.
l != null && root.
d == null) { // imamo samo levo dete
return 1 + najvisiList
(root.
l); // dodajemo 1 da bi uracunali i nivo na kome se nalazi trenutni cvor koji posmatramo
}
if (root.
l == null && root.
d != null) { // imamo samo desno dete
return 1 + najvisiList
(root.
d);
}
// slucaj pod (d)
int l
= najvisiList
(root.
l); // uzimamo dubinu najblizeg lista u podstablu sa korenom u root.l
int r
= najvisiList
(root.
d); // uzimamo dubinu najblizeg lista u podstablu sa korenom u root.d
return 1 + Math.
min(l, r
); // uzimamo najvisi list od dva dobijena i vracamo njegovu dubinu uvecanu za 1
}
I to je to, ovaj kod radi ono sto treba. Ali mozemo da objedinimo 3. i 4. korak i da tako optimizujemo trenutni kod. Ako pogledamo kod za slucaj (d) vidimo da on vraca manji od levog i desnog + 1, ako dalje pogledamo kod za slucaj (a) vidimo da funkcija vraca 0 ukoliko joj prosledimo nevalidan objekat. Izgleda da mozemo da izbacimo kompletan kod za slucaj (c), dobijamo:
Code (java):
public int najvisiList
(Node root
) {
if (root
== null) return 0; // slucaj pod (a)
if (root.
l == null && root.
d == null) return 1; // slucaj pod (b)
// slucaj pod (d)
int l
= najvisiList
(root.
l); // uzimamo dubinu najblizeg lista u podstablu sa korenom u root.l
int r
= najvisiList
(root.
d); // uzimamo dubinu najblizeg lista u podstablu sa korenom u root.d
return 1 + Math.
min(l, r
); // uzimamo najvisi list od dva dobijena i vracamo njegovu dubinu uvecanu za 1
}
Ali, ovo vise nije ispravan algoritam! Ukoliko cvor ima samo jedno dete dobicemo:
Code (java):
l
= 123; // neki broj > 0, posto je root.l != null
r
= 0; // root.d == null pa nam prvi if vraca nulu
return 1 + Math.
Min(123,
0); // dobicemo 1 a ne 124!
Najjednostavnije resenje je da umesto nule vratimo neku veliku vrednost, za koju pretpostavljamo da ce biti uvek veca od dubine drveta, Integer.MAX_VALUE je sasvim pogodan broj za tu namenu, i zato cemo njega da uzmemo:
Code (java):
public int najvisiList
(Node root
) {
if (root
== null) return Integer.
MAX_VALUE; // slucaj pod (a)
if (root.
l == null && root.
d == null) return 1; // slucaj pod (b)
// slucaj pod (d)
int l
= najvisiList
(root.
l); // uzimamo dubinu najblizeg lista u podstablu sa korenom u root.l
int r
= najvisiList
(root.
d); // uzimamo dubinu najblizeg lista u podstablu sa korenom u root.d
return 1 + Math.
min(l, r
); // uzimamo najvisi list od dva dobijena i vracamo njegovu dubinu uvecanu za 1
}
nakon poslednje "optimizacije" (samo skracujemo kod, ne dobijamo ni na smanjenu instrukcija ni memorije) imamo kod:
Code (java):
public int najvisiList
(Node root
) {
if (root
== null) return Integer.
MAX_VALUE;
if (root.
l == null && root.
d == null) return 1;
return 1 + Math.
min(najvisiList
(root.
l), najvisiList
(root.
d));
}
Sto je kod koji si ti postovao.
Dakle eto kako bih ja dosao do tog algoritma, koja istina ima jedan mali nedostatak, ukoliko mu prosledimo prazno drvo (drvo koje nema cak ni koren) dobicemo Integer.MAX_VALUE (2^31 - 1) sto nije bas tacno, tacan rezultat u tom slucaju bi bio 0. Ali eto savrsenog upozorenja da se stavi u dokumentaciju funkcije! :)
edit: izmenjeni dijagrami
[Ovu poruku je menjao Aleksandar Ružičić dana 30.07.2011. u 04:33 GMT+1]
Problem sa rekurzivnim razmisljanjem
