Imprimă pagina - Parcurgere

Titlul: Parcurgere
Scris de: Paul-Dan Baltescu din Decembrie 23, 2011, 22:22:48

Discutati aici pe marginea postului Parcurgere (http://infoarena.ro/blog/interviu-parcurgere).

Titlul: RÄƒspuns: Parcurgere
Scris de: Andrei Misarca din Decembrie 23, 2011, 22:53:15

MÄƒ gÃ¢ndesc cÄƒ ar trebui sÄƒ meargÄƒ ceva de genul

Cod:

void go(Node* node) {
    if (node -> left) {
        go(node -> left);
    }
    cout << node -> info; //sau ceva care sa arate ca am trecut prin nodul respectiv
    if (node -> right) {
        go(node -> right);
    }
}

Titlul: RÄƒspuns: Parcurgere
Scris de: Adrian Budau din Decembrie 23, 2011, 22:55:04

Aici memoria se tot declara pe stiva pana la adancimea arborului. Gen daca ai un arbore lant ai go(radacina) in care ai go(radacina -> left) in care ai go(radacina -> left -> left) s.a.m.d in total memoria fiind inaltimea arborului(care nu e O(1)).

Solutie:
Ma gandesc ca daca se poate modifica arborele(adica informatiile left, right nu sunt constante) ar merge sa modificam arborele astfel incat sa avem un query liniar(adica un query apeleaza doar unul singur nu mai multe ca sa se poata rezolva totul iterativ) de forma(unde sunt, de unde vin) si la orice moment arborele curent traversat in inordine sa ne dea ce ne dorim(chair daca forma lui nu e cea initiala).

Sa ne gandim ca mereu suntem in radacina. Si avem query(current_node, father_node). Trebuie dupa ce traversam acest nod sa trecem prin nodul tata. Deci putem modifica astfel nodul curent:
1) Tinem minte fiul stang
2) Fiul drept devine fiul stang
3) father_node(nodul in care trebuie sa ne intoarcem) devine fiul drept.

Iar apoi facem query din nou pentru fiul stang si nodul curent.

Cod:

Node *current_node, *father_node, *NIL;
current_node = root;
father_node = NIL = new Node(); // sa stim cand sa ne oprim facem un nod special
while(current_node != NIL) {
    Node *temporary_node = current_node -> left;
    current_node -> left = current_node -> right;
    current_node -> right = father_node;

    father_node = current_node;
    if (current_node -> left != 0) {
        current_node = current_node -> left;
    }
    else {
        current_node = current_node -> right;
    }
}

Sper ca e corect ce zic.

L.E: E gresit. E foarte gresita.

Titlul: RÄƒspuns: Parcurgere
Scris de: Andrei Misarca din Decembrie 23, 2011, 22:58:57

Ah, da, ai dreptate :)

Titlul: RÄƒspuns: Parcurgere
Scris de: Sturzu Antonio-Gabriel din Decembrie 23, 2011, 23:19:06

Daca se poate modifica arborele cred ca merge si o chestie gen inversare de lista simplu inlantuita
care se poate face cu memorie O(1) iterativ. Cand cobori in arbore tot timpul inversezi legaturile ca sa poti sa te intorci iar
cand te intorci refaci legaturile astfel incat la sfarsit arborele sa fie nemodificat. Poate imi scapa ceva ca sunt cam obosit la ora
asta.

Titlul: RÄƒspuns: Parcurgere
Scris de: Gabi Szocs din Decembrie 24, 2011, 11:09:06

Cel mai simplu cred ca e sa pornesti mereu de la radacina si cand ajungi la o frunza o faci 0xffffff.. in parinte apoi pornesti iarasi de la radacina. Astfel poti deosebi intre copiii vizitati si cei inexistenti(NULL).

In felul asta informatia necesara marcarii portiunii de arbore vizitat (partea neconstanta in parcurgere) se memoreaza in structura arborelui.

Titlul: RÄƒspuns: Parcurgere
Scris de: Cosmin Negruseri din Decembrie 24, 2011, 13:12:30

Bagati si cod sa vedem cum arata niste solutii scurte si curate. N-ar trebui sa fie prea greu si in interviu probabil s-ar cere si codul sursa nu doar ideea.

Titlul: RÄƒspuns: Parcurgere
Scris de: Paul-Dan Baltescu din Decembrie 24, 2011, 13:52:31

Are dreptate Cosmin. :)

Sfat: E ok sa modificati pe parcurs structura arborelui, atat timp cat la final ramane aceeasi structura.

Titlul: RÄƒspuns: Parcurgere
Scris de: Mircea Digulescu din Decembrie 24, 2011, 14:20:08

Va propun si o variatiune:

Daca arborele nu poate fi modificat (sa ziceam ca lucrurile se petrec intr-un scenariu distribuit si sunt mai multi acceseaza arborele pentru citire), este posibil sa se scrie un program care sa foloseasca O(1) spatiu total si care sa "enumere" in inordine nodurile arborelui?

Se poate gandi ca exista un API:

Nod Left(Nod);
Nod Right(Nod);
void Emit(Nod);

Titlul: RÄƒspuns: Parcurgere
Scris de: Popescu Silviu din Decembrie 24, 2011, 16:33:09

Salut

Daca s-a zis solutia va rog frumos sa ma scuzati :D.
M-am gandit la urmatorul algoritm: cand parcurgi nodurile de fiecare data faci o "shiftare la dreapta" ( adica left devine right si right devine parinte , se poate face usor tinand parintele ) , apoi cand nodul meu este NULL il inversez cu parintele. Conditie de oprire: t este NULL si parintele este radacina :D.

Cod:

void parcurgere(Node *T)
{
	Node *p=NULL,*f=T,*aux;
	
	while (f!=NULL || p!=T)
	{
		if ( f )
		{
			//printf("%d ",f->x);
			aux=p;p=f;f=p->left;
			p->left=p->right;
			p->right=aux;
			continue;
		}
		swap(f,p);
	}
}

Ar trebui sa si demonstrez ca e corect :D .
In primul rand , in fiecare nod o sa ajungem de 3 ori ( odata din radacina , apoi sin left si right ), deci dupa parcurgere arborele ramane neschimbat.
La fiecare nod vom parcurge in ordinea left , right , parent ( de fiecare data left se schimba cu right ).
La radacina , vom parcurge in ordina left , right , parent ( moment in care vom fi pe nodul NULL si parintele lui va fi radacina ).

Sper ca s-a inteles ce am vrut sa zic :D

Titlul: RÄƒspuns: Parcurgere
Scris de: Adrian Budau din Decembrie 27, 2011, 17:36:10

Cred ca totusi cea mai simpla varianta e sa rotim arborele la dreapta(sau stanga nu-mi amintesc exact) pana cand arborele devine lant. Daca faci asta cat nu mai poti in nodul curent si apoi te duci in nodul din dreapta si repeti procedeul complexitatea e O(N) si memoria e O(1).

Cod:

Cod:

for (Node* i = root; i != 0; i = i -> right) {
    while (i -> left != 0) {
        Node* temp = i -> left;
        i -> left = i -> left -> right;
        temp -> right = i;
        i = temp;
    }
    // aici putem face ce vrem cu nodul curent.
}

Cred ca e O(N) complexitatea pentru ca un nod nu trece in locul tatalui sau decat o data.
Dezavantajul: nu mai avem structura initiala :(.

infoarena

Comunitate - feedback, proiecte si distractie => Blog => Subiect creat de: Paul-Dan Baltescu din Decembrie 23, 2011, 22:22:48