Екілік тармаќтармен ж‰ргізілетін амалдар

1. Тармаќты толыѓымен ќарап µту алгоритмі

Тармаќтыњ тµбелерін с±рыптау алгоритмі – тармаќты толыѓымен ќарап µту алгоритмі деп аталады. М±ндай алгоритмдер т‰йінде ‰ш т‰рлі єрекет жасайды: т‰йінге кіреді, сол жаќ б±таќпен рекурсивті т‰рде тµмендейді, рекурсивті т‰рде оњ жаќ б±таќпен тµмендейді.

Тармаќты ќарап шыѓудыњ 3 т‰рлі негізгі єдісі бар:

1. Тура єдіс;

2. Симметриялы єдіс;

3. Кері єдіс;

Тармаќты толыѓымен ќарап шыѓу алгоритмі олардыњ түйініндегі µздерініњ єрекеттерімен байланысты реттерімен ажыратылады.

1. Тура єдіс (жоѓарыдан тµмен ќарай):

- т‰йінге кіру;

- сол жаќ б±таќтан µту;

- оњ жаќ б±таќтан µту;

(1) 7

5 8

0 6 9

2

Екілік тармаќ берілген. Б±л тармаќтаѓы т‰йінге кіру реті келесідей болады:

7 5 0 2 6 8 9

2. Симметриялыќ єдіс (солдан оњѓа ќарай):

- сол жаќ б±таќтан ж‰ріп µту;

- т‰йінге кіру;

- оњ жаќ б±таќтан ж‰ріп µту;

Берілген (1) тармаќ ‰шін симметриялыќ ќарап шыѓу келесі т‰рде болады:

0 2 5 6 7 8 9

Екілік тармаќты симметриялыќ ќарап шыѓу єдісі элементтерді µсу ретімен орналастырды. Осылайша, с±рыптаудыњ таѓы бір алгоритмін ±сынуѓа болады:

А) массив негізінде с±рыптау;

В) тармаќты симметриялыќ ќарап шыѓу єдісі ж‰зеге асады;

М±ндаѓы ењ жаќсы жаѓдайда алгоритмніњ тиімділігі O(n log₂n) болады.

3. Тармаќты кері ќарай ќарап шыѓу єдісі (тµменнен жоѓарыѓа ќарай):

- сол жаќ тармаќтан ж‰ріп µту;

- оњ жаќ тармаќтан ж‰ріп µту;

- т‰йінге кіру;

Осы єдіс ‰шін тармаќты ж‰ріп µтудіњ жолы:

2 0 6 5 9 8 7

¤рнектіњ екілік тармаќтарын ќарап µтуде жоѓарыда берілген ‰ш єдіспен мынаны аламыз:

1. Ќарап шыѓудыњ тура єдісі. ¤рнектерді жазудыњ префиксті форматына (жоѓарыдан тµменге ќарай) сєйкес келеді.

2. Ќарап шыѓудыњ симметриялыќ єдісі µрнектерді жазудыњ инфиксті форматина сєйкес келеді.

3. ќарап шыѓудыњ кері єдісі µрнектерді жазудыњ постфиксті форматына сєйкес келеді.

2. Екілік іздеу тармаѓынан элементті алып тастау.

Тармаќтан элементті алып тастау алгоритмі тармаќтаѓы осы элементтіњ орналасќан орнына тєуелді болады жєне келесі тµрт жаѓдайды ќамтиды:

1. Мєні х-ке тењ болатын элемент жоќ.

2. Мєні х-ке тењ болатын элемент терминальды т‰йін болып табылады.

3. Мєні х-ке тењ болатын элемент бір ѓана ±рпаќты болады.

4. Мєні х-ке тењ болатын элемент екі ±рпаќты болады.

Бір ѓана ±рпаѓы болатын элементті алып тастауда ешќандай к‰рделілік жоќ. М±ндай єрекеттер сызыќтыќ тізімдегі элементті алып тастауѓа ±ќсас болады.

Егер элемент екі ±рпаќты болса, онда екі баѓытта бір ѓана сілтемемен кµрсетуге келмейді. Б±л жаѓдайда µшірілетін элементті ауыстыруѓа тура келеді. Ауыстыратын элемент ‰шін оныњ сол жаќтаѓы ењ оњ жаќќы элемент, ал оњ жаќтаѓы ењ сол жаќќы элемент тањдап алынады (6 жєне 8 µшірілетін элементке мєндері жаѓынан жаќын элементтер).

Элементі µшіру алгоритмі. Алгоритм жоѓалѓанда ќарастырылатын 4 жаѓдайды ќамтиды:

1-жаѓдай: µшірілетін т‰йін табылѓан жоќ. Яѓни µшірук алгоритмі µз ж±мысын тоќтатады.

2-жаѓдай: т‰йінніњ ±рпаќтары жоќ. Яѓни жапыраќ болып табылады. Б±л жаѓдайда ата-аналыќ т‰йінді оныњ б±таѓы бос болатындай етіп жањарту керек.

3-жаѓдай:

1. Т‰йінніњ сол жаќ ±рпаѓы бар, оњ жаќ ±рпаѓы жоќ. Яѓни сол жаќ б±таќты оныњ ата-анасына жалѓастыру керек.

2. Т‰йінніњ оњ жаќ ±рпаѓы бар, сол жаќ ±рпаѓы жоќ. Яѓни т‰йінніњ оњ жаќ б±таѓын оныњ ата-анасына жалѓастыру керек.

4-жаѓдай: екі ±рпаѓы бар т‰йінді алып тастау немесе µшіру. М±нда µшірілетін т‰йінді ауыстыру ќажет. Ауыстыру ‰шін сол жаќ б±таѓы ењ оњ жаќтаѓы т‰йінді тањдаймыз.

Келесілерді аныќтаймыз:

D – µшірілетін т‰йін

P – µшірілетін элементтіњ ата-анасы

R – ауыстыратын т‰йін

PR – R т‰йінніњ ата-анасы.

1. D т‰йінініњ сол жаќ б±таѓына кµшеміз. Себебі, R ауыстыратын т‰йін µшірілетін D т‰йінінен кіші болады.

2. R ауыстыратын т‰йін D т‰йінініњ сол жаќ б±таѓындаѓы максимальды т‰йін болып табылады. Оњ жаќ б±таќ бойынша тµмен жылжып, P ауыстыратын т‰йінді іздейміз. Жылжу барысында RR ата-аналыќ т‰йінді баќылап отырамыз. М±нда екі м‰мкін жаѓдай бар:

1. Оњ жаќ б±таќ бос. R ауыстытылатын т‰йін µшірілетін т‰йінніњ сол жаќ баласы болып табылады. Ал PR сєйкесінше D т‰йініне кµрсетіледі. М±ндай жаѓдайда келесі єрекеттерді орындаймыз:

А) D т‰йінініњ оњ жаќ б±таѓын R т‰йініне ќосамыз.

Б) ¤шірілетін т‰йінніњ P ата-анасын R т‰йініне ќосамыз.

P P

D R

R PR=D

Оњ жаќ б±таќ оњ жаќ б±таќ

2. Оњ жаќ б±таќ бос емес. М±ндай жаѓдайда ауыстыратын т‰йін жапыраќтыќ т‰йін болады немесе тек ќана сол жаќ б±таѓы бар т‰йін болады. Келесі єрекеттерді орындаймыз:

А) R т‰йінін тармаќтан бµліп аламыз.

Б) R т‰йінініњ ±рпаќтарын оныњ ата-аналыќ РR т‰йініне жалѓаймыз. (R-діњ сол жаќ б±таѓы РR-ѓа оњ жаќ б±таќ болып жалѓанады).

С) ¤шірілетін D т‰йіні R т‰йінімен ауыстырылады. Яѓни D т‰йінініњ ±рпаќтары R т‰йінініњ ±рпаќтары болып жалѓанады, ал R т‰йіні ата-аналыќ P т‰йініне жалѓанады.

Дәріс 13.

Массивтермен берілген бинарлыќ тармаќтар

Мақсаты: Массивтермен берілетін бинарлық тармақтар ұғымын енгізу. Турнирлік сұрыптау, пирамидалар түсініктерін енгізу.

Массивтермен берілген бинарлыќ тармаќтар екіге бµлінеді:

1. Турнирлік с±рыптау.

2. Пирамидалар.

Егер бинарлыќ мєліметтер элементтерде саќталса, онда мєліметтерге тура кіруді ж‰зеге асыруѓа болады. Массивтіњ 0-элементі б±л тармаќтыњ тамыры немесе т‰бірі. n элемент массиві ‰шін ai т‰йінніњ ±рпаќтарын келесі формуламен есептеуге болады. Сол жаќтаѓы индекс - 2i+1, ал оњ жаќтаѓы индекс - 2i+2-ге тењ, ал ата-анасыныњ индексін - (i-1)/2 формуласымен аныќтаймыз. Тармаќталѓан массивті пайдалану беруді аяќтаѓалѓан бинарлыќ тармаќ ‰шін ќолдану ќолайлы. Біраќ тыѓыздыѓы аз болатын тармаќты саќтаѓанда массивте пайдаланылмайтын элементтер болады да массивпен ж±мыс істеуде бірќатар ќиындыќтар туѓызуы м‰мкін. Мысалы:

A[]=(5,1,3,9,6,2,4,7,0,8)