Екілік тармақтың құрылымы.

Екілік тармақты компьютер жадысына берудің екі түрлі жолы бар.

1. Кәдімгі массивті пайдалана отырып тізбектеп беру

2. Динамикалық құрылым ретінде беру.

Массивті пайдалана отырып тізбектеп беруде екілік тармақ бір өлшемдік массивке қапталады. Мұндай беруде тек бір ғана TREE сызықты массиві қолданылады. Тармақтың түбірі массивтің бірінші элементі TREE[0] –де орналасады. Келесі екі балалық төбелері көршілес элементтерде орналасады. Т.с.с.

Егер n түйіні массивтің TREE[k] элементін алатын болса, онда оның сол жақтағы балалық түйіні TREE[2K+1], ал оң жақтағы блалық түйіні - TREE[2K+2].

Кемшіліктері:

1. Тармақтың өлшемі массив өлшемімен шектелетін болады.

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

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

Көрсеткіштер өрістері – сол жақ көсеткіш және оң жақ көрсеткіш деп аталады. Себебі, олар сәйкес сол және оң тармаққа көрсетеді.

Жапырақтық түйін – сол және оң жақ түйін көрсетуде Null болады.

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

1. түбір ретінде бір түйінді алу.

2. nl=n/2 түйіні бар сол жақ бұтақ салу (осы алгоритм көмегімен)

3. nr=n-nl-1 оң жақ бұтақ салу (алгоритм көмегімен)

Мысалы, 1,2,3,4,5,6,7,8,9,0 сандар тізбегі үшін идеалды балансталған тармақ келесі түрде болады:

Өрнектердің екілік тармақтары

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

2 3

7 +(6*4) өрнегін келесі түрде:

7 *

6 4

Тармақтардың мұндай типтері өрнектер тармақтары деп аталады. Мұндай тармақтардың әрқайсысы қөандай да бір өрнектерді сипаттайды. Тек қана екілік амалдарды сипаттайтын екілік тармақтар өрнектердің екілік тармақтары деп аталады. ( амалдар дегеніміз – бұл тек қана операндасы бар амалдар).

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

1. Әрбір жапырақтық төбе бір ғана операндқа ие болады (операнд - сандар), ал жапырақ емс төбе – амалға ие болады.

2. Әрбір бұтақ қандай да бір туындыны құрайды.

3. Сол жақ немесе оң жақ бұтақтың түбіріне сәйкес амалды орындамас бұрын есептеліп шыққан болуы керек.

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

Дәріс 12.

Екілік іздеу тармақтары

Мақсаты: Екілік іздеу тармақтары ұғымы. Екілік тармаќтармен жүргізілетін амалдар. Байланған сызықтық тізімдер түсініктерін енгізу.

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

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

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

5 7

2 8 5 8

0 7 0 6

9 9

6 2

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

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

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

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

1. тармаққа қосылатын мән ағымдағы түйін мәніне салыстырылады.

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

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

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

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

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

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