Главная Обратная связь

Дисциплины:






Ызыл-қара ағаштар.



h биіктіктегі екі жақтыіздестіру ағашының негізгі операциясын O (h) іс-әрекеттері арқылы жүзеге асыруға болады.Егер ағаштардың биіктігі кішкене болса, нәтижелі болады. Операция нәтижесін арттыру үшін ағаштың биіктігі Ο (log n) өлшемінде керек болса,

ағаштарды салудың тиімді әдістері қолданылады. Бұндай әдістер ағаштарды тепе-теңдікте ұстау деп аталады. Тепе-теңдік сапасының әр түрлі өлшемдері қолданылады.

Ο (log n) өлшемдегі биіктікке қол жету үшін кепіл баға беретін іздеу ағаштарының теңестірілген бір түрі қызыл-қара ағаштар деп аталады.

Осындай теңестірукезінде жиі кездесетіні АВЛ- теңестіру, онда әр бөліктегі сол жақ ағаш түбінің биіктігі оң жағынан бірлікке ғана ерекшеленеді.

Қызыл-қара ағаштар- іздеудің кеңейтілген екі жақты ағашы,биіктігі қара және қызыл болып бөлінеді:

Әр бөлігі не қара , не қызыл.

Әр парағы (nil-бөлігі)-қара.

Егер бөлігі қызыл болса, онда екі баласы қара.

1. Бас-басы түйіншек не қызыл, не қара.

2. Бас-басы парақ(nil- түйіншек) - қара.

3. Түйіншек қызыл, оның екі баласы қара.

4. Төмен түптен жапырақтарға, баратын барлық жолдар қара түйіншектің бірдей санын асырайды.

Түбірінен жапырақтарына дейінгі жолдар бірыңғай мөлшерде қара бөліктерді құрайды. 1-4 дейінгі қасиеттер RB-қасиеттері деп аталады. Қызыл-қара ағашының бөліктерін былай белгілейміз:

Node = (color, key, left, right, parent).

 

 

 
 

 

Айналу– бұл RB-қасиеттері бүлінген жағдайда қызыл-қара ағаштарды қалпына келтіру үшін жасалатын әрекеттер.Оларды Insert және Delete операцияларын жүзеге асыруда орындаймыз.Айналу кезінде бірнеше көрсеткіш ауысуы мүмкін, бірақ тәртібі сақталатын жүйелі операция болып табылады.1-суретте біржақты екі айналу түрі көрсетілген:сол жаққа және оң жаққа

Негізгі алгоритмдік проблемаларға нелер жатады?



Негізгі алгоритмдік проблемалар:

1. Өзіне өзін қолдану про­бле­масы.

2. Тоқтату про­бле­масы

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

1936 жылы Алан Тьюринг кез келген мүмкін болатын кірістік деректер үшін тоқтап қалудың проблемасын шешудің жалпы алгоритмі болмайтындығын дәлелдеді. Тоқтап қалу проблемасы Тьюринг машинасында шешілмейді.

Шешімі болмауды дәлелдеудің 2 әдісі бар: тікелей әдіс және жанама әдіс.

 

3. Жалпырекурсивтілік про­бле­масы

4. [Род­жерс,1972,с.54] кез келген натурал x мәні үшін мына сұраққа жауап беретін алгоритм бар ма: " x номерлі jx фун­кция тұрақты функция ма?".

5. [Род­жерс,1972,с.54] кез келген натурал (x,y) жұбы үшін мына сұраққа жауап беретін алгоритм бар ма: " y мәні jx фун­кциясының мәндер жиынына жата ма ?".

6. [Род­жерс,1972,с.54] кез келген (x,y,z) үшін мына сұраққа жауап беретін алгоритм бар ма: "jx(y)=z теңдігі орындала ма?".

7. [Род­жерс,1972,с.54] кез келген (x,y) жұбы үшін мына сұраққа жауап беретін алгоритм бар ма: "jx=jy теңдігі орындала ма?".?".

8. [Род­жерс,1972,с.54] кез келген x мәні үшін мына сұраққа жауап беретін алгоритм бар ма: " j фун­кциясының мәндер жиыны шексіз бе?".

9. [Род­жерс,1972,с.54] нақты y0 және кез келген x үшін мына сұраққа жауап беретін алгоритм бар ма:: " y0 jx фун­кциясының мәндер жиынына жата ма?".

10. [Род­жерс,1972,с.54] нақты x0 және кез келген y үшін мына сұраққа жауап беретін алгоритм бар ма: «y0 jx0 фун­кциясының мәндер жиынына жата ма».

[Род­жерс,1972,с.54]). Теорема: Ал­го­рит­мдік про­бле­малар 1-10 ал­го­рит­мдік шешімі жоқ. не­раз­ре­ши­мы. 9-про­бле­ма кез келгене y0 үшін шешімі жоқ, ал 10-про­бле­ма x0.-ті таңдауға байланысты шешімі болуы да болмайы да мүмкін





sdamzavas.net - 2017 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...