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

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

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

1. Есептеліну және шешімі болу дегеніміз не?

А алфавитіндегі n сөзден тұратын реттелген жинақ А-ның үстіндегі n-орынды жинақ деп аталады. Оны (A ^*) ⁿ деп белгілейміз. Кез келген (A ^*) ⁿ жиының R жиыншасы n-орынды сөздің қатынас деп аталады.

f: (A ^*) ⁿ → A ^* кез келген, мүмкін жеке көрсетілуі n-орынды сөздің функциясы деп аталады. f функциясының анықталу облысы Def (f) арқылы белгіленеді.

Т бағдарламасының жұмысының Х псевдосөзіндегі нәтижесі T (x) псевдосөзі деп аталады, ол бағдалама тоқтаған кезде лентада пайда болады; егер бағдарлама ақырсыз жұмыс жасаса, нәтиже анықталмаған.

Кез келген Х псевдосөзімен жұмыс кезінде бастауын n-ші Х псевдосөзіненің сол жағында орналасқан пробелден солға қарай жылжытпайтын бағдарламаны n-бағдарлама деп атаймыз.

Егер X* u_n * u_{n –1} * … *u ₁ * ^↓ , где (u ₁, u ₂, …, u_n) ∈ R. түрдегі барлық псевдосөздерде анық тоқтайтын Т n-программасы бар болса, R cөздік n-орынды қатынасы жартылай шешімді деп аталады.

Егер R және R(мұндағы R және R ретінде (A ^*) n \ R түсініледі) жартылай шешімді болса, R сөздік n-орынды қатынасы шешімді деп аталады.

Егер T (_* u _1* u _2*..._* u_{n *} ^↓ ) = _* u _1* u _2*..._* u _n* v _* ^↓ ,

мұндағы u ₁, u ₂,..., u_n ∈ Def (f) және v = f (u ₁, u ₂,..., u_n) болатын Т бағдарламасы бар болса, f: (A*) ⁿ → A* сөздік n-орынды функциясы Тьюринг бойынша есептелінеді деп аталады, кері жағдайда нәтиже анықталмаған.

Тьюринг бойынша есептелетін функцияларды жартылай есептеленуші, ал рұқсат етілген анықталу обылсымен жартылай есептелінушілерді – есептелінуші деп атауға болушы еді, алайда бұл қалыптасқан дәстүрге қарсы.