Сортиране частично подредени дърво

В двоичен дърво, което се изгражда в този метод на сортиране за всеки възел следното твърдение е вярно: ключовата стойност, отчетена в възел е по-малко от ключовете на своите деца. Има изисквания към връзката между потомците на ключовете за напълно наредено дърво. За това дърво не са определени такива изисквания, така че това дърво се нарича частично наредено. Освен това, нашите дърво, за да бъде напълно балансиран. Това означава не само, че дължини на пътя на всеки два листа се различават с не повече от 1, но също така и факта, че при добавяне на нов елемент към предпочитание дърво винаги се дава на левия клон / подотрасъла, стига да не пречи на баланса. За повече подробности дървета, обхванати в глава 6.

Например, номера на последователност:

3 20 12 58 35 30 32 28

Това ще бъде представен под формата на дърво е показано на фигура 3.15.

Фигура 3.15. Частично наредено дърво

Дървото под формата на пирамида ясно ни показва, че това дърво може да се въведе понятието "начало" и "край". Началото естествено да се разглежда като връх на пирамидата и края - най-левия елемент в най-долния ред (на фигура 3.15 е 58).

За да сортирате по този метод трябва да се определя от две операции: да се въведе нов елемент дърво и дърва минимален елемент; и изпълнението на всяка една от тези операции не трябва да нарушават частична поръчка дърво посочено по-горе, нито на неговия баланс.

вмъкване алгоритъм е както следва. Новият елемент се вкарва в първия свободно място в края на дървото (Фигура 3.15 на мястото, указано със символа "*"). Ако ключът е вкаран в елемент е по-малък от ключа на своя предшественик, родоначалник и добавя елемента са разменени. Ключов елемент в момента е поставена се сравнява с ключа на своята майка, на ново място, и т.н. Сравнение приключва, когато ключов Новият елемент е по-голяма от ключа за прародител или когато нов елемент "ще се появи" на върха на пирамидата. Pyramid, показан на фигура 3.15, е построен точно последователно включване на числата от горе серии. Ако се включи в него, например, има номер 16, пирамидата ще бъде под формата, показана на фигура 3.16. (Символът "*" маркиран разселени елементи в тази операция.)

Фигура 3.16. Частично нареди елемент включване дърво

Процедура за вземане на проби елемент е малко по-сложно. Очевидно е, че минималният елемент е най-отгоре. След вземане на проби от освободената пространство е уредил мач между потомците и върха се премества потомък с най-малката стойност на ключа. За вакантното място при разбъркване потомство конкурират неговите потомци, и т.н. докато в свободното пространство, пада до пирамидата на листа. Състоянието на нашето дърво, след проба от него минималният брой (3) е показано на ris.3.17.a.

Ris.3.17. Частично наредено дърво, изключение артикул

Поръчано дърво се възстановява, но е нарушил условие за неговото равновесие, тъй като пространството не е в края на дървото. За да се възстанови баланса на последния елемент в дървото се прехвърля на свободна длъжност, а след това "изскача" на същия алгоритъм, който се използва при поставяне. Резултатът от това е показано на балансиране ris.3.17.b.

Преди описанието дадения пример, илюстриращ сортиране частично наредено дърво - пример 3.13, привлека вниманието ви към начина, по който тя е представена като едно дърво в паметта. По този начин за представяне на двоични дървета в статична памет (в едномерен масив), които могат да бъдат приложени към други задачи. дървени елементи са разположени в съседни слота за нива на паметта. Първият слота се разпределя памет на върха. След 2 слот - елементите на второ ниво, следните 4 слотовете - трети и т.н. Wood ris.3.17.b с, например, се линеаризира както следва:

12 16 28 20 35 30 32 58

В края на краищата на програмата проба по-горе алгоритъм 3.13 не изисква специални обяснения. Ние обясни структурата на само пример. Пример проектиран като пълен модул на софтуер, за да се използва в следния пример. Дървото се е представена в променливата на дърво масив NT е индексът на първия свободен елемент в масива. Точката за входен модул:

· InitST процедура - инициализиране на модул, разположен на първоначалната стойност на NT;

· InsertST функция - за вмъкване на нов елемент в дървото; функцията връща фалшиви, ако дървото не е пространство, в противен случай - вярно;

· DeleteST функция - мостра от дърво минималната елемент; функцията връща фалшиви, ако дървото е празен, в противен случай - вярно;

· CheckST функция - да се провери състоянието на дървото: Ключът минималния елемент се връща като изходен параметър, но елементът не е изключено от дървото; и крайния резултат от изпълнението на функцията - 0 - ако дървото е празен, 1 - ако дървото не е изцяло попълнена, 2 - ако дървото е пълна.

В допълнение към вътрешния програмиране единица модул дефинирани:

· Функция Down - спускане осигурява свободно пространство от върха на пирамидата в основата му, функцията връща индекса на свободно пространство след затвора;

· Процедура Up - предоставяне настилка елемент на определено място.

Ако се прилага частично наредено дърво сортиране за поръчка на последователност приключи размер N, то тогава е необходимо да се добавят N пъти, а след това N пъти - примерни. Поръчка Алгоритъм - O (N * log2 (N)), но средната стойност на броя на сравненията е около 3 пъти по-голям, отколкото за турнир подобно. Но сортиране частично наредено дърво има едно значително предимство пред всички други алгоритми. Фактът, че това е най-удобен алгоритъм за "сортиране он-лайн", когато подредени последователност не е фиксирана преди началото на сорта, както и промени в процеса и паста се редуват с проби. Всяка промяна (добавяне / изтриване на елементи) да изисква от подредени последователност е не повече от 2 * log2 (N) сравнения и пермутации, докато други се нуждаят от алгоритми с една промяна на преподреждане на цялата последователност "изцяло".

Типичен задача, която изисква като сортиране, сортиране се извършва на данните външна памет (файлове). Първата стъпка е създаването на един вид файл с данни на поръчаните последователности от максималната възможна дължина с ограничено количество RAM. Следната програма пример (пример 3.14) показва решение на този проблем.

Поредният номер, съхранени в входния файл се чете елемент по елемент и броя четете включени в дървото. Когато дървото е пълен, следващата чете от номера на файла е в сравнение с последния номер, получен в изходния файл. Ако ограничен брой не по-малко в сравнение с миналата отпечатана, но по-малко от броя намира в горната част на дървото, се счита, номера, показан в изходния файл. Ако ограничен брой не по-малко в сравнение с миналата отпечатани, а не по-малко от броя, който е в горната част на дървото, а след това на изхода номера на изходния файл, избран от дървото, и ограничен брой вписани в дървото. И накрая, ако ограничен брой по-малко в сравнение с миналата отпечатване, точка по точка се избира и показва цялото съдържание на дървото, както и формирането на нова последователност започва с влизането в празното дървото чете числа.