Исследовать ребро (x, y)

Begin

Begin

Begin

Begin

if (x = nil) or (k = key [x]) then Return x;

if (k < key [x]) then Return Search (left[x], k) else

Return Search (right[x], k)

end.

Бiз iздестiрудiң процессiнде түбiрден қозғаламыз, кілтті k кiлтпен салыстыра, x ағымдағы шың сақталған қозғаймыз. Егер ол тең болса, iздестiру аяқталады. Егер k < key[x], онда iздестiру x сол ағаш астындада созылады. Егер k > key[x], онда iздестiру оң ағаш астында созылады. Iздестiру жолының ұзындығы ағаштың биiктiгiн асып түспейдi, сондықтан iздестiрудiң уақыты (h - ағаштың биiктiгi) (h) O бар.

Процедура iздестiру итератив нобайы

Procedure IterativeSearch (x, k);

While (x ≠ nil) and (k ≠ key [x]) do

If k < key [x] then x:= left[x] else x:= right[x];

Return (x)

end.

Минимум және максимум. Iздестiру ағашында ең төменгi кiлтпен элемент табуға болады, көрсеткіш left түбiрден өте шыға nil-ге жеткенімізге дейін табуға болады. (x) Minimum(x) процедура түбiрi бар ағаш астынданың табылған элементiне көрсеткiштi қайтарады.

Procedure Minimum(x);

begin While left [x] ≠ nil do x:= left[x]; Return (x) end.

Алгоритм Maximum симметричен:

Procedure Maximum(x);

begin While (right [x] ≠ nil) do x:= right[x]; Return (x) end.

Екі алгоритм O(h) уақытты (ағаш бойымен тек қана төмен қозғалғандықтан) ағаштың биiктiгi талап етедi.

Келесi және алдыңғы элементтер. Егер х кейбір ағаштың көрсеткіші болса, сол Successor(x) рәсімі сілтегішті түйіншекке мен кейінгі x элемент немесе nil, егер көрсетілген элемент соңғы ағашқа қайтарады

Procedure Successor ( x );

If (right[x] ≠ nil) then Return Minimum (right[x]);

y:= p[x];

while (y ≠ nil) and (x=right [y]) do {x:= y; y:= parent[y]};

Return y

end.

Келтiрiлген процедура екi жағдайды бөлек қарастырылады. Егер шың x оң ағаш астындағысы бос болмаса, онда келесi x элементке - бұл ағаш астындада ең төменгi элемент және ([x ] right) Minimum тең бол. Болғанша, егер шың x оң ағаш астындасы бос болса, онда x жүр өз ата-анасын сол ұл болатын шыңды үстiне таппаймыз. Бұл (егер ол барып тұр) ата-ана және iзделiп отырған элемент болады. Процедура Successor ағашындағы жұмысын уақыты биiктiгінде(h), өйткенi бiз тек - үстiне, немесе тек қана төмен қарай қозғаламыз. Predecessor процедура симметриялық.

Элементтiң қосымшасы.Процедура Insert (T, z) ағаш T қолайлы орынына элемент берiлгенге толықсытады.

Келтір- рәсім оқшау екі уақиғаны қарайды. x шыңының оң поддерево жым-жылас, сол кейінгі x элементті - ең төмен элемент осы поддереве және Minimum(right[x]) тең. x шыңының оң поддерево жым-жылас, сол вверх от x барамыз, әлі де шыңды таппаймыз, өзінің родителя сол ұлымен болып табыламын. Осы родитель(ол болса) және искомым элементпен болады. Successor рәсімінің жұмысының уақыты биіктіктің h ағашында болады Ο (h), себебі біз либо ғана вверх, либо ғана төмен жүреміз. Predecessor рәсімі симметрична.

Элементтің қосымшасы. Insert(T, z) рәсімі тапсырынды элементті T ағашының лайық жеріне үстейді.

Procedure Insert(T, z);

y:= nil; x:= root;

while (x ≠ nil) do {y:= x; if key[z] < key[x] then x:= left[x] else

x:= right[x]};

p [z]:= y;

if y = nil then root:= z else if key[z] < key[y] then left[y]:= z else

right [y]:= z

end.

қосымша уақытты Ο (h) биіктіктің h ағашы үшін сұрайды.

Элементті өшіру. Өшіру рәсімінің өлшемі өшірілетін биіктіктегі z көрсеткіші болып табылады.Өшірудің үш жолы бар.Егер z-тің баласы жоқ болса,онда ата-анасының сәйкес полясына nil-ді қоя салу жеткілікті.Егер z-та бір бала болса, ата-анасымен бірге қалдырып, z-ті алып тастауға болады.Ал егер де баласы екеу болса, z-тің артындағы өз баласы жоқ келесі y элементін тауып аламыз.Енді кілт пен қосымша деректерді z биіктігінен y биіктігінекөшіруге болады, ал y биіктігін жоғарыда көрсетілген әдіспен өшіруге болады.

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

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-суретте біржақты екі айналу түрі көрсетілген:сол жаққа және оң жаққа

