[edit] Ideea de bază
Să luăm o structură de date ca o matrice dinamică. În punerea în aplicare standard, suntem capabili de a adăuga elemente la sfârșitul vectorului, să recunoască valoarea elementului într-o anumită poziție, pentru a schimba elementul de numărul și elimină ultimul element. Să presupunem că avem nevoie de o structură de date cu proprietățile de mai sus, precum și operațiuni: adăuga un element în orice locație (cu elemente de schimbare corespunzătoare de numerotare) și pentru a elimina orice element (de asemenea, renumerotează în mod corespunzător). O astfel de structură poate fi pusă în aplicare pe baza arborelui cartezian, rezultatul este adesea numit cartezian pe arbore cheie implicită (Ing. Treap cu tasta implicită).
[edit] Cheia X
După cum știți, un arbore cartezian este o structură de date care combină un arbore binar de căutare și un heap binar. Când implementăm arborele cartezian printr-o cheie implicită, modificăm această structură. Și anume, aceasta conține doar o prioritate, dar în schimb va utiliza următoarea valoare cheie: numărul de elemente din structura noastră, situată în partea stângă a elementului nostru. Cu alte cuvinte, vom lua ca cheie numărul ordinal al elementului nostru în arbore, redus cu unul.
Rețineți că aceasta va păstra structura arborelui binar de căutare pentru această cheie (adică copacul cartezian modificat va rămâne un copac cartezian). Cu toate acestea, prin această abordare apare o problemă: operațiunile de adăugare și eliminare a unui element pot schimba numerotarea și cu o implementare naivă, modificarea tuturor cheilor necesită timp, unde este numărul elementelor din arbore.
[edit] Valoarea auxiliară a lui C
Această problemă este rezolvată destul de simplu. Ideea principală este că o astfel de cheie în sine nu este stocată nicăieri. În schimb, acesta va stoca valoarea auxiliară: numărul de noduri din subarborele vertex nostru (și subarborele în vârful este pornit). Să fim atenți că toate operațiile cu un copac cartezian obișnuit au fost făcute de sus. De asemenea, rețineți că în cazul în care calea de la rădăcină la unele vârfuri însumează toate aceste valori în subarborele din stânga, în care noi nu am mers, plus unu, apoi a venit la foarte sus și adăugarea la valoarea numărului de elemente din subarborele stâng, obținem ca odată ce este cheia.
[edit] Operațiile care susțin structura arboretelor carteziene
Structura convențională arbore cartezian este sprijinit prin intermediul a două operații: - partiționare un Treap în două astfel încât o singură cheie este mai mică decât o valoare predeterminată, iar în celelalte - mai mari și îmbinarea - doi arbori, într-una dintre care toate cheile mai putin în al doilea. Având în vedere diferențele dintre arborele cartezian pe tasta implicită de la normal, operațiunile vor fi acum descrise după cum urmează: - copac partiție în două, astfel încât stânga va fi exact partea de sus, și - fuziunea oricăror doi copaci, respectiv.
[modifică] Împărțit
Procedura trebuie să înceapă la rădăcina copacului cu cerința de a tăia arborele de vârfuri. Este, de asemenea, cunoscut faptul că există noduri în subordonatul din stânga al vârfului și în subordonatul drept. Să luăm în considerare toate cazurile posibile:
- . În acest caz, trebuie să inițiați recursiv procedura de la fiul stâng cu același parametru. În același timp, noul fiu stâng al rădăcinii va fi partea dreaptă a răspunsului la procedura recursivă, iar rădăcina răspunsului va fi cea corectă.
- Cazul este simetric cu cel precedent. În mod recursiv, executăm procedura de la fiul potrivit cu un parametru. Noul fiu drept al rădăcinii va fi partea stângă a răspunsului la procedura recursivă, iar rădăcina răspunsului va fi la stânga.
[modifică] Mergeți
Să vedem toate implementările procedurii. Rețineți că programul nu accesează niciodată cheia. Prin urmare, punerea în aplicare a procedurii pentru un copac cartesian printr-o cheie implicită nu va fi deloc diferită de punerea în aplicare a aceleiași proceduri într-un copac cartezian obișnuit.
[citare necesară] Menținerea corectitudinii valorilor C
Singura acțiune care va asigura corectitudinea acestor valori este că după orice acțiune cu copii se află în fruntea trebuie să fie scrise în domeniul său, suma acestor valori în noul ei copii a crescut cu unul.
[edit] Aplicarea arborelui descris
Astfel, este descrisă o structură, din care este posibilă tăierea unei părți dintr-o lungime arbitrară spre stânga și îmbinarea a două părți în una în ordinea dorită. Acum avem ocazia:
- inserați elementul în orice loc (tăiați cantitatea potrivită de elemente din stânga, îmbinați copacul stâng cu arborele dintr-un element adăugat și rezultatul - cu copacul din dreapta),
- pentru a rearanja orice piesa a matricei oriunde (vom face tăieturile necesare și vom fuziona în ordinea corectă),
- efectuați operații de grup cu elemente. Să ne amintim implementarea unor astfel de operațiuni în arborele segmentelor și să înțelegem că nimic nu ne va împiedica să facem același lucru cu arborele descris. În operațiunile de grup, desigur, funcția este preluată din segment,
- făcând doi arbori pe aceeași matrice de surse din elemente de paritate diferite, puteți rezolva problema schimbării locurilor de locuri par și impare pe un segment,
- folosind ideile copacului cartezian pe o cheie implicită, puteți implementa o structură de date precum Rope.
[edit] Vezi, de asemenea
[edit] Surse de informare
Trimiteți-le prietenilor: