Екілік тармақтар типіндегі құрылыстар матрицалық өрнектерді беруде көп қолданылады. Мысалға, 2+3 өрнегін мына түрде жазуға болады (екілік тармақ ретінде)

Екілік тармақтар типіндегі құрылыстар матрицалық өрнектерді беруде көп қолданылады. Мысалға, 2+3 өрнегін мына түрде жазуға болады (екілік тармақ ретінде):

2 3

6 4

Өрнектің екілік тармақтары келесі қасиеттерге ие болады:

1. 
   Әрбір жапырақтық төбе бір ғана операндқа ие болады (операнд - сандар), ал жапырақ емс төбе – амалға ие болады.
   
2. 
   Әрбір бұтақ қандай да бір туындыны құрайды.
   
3. 
   Сол жақ немесе оң жақ бұтақтың түбіріне сәйкес амалды орындамас бұрын есептеліп шыққан болуы керек.
   

Екілік іздеу тармақтары программалауда кең таралған. Екілік іздеу тармақтарының әрбір төбесінің мәні:

1. 
   Оның сол жағындағы бұтақ төбесінің кез келген мәнінен үлкен немесе тең.
   
2. 
   Оның оң жақ бұтағының төбесінің кез келгенінің мәнінен кіші.
   

2 8 5 8

9 9

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

Сызықтық құрылғылар үшін тізбектеліп іздеу алгоритмінің күрделілігі – О(n) –ға тең. Мұндағы n-құрылым элементтер саны. Ал аяқталатын бинарлық тармақ үшін күрделілігі – О(log₂n)-ға тең.

Мысалға: 10000 элементтен тұратын тізімде тізбектеп іздеуде салыстырудың максимальды саны 10000-ға тең болады. Ал аяқталған тармақта іздеу 14 салыстырудан аспас еді.

Екілік іздеу тармағына элементті осу алгоритмі (тармақты қарау үнемі түбірден басталады):

1. 
   тармаққа қосылатын мән ағымдағы түйін мәніне салыстырылады.
   
2. 
   Егер тармаққа қосылтын мән ағымдағы түйін мәнінен кіші болса, онда келесілер тексеріледі:
   

б) әйтпесе, (егер ұрпақ болса) тармақтың сол жақ бұтағы арқылы бір деңгейге төмендетеміз.

3. 
   Егер тармаққа қосылатын мән ағымдағы түйін мәнінен үлкен немесе тең болса, келесілер тексеріледі:
   

б) әйтпесе, оң жақ бұтақ бойымен бір деңгейге төмендетеміз.

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

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

1. 
   Тура єдіс;
   
2. 
   Симметриялы єдіс;
   
3. 
   Кері єдіс;
   

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

(1) 7

5 8

0 6 9

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

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. Т‰йінніњ оњ жаќ ±рпаѓы бар, сол жаќ ±рпаѓы жоќ. Яѓни т‰йінніњ оњ жаќ б±таѓын оныњ ата-анасына жалѓастыру керек.

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

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

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

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

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

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

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

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

P P

R PR=D

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

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

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

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

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

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

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

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

Турнирлыќ m, n элементтен m массивті с±рыптауѓа ќолданылуы м‰мкін. Турнирлыќ с±рыптауды келесі мысалда ќарастырайыќ:

A[8]=(35, 25, 50, 20, 15, 45, 10, 40)

Осы массивті µсу ретімен с±рыптау ќажет.

1. Массив элементтері бинарлыќ тармаќ к дењгейінде болады. М±ндаѓы: 2^k>=n n – массив элементтер саны. Б±л жаѓдайда 2³=8, яѓни k=3 болады.

2. Ата-аналыќ т‰йінге ж±птарѓа элементтердіњ кішісі орналасады, ењ соњѓы салыстыру нєтижесінде массивтіњ ењ кіші элементі 0-дењгейіне (тамырына) т‰седі.

3.

10

10

15

10

15

20

25

35

40

45

50

Осы процесс барлыќ жапыраќтары алынып тасталѓанша ж‰ргізіліп ж‰ре береді. Ењ соњѓы т‰йін (ењ ‰лкен элемент) барлыѓын ‰нсіз келісім бойынша шыѓады.