Жайылып өсетін ағаштар үшін бір операцияға есептегенде есептік құны O (log n)-ді құрайды.

Б-ағаштары дегеніміз- магниттік дискіде немесе тікелей жеткізілетін құралдарда ақпаратты сақтауды қамтамасыз ететін теңестірілген ағаштардың бір түрі. Б-ағаштары қызыл–қара ағаштарға ұқсайды.Айырмашылығы мынада: қолданылатын дисктің мінездемесіне қарай Б-ағаштарының бөліктерінде көп бала, іс жүзінде мыңға дейін болуы мүмкін.Осыған байланысты ағаштың биіктігі O (log n)-ді бағалау нәтижесі бойынша қызыл–қара ағаштарға қарағанда айтарлықтай аз мөлшерде. Қызыл–қара ағаштар сияқты Б-ағаштары да O (log n) мерзімінде көптеген n өлшемдегі әр қилы операцияларды жүзеге асыра алады.

x түйіншегі, сақта- n[x] кілттердің, n имеет[x] + 1 бала-шағалардың. x кілттерге деген сақтал- қызмет ет- барлық оның бұтақтарын бас n бөлетін шекаралармен[x] + 1 топтардың; үшін бас-басы топты бір x бала-шағаларынан жауап береді. При ізденісте Б-дереве біз искомый кілтті мен n салыстырамыз[x] ара x сақталатын кілттермен, қарамастан және дейін ре-зультатам салыстыр- сайлаймыз

Дискте берілген деректер құрылымдағы жұмыстардың ерекшеліктері.

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

Диск естің үлкен аумағы болып табылады, келесі х нысанымен жұмыс істеу үшін біз Disk-Read (x) арнайы(дискке жазу)операциясын орындауымыз керек.

Бағдарламаның жұмыс уақыты негізінен осы операциялардың санымен анықталады, сондықтан да Б-ағашының бөлігі дисктің бір бөлшегін түгелдей толтыру үшін бар ақпаратты бірден оқып, жазып отыру керек.Осылайша, тармақтану дәрежесі(бөліктегі бала саны) өлшемімен анықталады.

Б-ағашының типтік тармақтану дәрежесі элементтің өлшеміне байланысты 50 мен 2000 арасында болады. Іздеу барысында тармақтану дәрежесінің артуы ағаш биіктігі мен дискке оралу санын тез арада қысқартады. Мысалы,биіктігі 2 және 1001 дәрежедегі Б- ағашы миллиардтан астам кілтті сақтауы мүмкін. Тамырды үнемі оперативті есте сақтауға болатынын ескерсек, керекті кілтті іздегенде, дискке екі рет оралу жеткілікті.

Ескерту. Б-ағаштарының басқа жиі пайдаланылады ақпарат көп орыны бар жапырақтарда орналасады, себебі кілтті сақтамауға да болады, ал ішкі бөліктерде тек қана кілттер мен балаларға көрсеткіштер сақталады.

Б-ағаштарымен жүргізілетін негізгі операциялар. Б-ағашының тамыры әрқашанда оперативті есте болады деп санауға болады,өйткені дисктен оқу операциясы тамыр үшін қажет етілмейді; дегенмен де біз ылғи да тамырды өзгерткенде, дискте сақтауымыз керек.

Б-ағашында іздеу. Б-ағашында іздеу қос ағашта іздеуге ұқсас. Айырмашылығы мынада: біз х-тің әр бөлігінде (n [ x ] + 1)-тің екеуін емес, бір вариантын таңдаймыз.Іздеу барысында ағаштың тамырдан жапырақтарына дейінгі бөліктері қаралады.Сондықтан да дискке оралу көрсеткіші θ(h) = θ(log _t n) тең, мұндағы h – ағаштың биіктігі, ал n – кілттер саны. n [ x ] ≤ 2 t болғанда, онда while циклы O (t) рет, және де санау уақыты O (th) = O (t ⋅log _t n)-ға тең.

және оны орналастыратын іс-шара арқылы жасалады.Оны O (1) уақыт ішінде дисктен оқу операциясын қолданбай-ақ жүзеге асыруға болады.

Y бөлігінде қалыптасқанша 2 t бала болды; қалыптасқаннан кейін t ең кішісі қалды, ал қалғандары t жаңа z бөлігінің балалары болады, олар өз кезегінде х бөлігінің баласы болады. y бөлігінің медиана-кілті x бөлігіне қосылады да y бөлігі мен оның артындағы z бөлігін айырып тұрады.

