Қазақстан республикасының бiлiм және ғылым министрлiгi

Ал егер a[i]=x тек қана i=n+1 болса, онда массивте ізделінді элемент жоқ. Көп жағдайда іздеу реттелген массивте жүргізілген тиімді. Бұл жағдайларда тиімді әдістердің бірі – қақ бөлу бойынша іздеу.

Қақ бөліп іздеу әдісінде ізделінді эталонды салыстыру массивтің ортасында орналасқан элементпен жүргізіледі, салыстыру нәтижесіне байланысты (артық немесе кем) ары қарай іздеу массивтің не сол жақ жартысында, не оң жақ жартысында жүргізіледі.

Тоғыстыру арқылы сүрыптау (Сортировка слиянием; merge sorting) — бірінші кезеңде жазбалар тобы жедел жадта сүрыпталатын өрі бірнеше таспаға жазылатын, ал екінші кезенде реттелген топтар бірнеше таспадан бір таспаға жинақталатын сыртқы сүрыптау.

Ағаштармен байланысты ұғымдар кең таралған және интуитивті түсінікті. Ағаштың бірнеше мүмкін анықтамалары бар.

Мысалы, графтар көзқарасы жағынан, ағаш деп жиі жағдайда бағытталмаған ұшы белгіленген, циклдары болмайтын, графты атайды. Бізді тек бағытталған ағаштар қызықтыратын болады, бағдарламаушылар көзқарастары жағынан. Сондықтан біз келесі рекурсивті анықтамамен қолданамыз: Т базалық типті R ағашы – бұл немесе (a) бос ағаш (бір де бір ұшы жоқ ), немесе (b) T типті кейбір ұш (ағаштың түбі) соңғы (мүмкін, нөльдік) Т базалық ағаштармен байланысқан санмен (Бұл ағаштар R ағашының ішіндегі ағаштар деп аталады). Бұл анықтамадан келесіні түсінуге болады, біржақты бағытталған тізім ағаш болып аталады. (Сур. 1).

Сурет. 2. Графтың бір түрі

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


Сурет. 3. Графтың екінші түрі

Ағаштардың ішіндегі ағаштардың байланыстарын бұтаұтар деп атаймыз, ал әр ағаштың түбін ұшы деп атаймыз. Реттелген деп бұтақтары реттелген ағаштарды атаймыз. Мысалыр, 4 суретте екі реттелген ағаштар айырылады.

Ұштар саны немесе бұтақтар саны x ұшына жолы деп аталады. Биіктігі немесе тереңдігі деп ұштың максималды ұзындығын атаймыз.

1. 
   «Іріктеу және іздеу әдістері» пәнінің мақсаттары.
   
2. 
   Ағаштардың мүмкін болатын анықтамаларын атаңыз.
   
3. 
   Граф деген не?
   
4. 
   Ұшқа апаратын жолдың ұзындығы деген не?