1 страница. Бірінш ағаш сол жақтағы (1-сурет) ағашпен толық немесе толық емес түрде алу жолы бар

Сурет

Сурет

Бірінш ағаш сол жақтағы (1-сурет) ағашпен толық немесе толық емес түрде алу жолы бар. Мұндай ағаштар биіктігі Log₂n болады және оны массив түрінде көрсетілім жасау өте ыңғайлы (2-сурет). Ал екінші ағаштың (3-сурет) биіктігі n-ге тең болады және мұндай бинарлы ағаш көрсетілім типі біріншіге қарағанда қарама-қарсы болады (4-сурет). Алайда оның жадтаалатын орны әлдеқайда зор.

Сурет

Сурет

Осылайша, бұл әдісті кез келген ағаш түріне қолдана алу үшін ағашты қарастырып, сол жақтағасы толық болғанға дейін реттеу қажет екендігі анықталды.

Сурет

Бастапқы бинарлы ағаш тек бір бұтағы бар ағашка жақынарақ болған кезде, ағашты көрсетілімінің эффектілігі аз болады.

6. Бинарлы ағаш тұрғызу алгоритмі және олардың арнайы ерекшеліктері

Мысал арқылы түсіндірейік: 25,31,7,4,10,18,5,13 сан/ жиымы берілсін.

Алгоритм:

1) ағаштың төбесін береміз 25 саны (жиымның алғашқы элементі);

2) кейінгі элементті оның ағаш төбесінен кіші болса сол жақтан, үлкен болса оң жақтан бұтақ арқылы орналастырамыз;

3) кейінгі элементтердің орын/ы да олардың түбірден кіші н/е үлкен болуына байланысты сол жаққа немесе оң жаққа бұтақ арқылы орналастырып отырамыз.

31 25-тен үлкен оң жақта, ал 7 кіші ол сол жақта орналасады:

4-ті 25 пен салыстырамыз, 4 кіші 25-тен 25-тің сол жағына, 4-ті 7-мен салыстырамыз, 4 кіші 7-ден 7-нің сол жағына орналастырамыз. 10-ды 25-пен салыстырамыз, 10 кіші 25-тен 25-тің сол жағына, 10-ды 7-мен салыстырамыз, 10 үлкен 7-ден 7-нің оң жағына орналастырамыз.

18, 5, 13 сандары 25-тен кіші болғандықтан сол жақта орналасады. 18 7-ден үлкен және 10-нан да үлкен, 18 7-нің оң жағына және 10-ның оң жағына орналасады. 5 7-ден кіші және 4-тен үлкен, 5 7-нің сол жағына және 4-тің оң жағына орналасады. 13 7-ден үлкен, 10-нан үлкен, 18-ден кіші, 13 7-нің оң жағына, 10-ның оң жағына және 18-дің сол жағына орналасады.

Ескере кетейік, сол жақ бұтақта белгіленген түбірден кіші элементтер, ал оң жақ бұтақта белгіленген түбірден үлкен элементтер орналасады.

7. AVL ағашта сол жақ және оң жақ бұрылыс операциялары

Aлдымен бұрын тұрғызылған AVL ағашына жаңа төбелі қабырғаны жалғау ағаштың баланссыздығына әкеліп соғатынын ескерейік ж/е керісінше қабырғамен сәйкес төбемен бастапқы ағаштың қосу нүктесі болатын боялмаған төбе/ді жалғауда балансыздану болмайды.

1-сурет

Төбе қасындағы цифра осы төбенің балансы мәні.

AVL ағашқа жаңа төбе қосу кезінде бинарлы ағашты тұрғызудың қарапайым алгоритмі қолданылады. Осылайша, бар болған AVL ағашқа қайта қосылған төбе, оны N арқылы белгілейік, ағаш түбірі мен жаңа төбені қосатын ерекшеленген деп аталатын жол үшін ақырғы төбе болып табылады.

AVL ағашқа жаңа төбелер қосу есебі шешімін корректі түрде жүргізетін жалпы талаптарға тоқталып кетейік:

1. Осы түрлендіру нәт-де алынған бинарлы ағаш іздеудің бинарлы ағашы болу к/к;

2. Нәтижелік ағаш AVL ағашы болуы керек;

3. Түрлендіру жеткілікті түрде тиімді болуы керек.

Осыған байланысты, жаңа төбе қосқанға дейін AVL ағашы болған, бірақ балансы жаңа төбе қосу нәтижесінде бұзылған ағаштың ішкі ағаштарымен орындалатын екі операцияны қарастырайық. Қажет болған жағдайда бұл операциялар кез-келген бинарлы іздеу ағашымен жүргізіле алады.

Алғашқы операция сол жақ бұрылыс, мағынасын келесі сурет ұғындырады.

2-сурет

3-сурет

3 суретіндегі ағашты айналуда түйіндердің тізбегі симметриялы түрде сол қалыпында бастапқы ағаш 3 суреттегідей болады.

Сонда t_D={D}; t_E={E}; t_F={F}; t_G={G} шарты ушін бұл тізім D,B,E,A,F,C,G болады.

Осыған ұқсас ағашты оң жақ бұрылыс кезінде төмендегі суреттегідей орындалады.

4-сурет

Сонымен бинарлы іздеу ағашымен сол жақ немесе оң жақ бұрылыс операциясын орындау нәтижесінде алынған ағаш бинарлы іздеу ағашы болып қалады. Ескерте кетсек, сол жақ немесе оң жақ бұрылыс операциясын орындау онша қиын шаруа емес, себебі олардың әрбірін орындағанда тек үш сілтемені ғана қайта баптау керек және ең маңыздысы бұл t_D, t_E, t_F,t_G ішкі ағаштарынан тәуелсіз жүргізіледі. Егер жоғарыда келтірілген бұрылыстар схемасы түсініксіз болса, онда осыны қарапайым схемалар үшін қайталауға болады, мысалы, үш төбе мен 4-ші ішкі ағаш 5 сурет және 6 сурет.

Формальды түрде басқа жолдардың төбелерінің балансы да өзгеруі мүмкін, тек бұл жолдардың ішіндегі төбелер бір уақытта ерекшеленген жол төбелері болғанда ғана болады.

5-сурет

А төбесіндегі түбірлі ішкі ағаштың оң жақ бұрылысы

А төбесіндегі түбірлі ішкі ағаштың сол жақ бұрылысы

6-сурет

Әрине екі төбесі мен үш ішкі ағашы бар ағаштар үшін қарапайым бұрылыстар жасауға болады.

7-сурет

8. O(n log₂n) күрделілігімен сұрыптау

Қарастырылатын алгоритм таңдаумен сұрыптау алгоритмдері классына жатады. Бірақ бұл алгоритмнің өзінің ерекше қасиеттері бар. Біріншіден, бастапқы массив бинарлы ағашпен беріледі. Бұл бинарлы ағаш құрылысы жағынан ерекшеленіп келеді, ондай ағаштарды толықтау бинарлы ағаштар деп атайды. Реттеу процессі екі этаптан тұрады. Бірінші этапта пирамида тәріздес ағаш түзіледі. Екінші этапта құрылған ағаш пирамидасында түйіндеріне бекітілген массив элементтері түпкілікті реттеуге пайдаланылады. Бұл этапта пирамиданың элементтерін реттеу бағыты пирамиданың оң жағынан солға қарай, төменнен жоғарыға қарай қажет болған жағдайда алмастырылады. Екінші этап бірнеше фазадан тұрады. 1-фазада массивтің реттелмеген бөлігіндегі ағымдық максималды элемент пирамиданың төменгі оң бұрышында орналасқан элементпен алмастырылады. Сөйтіп, ағымдық максималды элемент реттелген массивте өзінің орнын табады. Осыдан кейін бұл максималды элемент те, оның орны да реттеуде қарастырылмайды. 2-этаптың 1-фазасының нәтижесінде пирамиданың құрылысы қайтадан құрылады.

HeapSort алгоритмінің тағы бір ерекшелігі алгоритмнің күрделілігі өзгермейтіндігінде. Жаман жағдайда н/е орташа алғанда да күрделілігі 0(n log2n) тең. Жоғарыдан бағасы орташаға жақын екенін дәлелдеуге болады. Бірақ дәл бағасын есептеу күрделі нәрсе. Екінші қызықты ерекшелігі бұл сұрыптауды жүргізуге қажетті қосымша жадтың минималдығында.

Стек. Алдын ала ескерсек, стек деректер құрылымы, кейбір жағдайлар магазин, динамикалық жадыны деп аталады. Осындай стек алдында тізбектеліп орналасқан шексіз «стек басы» және «түбі» ерекше ажыратылады. Процестің кезкелген уақыт мезетінде тек басына ғана оқу н/е жазу мүмкін болады. Осыған орай процесс барысында не өсіп не кеміп отырады. Еске салсақ, стек реттелген ұяшықтардан құрал5ан жады. Егер стек тізім ретінде ұйымдастырылса да, оны тізбектелген тізім ретінде көрсету жеңіл болып келеді.

Стек арқылы постфикстік түрдегі арифметикалық өрнекті есептеу алгоритмі қарапайым болып келеді.

Егер өрнектің кезекті символы операнд болса, онда оны стек басына келтіреміз.

Егер өрнектің келесі символы операция болса, онда стек басына келтіреміз. Операция операндылары осы уақыт мезетіне дейін стек операция белгісі орналасқан «этаждан» төмен «этаждарға» орналасады. Келесі қадамда операцияны орындап, орындалған операцияны және операндтарды стектен өшіреміз. Алынған нәтижені ең төменгі операндтар орналасқан «этажға» енгіземіз.

Өрнекте символдардың аяғына жеткенде есептеу тоқталады.

Quick Sort сұрыптауы. Quick Sort алгоритмінің күрделілігі орташалап алғанда 0(n log2n) жақын болады. Бастапқы берілген массивтің қандай да бір элементі таңдалып бекітіледі, әдетте массивтің ортаңғы н/е шеткі элемент/ін таңдайды ж/е тіректік элемент д.а. Қалған массив элемент/ін осы тіректік элем-тпен кезекпен салыстырады. Салыстыру нәт-де кезекті элемент тіректік элементтен үлкен болса, онда оны тіректік элементтің оң жағына орналастырады. Кері жағдайда сол жағына алмасады. Осы тіректік элем-т массивтің қалған барлық элемент/імен салыстырылғаннан кейін өзінің массивтегі түпкілікті орнын анықтайды. Сөйтіп, бұл элем-т жаңа массивтегі орнына жайғасып массивті 2ге бөледі.

9. Бинарлы іздеу ағашының элементтерін жою

Бинарлы іздеу ағашынан элементтерді жою үшін, берілген операциялардан кейін пайда болған объект(граф) бинарлы іздеу ағашы болатынын анықтау керек.

Мұнда 3 жағдай қарастырылады. Ең қарапайымынан бастайық. Егер жойылатын элемент, ағаштың түйіні ақырғы төбе болса, онда ол ешқандай қиындықсыз жойыла береді, н/е мұнда ағашқа ешқандай коррекция талап етілмейді, тек жойылатын түйіннің тікелей тегінің сәйкес өрісіне nill жазуынан басқа.

Егер жойылатын түйіннің (мысалы, №8 түйін 13 мәнімен) тек бір тікелей ұрпағы болса, онда ол ұрпақ жойылатын түйіннің орнына көшіріледі. Геометриялық тұрғыдан алғанда мұнда түбірі көшірілетін элемент болатын ішкі ағашта көшіріледі, бірақ ішкі ағаштардың ішінде сілтемелер ешбір өзгеріссіз қалады. Осы ерекшелік бұл операцияны стандарттық кодтаумен жүргізуге өте ыңғайлы болады.

Енді соңғы жағдай қалды, яғни жойылатын элементтін (3 түйін 7 мәнімен) екі тікелей ұрпағы бар болса, бұл жағдайда жойылатын элементтің оң жақ тікелей ұрпақтарының ұрпақтары арасында ең кіші мәнімен түйін – элемент табу керек және оны жойылатын элементтің орнына ауысуы керек.

Тура осылай жойылатын элементтің сол жақ тікелей ұрпақ/ң ұрпақ/ы арасында максималды мәнімен элемент табуға ж/е оны жойылатын элементтің орнына ауыстыруға болады.

Басқа сөзбен айтқанда, егер жойылатын V элементтің, өзі түбірі болатын екі ішкі ағаштары бар болса, онда оның ұрпағы V’ немесе алдыңғы «тегі» V’’ симметриялы ретті айналымда жойылатын элементтік орнын басу керек. Сонымен қатар V-түйінін V’- түйініне ауыстыру кезінде V’-түйінінің оң жақ тікелей ұрпағы V’-түйінінің орнын басады. Сәйкесінше, V’-түйінін V’’- түйініне ауыстырғанда да ұрпақ түйін орнын басады.

Бұл бөлімнің қорытындысына айта кететін бір жайт, бинарлы ағаштарға орындалатын басқа да арнайы операциялар бар. Мысалы: бұл ағаштың ішкі ағаш/ына AVL-ағаш/ның түйін/ін кірістіру кезінде бұрылу операциясы анықталады.

10. Толықтау бинарлы ағаш

Бинарлы ағаштың өсу нүктесі деп вакантты бағыт бойынша жаңа қабырға тұрғызуға болатын төбені айтады.

Егер бинарлы ағаштың барлық өсу нүкте/і соңғы деңгейде орналасса, онда ол толық д.а. Толық ағаштың ақырғы/ынан өзге әрбір төбесі 2 тікелей ұрпаққа ие болады, ал түбірден басталатын ж/е ақырғы төбеде аяқталатын барлық жол/дың ұзындығы бірдей болады ж/е бұл кезде мұндай жолдағы әрбір қабырға бір ғана рет өтіледі.

Толық бинарлы ағаштың k деңгійіндегі төбелердің саны n мынаған те болады

Толық ағаштағы элемент іздеу жылдам орындалады, ең көп дегенде log ₂ n слыстыру жасалады, бірақ бастапқы массивте «екінің дәрежесі минус бір» тең элементтер саны болады деген үміт үлкен емес. Осыған байланысты толықтау ағаш түсінігін қарастырайық, бұл типті ағашты теңестірілген дейді және оны элементтер саны еркін алынатын масссив үшін тұрғызуға қолдануға болады.

Бинарлы ағашты толықтау дейміз, егер оның барлық өсу нүктелері осы ағаштың тек соңғы және соңғының алдындағы деңгейлерде орналасса.

Кейде мұндай ағашты толықтау баланстандырылған деп те атайды.

Егер толықтау ағашта m деңгейінен жоғары төбелер жоқ десек, онда элементті іздеуге қажетті салыстырулардың максималды саны былай бағаланады:

log ₂ n < m≤ log ₂ n+1

яғни, толықтау ағаш үшін іздеу есебі оптималды- минималды уақытта шешіледі, яғни салыстыру саны минималды болады. Толықтау ағашш тұрғызу алгоритмі күрделі емес, бірақ бұл ағаштардың айтарлықтай кемшіліктері бар. Егер массив статикалы болса, яғни, элементтер саны да, элементтің өзі де өзгермесе, онда толықтау ағашты іздеуге қолдану негізді болып табылады. Мұндай ағашты ұйымдастыруға бір рет уақыт жұмсаса, ары қарай тек іздеу есебі ғана жүргізіледі және ол тиімді болады. егер массивтің элемент/і периодты түрде өзгерсе н/е қосылса н/е алынатын болса, онда бұл басқа бір мәселе.

Дәстүрлі түрде 6 элементтен тұратын массивті жне оның толықтау ағашын қарастырайық:

Бір ғана «2» элементін қосу ағашты қайта құруды керек етедіғ бұл кезде массивтің тек бір элементі ғана өз орнында қалады.

Бастапқы массив бойынша толықтау ағаш тұрғызу алгоритмі қарапайым болғанымен, бұл типті ағаштарды динамикалық массивтерге қолдану тиімділігі өте төмен болады. себебі жоғарыда көргеніміздей массив аз ғана өзгеріске түскен кезде ағашты айтарлықтай немесе толық қайта құру қажет болады.