Элементке қосылған Б-ағашы. Бұл операция қолданудан алдын процедурада қолданылады.Барлығының сынуынан бөліп екі бөлікке бөлінеді.Атқарушы t-1 элементі әрқайсысында болады.

Алдын бұл кілт-медианасы key [y] жіберіледі. Ол х бөлігі у қойылады. Бұл мән орындалған жағдайда х толық болмайды. Алайда у-түбір процедурасы анологиялық жүмыс атқарады. Бұл жағдайда ағаш ұлғайады.

Insert процедура Б-ағашқа к элемент қосады. Түбірден жапыраққа дейін бір рет өтеді. O (th) = O (t ·log _t n) уақыт керек және O (h) дискіге қарасты. Ағаштың биіктігі һ болса жұмыстың барысы бойынша ұсақтау процедурасы бойынша кездесетін толық бөлінеді. Толық бетпен ауыстыратын, яғни толық емес бетке жақын болады.Ал оны бөлуге болады. Ол оған жақын қосымшалар. Кілті сол үшін жоғары көтеріледі және оны толық емес элементтерге қосамыз.

Б-ағашын өшірілуі. Б-ағашының элементтен өшірілуі ол аналитикалыққа кіреді,қиын болмаса да. Оқырмандарға көрсетілетін процедураларда мүмкін өшіріледі. Бөлікте құралған О һ жүктеледі. Б-ағаштан ұзын һ, сосын оған барлық процедуралар жүктеледі O (t · h) = O (t ·log _t n).

Қорытындыда байқайтынымыз аға балансталған және Б-ағашы кітаптан қарастыру болады. Кнута Ахо, Хопкрофта және Ульмана және Седжвика. Тура баламадан Б-ағашын кітаптан Кормена және басқалар Тибас және Сиджвик қарастырады және олардың әр түрлі болатынын айтты. Ағаштың құрамында қосылатын қызыл-қара және 2-3-4 ағаштар.

1970 жылы Хопкрофт бұл тұжырымдамаларды 2-3 ағаштарды және алдында айтылған Б-ағашын және 2-3-4 ағаштарды қарастырды. Бұл ағаштардың әрқайсысы бұтақтарды немесе үш бұтақтан бола алады. Б-ағашын арнайы Байером және Мак Крейтом 1972 жылы қарастырды.

Кеңістікті іздеу.

Жоғары алгоритмнің жұмысы, жоғары нүктелері мен қабырғаларын қарастырады. Қандайда бір жағдайда орындалатын нүктелерді алдыннан қарастырады. Қарастырылмаған шыңда жана деп алайық. Соған қатысты қарастырылған шың ашық болып қала береді.Сосын ғана жабық болады.

Қабырғаны кеңдігіне қарай қарау идеясының мәні алдын ала тандалған немесе берілген басты а шыңының кезекпен өшірілгендерді қарастыра алуында. Басқаша айтқанда, ең алдымен а шыңның өзі қарастырылады, сосын барлыщ шыңдар, а-мен қосылған,яғни 1 қашықтығының арасында орналасқан,ал содан кейін 2 қашықтығының арасында орналасқандар және т.б.

а бастамалық шыңға іздеу алгоритмын қарастырайық. Ең бірінші а шыңы қарастырылады, ол жалғыз ашық шыңға айналады. Бұл шың активті болады. Әрі қарай әрбір қадам х ашық шыңынан басталады. Ары қарай активті шыңға қатысты қабырғалар зерттеледі. Егер бұндай қабырға жаңа х шыңы у-ке қосылса, онда у шыңы қарастырылады да, ашық шыңға айналады. Активті шыңға қатысты зертелгеннен кейін, ол активті болмай, жабыққа айналады. Содан кейін жаңа активті шың тандалады, және жұмыс барысы қайталанады.Көптеген ашық шыңдар бос болғанда, процессс аяқталады.

Кеңістікте іздеудің басты ерекшелігі, ол графқа көшу амалы басқашалығында, Алдындағы ашық шыңдардың бірінен тандалынады. Стартқа шың жақын болса, ол тез қарастырылады.

(BFS –ағылшын тіліндегі алгоритмнің мағынасы – Breadth First Search) біт старттық а шыңынан кеңістіктегі іздеу шыңындағы процедурасын қарастырайық. Көптеген барлық шың қарастырылады. Х шыңына жақын, Q-ашық шыңның кезегі.

Procedure BFS(a)

1 a шыңын қарастыру

2 a ⇒ Q

3 while Q ≠ ∅ do

4 x ⇐ Q

5 for y ∈ V (x) do

Дата добавления: 2014-01-15