https://wiki.universitas.ro/index.php?action=history&feed=atom&title=1854_-_Arbore_Binar_Complet 2026-05-01T08:49:03Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=1854_-_Arbore_Binar_Complet&diff=9794&oldid=prev 2024-05-18T13:41:39Z

<p></p> <a href="//wiki.universitas.ro/index.php?title=1854_-_Arbore_Binar_Complet&amp;diff=9794&amp;oldid=9248">Show changes</a>

Oros Ioana Diana https://wiki.universitas.ro/index.php?title=1854_-_Arbore_Binar_Complet&diff=9248&oldid=prev 2024-01-08T21:13:53Z

<p>Pagină nouă: Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului sunt ocupate în întregime. În general, deși nu este obligatoriu, toate nodurile de pe ultimul nivel sunt grupate în partea stânga a acestuia. &lt;br&gt; Înălțimea unui arbore binare complet este [log2n]+1, unde n este numărul de noduri. Pentru reprezentarea unui arbore binar complet se poate folosi un tablou unidimensional A cu n elemente, în felul următor: *rădăcinii arbo...</p> <p><b>New page</b></p><div>Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului sunt ocupate în întregime. În general, deși nu este obligatoriu, toate nodurile de pe ultimul nivel sunt grupate în partea stânga a acestuia.<br /> &lt;br&gt;<br /> Înălțimea unui arbore binare complet este [log2n]+1, unde n este numărul de noduri.<br /> <br /> Pentru reprezentarea unui arbore binar complet se poate folosi un tablou unidimensional A cu n elemente, în felul următor:<br /> <br /> *rădăcinii arborelui îi corespunde elementul A[1];<br /> *dacă unui nod îi corespunde elementul A[k], descendentului stâng îi va corespunde elementul A[2*k], iar celui drept îi va corespunde elementul A[2*k+1].<br /> <br /> Observăm că pentru un nod A[k], nodul părinte este A[k/2], unde k/2 este câtul împărțirii, fără zecimale.<br /> <br /> Într-un arbore reprezentat astfel, nodurile de pe ultimul nivel sunt grupate în stânga. Dacă nodurile nu sunt grupate în stânga, sunt necesare câteva elemente în plus în vector, iar unele dintre ele nu vor fi folosite – nu vor avea un nod corespunzător.<br /> == Cerința ==<br /> Se dau n numere naturale, reprezentând în ordine valorile nodurilor dintr-un arbore binar complet și m operații de tip 1 sau 2, aplicate unui nod k.<br /> <br /> Operația de tip 1 determină valoarea nodului părinte a lui k, iar operația de tip 2 determină suma valorilor fiilor nodului k. Dacă k=1 sau dacă nodul k nu are fii, rezultatul va fi 0.<br /> <br /> Afișați pentru fiecare operație rezultatul ei.<br /> == Date de intrare ==<br /> Fișierul de intrare completin.txt conține pe prima linie numărul n, pe linia a doua n numere naturale, pe linia a treia m, iar pe următoarele m linii câte o pereche op k<br /> == Date de ieșire == <br /> Fișierul de ieșire completout.txt va conține rezultatele celor m operații, în ordine, câte unul pe linie.<br /> == Restricții și precizări ==<br /> *&#039;&#039;&#039;1 ≤ n ≤ 100000&#039;&#039;&#039;<br /> *cele n numere citite vor fi mai mici decât 1.000.000<br /> *&#039;&#039;&#039;1 ≤ m ≤ 100000&#039;&#039;&#039;<br /> *&#039;&#039;&#039;1 ≤ op ≤ 2&#039;&#039;&#039;<br /> *&#039;&#039;&#039;1 ≤ k ≤ n&#039;&#039;&#039;<br /> == Exemplul 1 ==<br /> ; completin.txt<br /> : 12<br /> : 15 5 18 35 32 23 12 43 29 25 22 13<br /> : 8<br /> : 2 9<br /> : 1 7<br /> : 2 5<br /> : 1 8<br /> : 1 1<br /> : 2 6<br /> : 1 9<br /> : 2 4 <br /> ; completout.txt<br /> : 0<br /> : 18<br /> : 47<br /> : 35<br /> : 0<br /> : 13<br /> : 35<br /> : 72<br /> &lt;br&gt;<br /> == Exemplul 2 ==<br /> ; completin.txt<br /> : 8<br /> : 4 8 2 6 7 1 9 3<br /> : 6<br /> : 1 5<br /> : 2 6<br /> : 1 4<br /> : 2 1<br /> : 1 3<br /> : 2 8<br /> ; completout.txt<br /> : 5<br /> : 0<br /> : 12<br /> : 12<br /> : 2<br /> : 0<br /> &lt;br&gt;<br /> == Rezolvare == <br /> &lt;syntaxhighlight lang=&quot;python&quot; line&gt;<br /> #1854 - Arbore Binar Complet<br /> def parent(k):<br /> return k // 2 if k != 1 else 0<br /> <br /> def children_sum(k):<br /> left_child = 2 * k<br /> right_child = 2 * k + 1<br /> left_value = values[left_child] if left_child &lt;= n else 0<br /> right_value = values[right_child] if right_child &lt;= n else 0<br /> return left_value + right_value<br /> <br /> # Verificare restricții<br /> if not (1 &lt;= n &lt;= 100000 and all(1 &lt;= value &lt; 1000000 for value in values) and 1 &lt;= m &lt;= 100000 and all(1 &lt;= op &lt;= 2 and 1 &lt;= k &lt;= n for op, k in queries)):<br /> with open(&quot;completout.txt&quot;, &quot;w&quot;) as fout:<br /> fout.write(&quot;Fals\n&quot;)<br /> else:<br /> # Executarea operațiilor și scrierea rezultatelor în fișierul de ieșire<br /> with open(&quot;completout.txt&quot;, &quot;w&quot;) as fout:<br /> for query in queries:<br /> op, k = query<br /> if op == 1:<br /> # Operația 1: valoarea nodului părinte al lui k<br /> fout.write(f&quot;{values[parent(k)]}\n&quot;)<br /> elif op == 2:<br /> # Operația 2: suma valorilor fiilor nodului k<br /> fout.write(f&quot;{children_sum(k)}\n&quot;)<br /> <br /> <br /> &lt;/syntaxhighlight&gt;</div>

Oros Ioana Diana