Sortarea arbore parțial ordonat

În arborele binar, care este construit în această metodă de sortare pentru fiecare nod următoarea afirmație este adevărată: valoarea cheii înregistrată în nodul este mai mică decât cheile copiilor săi. Există cerințe la relația dintre descendenții cheile pentru un copac complet ordonat. Pentru acest copac nu sunt astfel de cerințe, astfel încât acest copac se numește parțial ordonată. În plus, copacul nostru să fie complet echilibrat. Acest lucru înseamnă nu numai că lungimea drumului de oricare două frunze diferă cu mai mult de 1, dar, de asemenea, faptul că atunci când adăugați un element nou la preferința copac este întotdeauna dat la stânga ramură / sub-ramură, atâta timp cât nu deranjează echilibrul. Pentru mai multe detalii Copaci acoperite în capitolul 6.

De exemplu, numere de secvență:

20 12 58 3 35 30 32 28

Acesta va fi prezentat sub forma unui arbore prezentat în figura 3.15.

Figura 3.15. arbore partial ordonat

Copacul sub forma unei piramide ne arată în mod clar că acest copac poate introduce conceptul de „început“ și „sfârșit“. Început fi în mod natural considerat un vârf al piramidei, iar capătul - lateral stânga elementului în stratul inferior rând (în figura 3.15 este 58).

Pentru a sorta prin această metodă ar trebui să fie determinată prin două operații: se introduce un nou element de copac și aducă lemn element de minim; și punerea în aplicare a oricăreia dintre aceste operațiuni nu trebuie să încalce orice tip de lemn prin care se dispune parțial menționat mai sus, nici echilibrul.

Algoritmul de inserare este după cum urmează. Noul element este inserat la primul loc disponibil la capătul arborelui (Figura 3.15 pe locul indicat prin simbolul „*“). În cazul în care este introdus în elementul cheie este mai mică decât cheia strămoșul său, stramosul și elementul introdus sunt inversate. Elementul cheie este acum introdusă este comparat cu cheia de societatea sa mamă într-un loc nou, etc. Comparația se încheie atunci când noul element cheie este mai mare decât cheia strămoș sau atunci când un element nou „va apărea“ în vârful piramidei. Piramida, prezentată în figura 3.15, este construit exact includerea consecventă a numerelor din seria de mai sus. Dacă includem în ea, de exemplu, are numărul 16, piramida va lua forma prezentată în figura 3.16. (Simbolul „*“ etichetat elemente deplasate în această operațiune.)

Figura 3.16. comandat parțial element de incluziune copac

Procedura de eșantionare element este ceva mai complicat. Este evident că elementul minim este în partea de sus. După prelevarea de probe din spațiul eliberat este aranjat un meci între descendenții și vârful este mutat descendent cu cea mai mică valoare cheie. Pentru locul vacant un urmaș agitat concura descendenții săi, etc. până când spațiul liber scade la piramida foaie. Starea arborelui nostru după un eșantion din acesta numărul minim (3) este prezentat în ris.3.17.a.

Ris.3.17. arbore partial ordonate, element excepție

Comandat de copac este restaurat, dar a încălcat o condiție a echilibrului său, ca spațiu nu este la capătul arborelui. Pentru a restabili echilibrul ultimul element din arborele este transferat în poziția vacantă, iar apoi „POP“ pe același algoritm care este utilizat la inserarea. Rezultatul acestui fapt este prezentat în ris.3.17.b. de echilibrare

Înainte de a descrie exemplul programului care ilustrează sortarea unui arbore parțial ordonate - exemplul 3.13, atrag atenția asupra modului în care este reprezentat de un copac în memorie. Acest mod de reprezentare arbori binari într-o memorie statică (în matrice unidimensională) care pot fi aplicate altor sarcini. elementele din lemn sunt situate în fante adiacente pentru nivelurile de memorie. Primul este slotul de memorie alocată de sus. Dupa 2 fante - elementele doilea nivel, următoarele 4 sloturi de - al treilea etc. Lemnul ris.3.17.b cu, de exemplu, să fie liniarizată după cum urmează:

12 16 28 20 35 30 32 58

După toate programul de proba algoritmul de mai sus 3.13 nu necesită explicații speciale. Noi explica structura de numai exemplu. EXEMPLU conceput ca un modul complet de software pentru a fi utilizat în exemplul următor. Arborele in sine este reprezentat în variabila copac matrice nt este indicele primului element liber în matrice. Punctul de modulul de intrare:

· Procedura InitST - inițializarea modulului, setați valoarea inițială a nt;

· Funcția InsertST - pentru a introduce un element nou în copac; funcția returnează false, în cazul în care arborele este nici un spațiu disponibil, în caz contrar - adevărat;

· Funcția DeleteST - un eșantion de lemn elementului minim; funcția returnează false, în cazul în care arborele este gol, în caz contrar - adevărat;

· Funcția CheckST - verifica starea arborelui: cheia elementul minim este returnat ca un parametru de ieșire, dar elementul nu este exclus din copac; și valoarea de retur a funcției - 0 - în cazul în care arborele este gol, 1 - în cazul în care arborele nu este complet umplut, 2 - în cazul în care arborele este plin.

În plus față de unitatea de programare internă modul definit:

· Funcția în jos - coborâre oferă spațiu liber de la vârful piramidei în baza sa, funcția returnează indicele de spațiu liber după ce declanșatorul;

· Procedură Up - furnizarea elementului Surfacing la locația specificată.

Daca se aplica arbore partial ordonat sortare pentru secventa comanda a terminat dimensiune N, atunci este necesar să se introducă N ori, și apoi N ori - probă. Comanda Algoritm - O (N * log2 (N)), dar valoarea medie a numărului de comparații este de aproximativ 3 ori mai mare decât pentru un fel de turneu. Dar sortarea arborele parțial comandat are un avantaj semnificativ față de toți ceilalți algoritmi. Faptul că acest lucru este algoritmul cel mai convenabil pentru „sortare on-line“, atunci când secvența de sortat nu este fixat înainte de începutul de acest fel, și modificările în proces și pasta alternează cu probe. Fiecare modificare (adăuga / șterge elemente) necesită sortate secvență nu este mai mare de 2 * log2 (N) comparații și permutări, în timp ce altele necesită algoritmi cu o singură schimbare de reordonare a întregii secvențe „în totalitate“.

O sarcină tipică care necesită o astfel de sortare, sortarea are loc pe datele externe de memorie (fișiere). Primul pas este formarea unui tip de fișier de date de secvențe ordonate de lungime maximă posibilă cu o cantitate limitată de memorie RAM. Următorul exemplu de program (Exemplul 3.14) prezintă o soluție la această problemă.

Numărul de ordine, stocate în fișierul de intrare este citit element cu element, iar numărul citit incluse în copac. Atunci când arborele este umplut, următoarea citire din numărul fișierului este comparat cu ultimul număr derivat din fișierul de ieșire. În cazul în care un număr limitat de cel puțin ultima imprimate, dar mai puțin decât numărul situat în partea de sus a arborelui, este considerat numărul afișat în fișierul de ieșire. În cazul în care un număr limitat de cel puțin ultima tipărite, și nu mai puțin decât numărul care este în partea de sus a arborelui, apoi numărul de ieșire fișier de ieșire ales din copac, și un număr limitat intrat în copac. În cele din urmă, în cazul în care un număr limitat mai mică decât ultima imprimate, apoi elementul de element este selectat și afișează întregul conținut al arborelui, și formarea unei noi secvențe începe odată cu intrarea în copac gol citit numere.