11. Бинарлы ағашты симметриялы ретпен айналу

Бинарды ағаш массивті реттеу үшін қолданылады.Бинарлы ағаш ретінде реттелген массив сызықты емес,яғни реттеу өсу немесе кему бойынша жүргізілмейді.Бірақ ағаш төбелерін айналып өтуде сәйкес элементтер,мысалы өспелі ретпен,пайда болуы үшін айналу реті қандай болуы тиіс деген сұрақ пайда болады.Айналудың бұл типі симметриялы рет деп аталады және ол рекурсивті анықталады.

1. Сол жақ ішкі ағаштың төбелерін симметриялы ретпен өтіп белгілеу;

2. Түбірді белгілеу(ішкі ағаштың,ағаштың);

3. Оң жақ ішкі ағаштың төбелерін симметриялы ретпен өтіп белгілеу.

Айналудың қарастырылған әрбір типі бинарлы ағашты қолданумен байланысты есеп/ді шешуге қолайлы. Симметриялы ретпен ағашты айналудың қолайлығы жоғарыда көрсетіледі. Операндар, бинарлы операция таңбалары ж/е жақшалары бар арифметикалық өрнекті беру кезінде осы өрнекті арнайы түрде жақшасыз жазу мүмкіндігі бар. Ағаш түбірі (ағаштың ішкі) осы түбірдің сол және оң жақ тікелей ұрпақтарына қолданылатын оперциялардың операндасы болып табылады.

Ағашты симметриялы айналу дегеніміз алдымен ішкі ағаш түбірінің сол жақ тікелей ұрпағы өтіледі,содан соң операция белгісі бар түбір,ал одан кейін ғана осы түбірдің оң жақ тікелей ұрпағы өтіледі.Айналудың бұл нұсқасы өрнектің жазылуының инфиксті түрі деп аталады.

12. Бинарлы ағашты тура ретпен айналу

Соның бірі бинарлы ағашты тура ретпен айналып өту және ол рекурсивті анықталады:

4. түбірді белгілеу (ішкі ағаштың, ағаштың);

5. сол жақ ішкі ағаштың төбелерін тура ретпен өтіп белгілеу;

6. оң жақ ішкі ағаштың төбелерін тура ретпен өтіп белгілеу.

Ағаштың төбелерін тура ретпен айналу кезіндегі массив элементерінің реті мына түрде аламыз: 25,7,4,5,10,9,18,13,11,21,31.

Практикалық ұсыныс:бұл жағдада сағат тілі бағытына қарсы және түгелдей қамтитын контур бойындағы кездесетін әлі белгіленбеген төбелерді тізіп шығу керек.

Айналудың қарастырылған әрбір типі бинарлы ағашты қолданумен байланысты есептерді шешуге қолайлы. Операндалар, бинарлы операция таңбалары және жақшалары бар арифметикалық өрнекті беру кезінде арнайы түрде жақшасыз жазу мүмкіндігі бар. Ағаш түбірі (ішкі ағаштың) осы түбірдің сол және оң жақ тікелей ұрпақтарына қолданылатын операциялардың таңбасына ие болады және ол осы опера цияның операнды болып табылады.

13. Іздеу бинарлы ағашынан элементті жою

Сонымен іздеу бинарлы ағашынан эл.тті жою операциясын орындау үшін аз шығынмен орындалатын осы операция орындалғаннан кейінгі алдыңғы объект граф іздеу бинарлы ағашы болып қалуы к/к. Мұнда 3 жағдай болады. Қарапайымнан бастайық. Егер жойылатын эл.т ағаш түйіні ақырғы төбе болса, онда ол жай ғана жойылады ж/е мұнда ағашты ары қарай түзету к/к болмайды. Егер жойылатын түйіннің тек бір ғана тікелей ұрпағы бар болса, онда жойылған элемент орнына тікелей ұрпағы жылжытылады. Әрі бұл кезде осы жылжытылған элемент түбір болып саналатын ішкі ағашта геометриялық жылжиды, бұл кезде осы ішкі ағаш ішіндегі сілтеме/ өзгеріссіз қалады, сондықтан бұл операцияны стандартты кодта орындауда ыңғайлылық танытады.

