«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері»

else q:=s;

end;
Схема түрінде іздеу процесін келесі схема түрінде бейнелеуге болады:

+-------------------------0-------------------------------+

¦ +---------------1---------------¦

¦ +-------2--------+ ¦

¦ ¦ +----3---¦ ¦

¦ ¦ +--4-+ ¦ ¦

¦ ¦ +-5+ ¦ ¦ ¦

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

1. 
   Ортасынан бөлу әдісімен элементті іздеу идеясы неменеге негізделген?
   
2. 
   Ортасынан бөлу әдісімен массив элементін іздеу алгоритмін жасаудағы әрекеттер тізбегін сипатта.
   

1. 
   10 бүтін сан массивы беріледі. Оны сұрыптап, ондағы бақылау санын тап. Бақылау санына дейінгі барлық элементтерді қарама-қарсыға өзгерт.
   
2. 
   20 символдан тұратын массив берілген. Сұрыптап, ондағы бақылау символын тап. Экранға бақылау символынан бастағандағы элементтерді шығар.
   

Тақырыбы: Жылдам іздеу

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

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

2 8 5 8

9 9

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

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

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

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

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

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

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

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

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

Тармақты қарап шығудың 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. 
   қарап шығудың кері әдісі өрнектерді жазудың постфиксті форматына сәйкес келеді.
   

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

5. 
   Мәні х-ке тең болатын элемент жоқ.
   
6. 
   Мәні х-ке тең болатын элемент терминальды түйін болып табылады.
   
7. 
   Мәні х-ке тең болатын элемент бір ғана ұрпақты болады.
   
8. 
   Мәні х-ке тең болатын элемент екі ұрпақты болады.
   

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

Егер элемент екі ұрпақты болса, онда екі бағытта бір ғана сілтемемен көрсетуге келмейді. Бұл жағдайда өшірілетін элементті ауыстыруға тура келеді. Ауыстыратын элемент үшін оның сол жақтағы ең оң жаққы элемент, ал оң жақтағы ең сол жаққы элемент таңдап алынады (6 және 8 өшірілетін элементке мәндері жағынан жақын элементтер).

Элементі өшіру алгоритмі. Алгоритм жоғалғанда қарастырылатын 4 жағдайды қамтиды:

1. Түйіннің сол жақ ұрпағы бар, оң жақ ұрпағы жоқ. Яғни сол жақ бұтақты оның ата-анасына жалғастыру керек.

2. Түйіннің оң жақ ұрпағы бар, сол жақ ұрпағы жоқ. Яғни түйіннің оң жақ бұтағын оның ата-анасына жалғастыру керек.

4-жағдай: екі ұрпағы бар түйінді алып тастау немесе өшіру. Мұнда өшірілетін түйінді ауыстыру қажет. Ауыстыру үшін сол жақ бұтағы ең оң жақтағы түйінді таңдаймыз.
Келесілерді анықтаймыз:

D – өшірілетін түйін

P – өшірілетін элементтің ата-анасы

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

PR – R түйіннің ата-анасы.

3. 
   D түйінінің сол жақ бұтағына көшеміз. Себебі, R ауыстыратын түйін өшірілетін D түйінінен кіші болады.
   
4. 
   R ауыстыратын түйін D түйінінің сол жақ бұтағындағы максимальды түйін болып табылады. Оң жақ бұтақ бойынша төмен жылжып, P ауыстыратын түйінді іздейміз. Жылжу барысында RR ата-аналық түйінді бақылап отырамыз. Мұнда екі мүмкін жағдай бар:
   

3. 
   Оң жақ бұтақ бос. R ауыстытылатын түйін өшірілетін түйіннің сол жақ баласы болып табылады. Ал PR сәйкесінше D түйініне көрсетіледі. Мұндай жағдайда келесі әрекеттерді орындаймыз:
   

Б) ¤шірілетін түйіннің P ата-анасын R түйініне қосамыз.

P P

R PR=D

4. 
   Оң жақ бұтақ бос емес. Мұндай жағдайда ауыстыратын түйін жапырақтық түйін болады немесе тек қана сол жақ бұтағы бар түйін болады. Келесі әрекеттерді орындаймыз:
   

Б) R түйінінің ұрпақтарын оның ата-аналық РR түйініне жалғаймыз. (R-дің сол жақ бұтағы РR-ға оң жақ бұтақ болып жалғанады).