Зертханалық жұмыс №6

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

Жалпы мәлімет

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

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

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

5 7

2 8 5 8

0 7 0 6

9 9

6 2

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

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

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

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

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

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

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

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

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

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

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

Екілік тармақтармен жүргізілетін амалдар

Тармақты толығымен қарап өту алгоритмі

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

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

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

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

5. Мәні х-ке тең болатын элемент жоқ.

6. Мәні х-ке тең болатын элемент терминальды түйін болып табылады.

7. Мәні х-ке тең болатын элемент бір ғана ұрпақты болады.

8. Мәні х-ке тең болатын элемент екі ұрпақты болады.

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

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

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

1-жағдай: өшірілетін түйін табылған жоқ. Яғни өшірук алгоритмі өз жұмысын тоқтатады.

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

3-жағдай:

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

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

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

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

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

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

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

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

3. D түйінінің сол жақ бұтағына көшеміз. Себебі, R ауыстыратын түйін өшірілетін D түйінінен кіші болады.

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

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

А) D түйінінің оң жақ бұтағын R түйініне қосамыз.

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

P P

D R

R PR=D

Оң жақ бұтақ оң жақ бұтақ

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

А) R түйінін тармақтан бөліп аламыз.

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

С) ¤шірілетін D түйіні R түйінімен ауыстырылады. Яғни D түйінінің ұрпақтары R түйінінің ұрпақтары болып жалғанады, ал R түйіні ата-аналық P түйініне жалғанады.