Сонымен бинарлы іздеу бинарлы ағашынан элементтерді жою үшін берілген операциядан кейін пайда болған объект граф бинарлы іздеу ағашы болатынын анықтау керек. Мұнда 3 жағдай болады. Қарапайымнан бастайық. Егер жойылатын эл.т ағаш түйіні ақырғы төбе болса, онда ол еш қиындықсыз жойыла береді н/е мұнда ағашқа ешқандай коррекция талап етілмейді, тек жойылатын түйіннің тікелей тегінің сәйкес өрісіне nill жазылуынан басқа.

Егер жойылатын түйіннің тек бір тікелей ұрпағы болса, онда ол ұрпақ жойылатын түйіннің орнына көшіріледі. Геом.қ тұрғыдан алғанда мұнда түбірі көшірілетін элемент болатын ішкі ағаш та көшіріледі, бірақ ішкі ағаш/ң ішінде сілтеме/ ешбір өзгеріссіз қлады. Осы ерекшелік бұл операцияны стандарттық кодтаумен жүргізуде өте ыңғайлы болады.

Енді соңғы жағдай қалды, яғни жойылатын элементтің екі тікелей ұрпағы бар. Бұл жағдайда жойылатын эл.ттің оң жақ тікелей ұрпақ/ң ұрпақ/ы арасында ең кіші мәнімен түйін эл.т табу к/к ж/е оны жойылатын эл.ттің орнына ауыстыру к/к.

Тура осылай жойылатын элементтің сол жақ тікелей ұрпақ/ң ұрпақ/ы арасында максималды мәнімен элемент табуға ж/е оны жойылатын эл.ттің орнына ауыстыруға болады.

Басқа сөзбен айтқанда егер жойылатын V элементтің өзі түбірі болатын екі ағаштары бар болса, онда оның ұрпағы V' немесе алдыңғы тегі V’’ симметриялы ретті айналымда жойылатын элементтің орнын басу керек. Сонымен қатар V түйінін V’ түйініне ауыстыру кезінде V’ түйінінің оң жақ тікелей ұрпағы V’ түйінінің орнын басады. Сәйкесінше V’ түйінін V’’ түйініне ауыстырғанда да ұрпақ түйін орнын басады.

14. O (n²) күрделілігімен сұрыптау

Қарастыруды өте жақсы белгілі «көпіршіктік сұрыптау» алгоритмінен бастайық. Алгоритмнің негізгі идеясы массивтің көрші элементтерін өзара қостап салыстырып қажет жағдайда орындарын ауыстыруда жатыр. Айқын болу үшін массивтің сол жағынан, яғни x₁ элементінен бастайық және солдан оңға қарай жылжиық. Жылжу барысында x_i,x_i+1 жұптарын екі екіден салыстырып отырып, бірінші қадамның соңында ең үлкен(ең кіші) элемент ең оң жақ шеткі орын алады. Процессті қайталаймыз, келесі қадамда да массивтің ең сол жақ шетінен бастаймыз, ал ең оң жақтағы, яғни n-ші орында тұрған элемент тұрақты орын алып және екінші қадамда процеске қатыспайтынын ескереміз.Әр қадамда бір элементтен шегеріліп отырады, яғни массивтің сұрыпталған оң жақ шеті оңнан солға қарай жылжып отырады. Процесс массивтің соңғы элементі(ең сол жақ шеткі) сұрыпталған массивте өзінің орнына тұрғанша қайталана береді.

Жоғарыда келтірілген «көпіршіктік сұрыптау» алгоритмінің негізінде массивті реттеуге қажетті салыстыру/ санының бағасын беруге болады. «Көпіршіктік сұрыптау» алгоритмі үшін салыстыру саны тең екенін есептеу қиын емес. Осыған байланысты «көпіршіктік сұрыптау» алгоритмі күделілігі O(n²) болатын алгоритмдер класына жатады.

Алгоритмнің программалық нұсқасын келтірейік.

Procedure bubblesort (a, n);

....

Begin

for m:=n down to 2 do

begin r:=a[1];