Тиімділігі

Алгоритмді жобалағанда және дербес жағдайда деректердің құрылымында ағаш кең қолданыста болады. Оқырманды әдебиет жағынан графтың қағидасына көнілін бұрсақ, түйіншек, қабырға, парақ, жұрағат, ұл, сол жұрағат, оң жұрағат, баба, әке, түп, тармақ және басқа да ұғымдарды пайдаланамыз.

Графта қысқаша жолдарды іздестіру

Кіретін деректер:

- Граф G өлше- қабырғалармен(Салмақ жайлы айтқанда қабырңанын ұзындығы деп түсінуге болады, егер геометриялық граф жайлы айтса немесе басқа да қабырғаның санды мінездемелерінде де солай түсінуге болады)

- s бастаманың шыңы (қалған барлық шыңға дейінгі қашықтықты есептейтін шың) Демалыстар: деректерлер

- dist алабы[1.. n], (dist[i] –s шыңынан i шыңына дейінгі қысқа қашықтық).

- up алабы[1..n], (up[i] –s-тен i-ге дейінгі қысқа жолдың соңынының алдындағы шың).

Дейкстраның алгоритмы

Дейкстрының алгоритмыграфқа арнайы қарсылы емес салмақты шыңдары бар есептерді дұрыс есептейді. Егер графта қарсы салмағы бар қабырға болса, бірақ қарсы суммарлы салмақпен цикл болмаған жағдайда, есеп шығу үшін Форд немесе Баллманның алгоритмін пайдалансақ болады. 1. up[1.n] алабын нөлдермен толтыру.

2.Әрбір i шыңына dist[i] кілтінің орнынаdist[i] –максималды мүмкін санды (ол графтағы қысқа жолдардың көбісінің ұзындығынан үлкен болуы қажет; есептеу барысында бұл сан азаяды және соңында s шыңынан i шыңына дейінгі қысқа жолдағы ұзындықпен алмасады).

3. Графтың шыңдарынан басымды кезек ұйымдастыру, кілттің орнына dist [ i ], i = 1, 2, …, n. аумағын алу.

4. s шыңының кілтін 0-ге ауыстыру.

5. Әлі де кезек бос емес жағдайында6 – 7 операцияларын орындау.

6. Басым кезектен r ₀ элементін таңдап алу(өшіре);

7.Әрбір r0 шектес r ш 8,9 операциялапын орындау.

8. delta = dist [ r ] – (dist [ r ₀] + L (r ₀, r)) аумағын есептеу;

9. Егер delta > 0, онда r элементінің кілті dist [ r ] delta аумағына ке міту және up [ r ] ескірген аумағын r ₀ ауыстыру;

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

• Search - берілген кілтпен элементті іздестіру,

• Minimum –минималды кілтпен элементті іздестіру,

• Maximum –максималды кілтпен элементті іздестіру,

• Predecessor –іздестіру алдыңдағы кілтпен элементті іздестіру,

• Successor –келесі кілтпен элементті іздестіру,

• Insert –өзінің кілт арқылы элементті енгіз,

• Delete –көрсетілген элементті өшіру.

Ізденістің ағашы сөздік ретінде де, басымды кезек ретінде де пайдалануы мүмкін.

Негізгі операций орындалуының уақыты ағаштың биіктігіне пропорционал. Егер әрбір жұпты ағаштын ішкі түйіншегінің екі жұрағаты болады, сонда оның ұзындығы және негізгі операциялардыә орындалу уақыты түйінше санының логарифміне пропорционал. Керісінше, егер ағаш н түйіншектен құралған сызықты шынжырды көрсетсе, бұл уақыт до Θ(n) дейін көбейеді. Байкаусыз ізденіс жұпты ағашы бұл өзі Ο (lоg n) екені белгілі, сондықтан бұл жағдайда Θ(lоg n) негізгіі операцияларды есептеу уақыты болады.

Әрине,пайда болатын iздестiру екiлiк ағашының тәжiрибелерiнде кездейсоқтан алыс бола алады. Алайда, бiз ағаштарды теңдеуiш бойымен арнайы өлшемдер қабылданып n түйiндермен ағаштарын биiктiк болғанын кепiлдiк бере аламыз 0(log n). Тәсiлдемелердiң бiрлерн мысалды төменде қарап шығамыз. (қызыл-қара ағаштар - АВЛ, дербес жағдайда ағаштар).Сонымен бiрге мәлiметтер үшiн әсiресе ыңғайлы кез келген (дискте) рұқсаты бар екiншi жад сақталған Б-ағаштар қарастырылады. Бұл туралы:

Iздестiру екiлiк ағашының ұсынысы. Iздестiру екiлiк ағашы әрбiр түйiнiне өлшенген элемент сәйкестiкке орнатылған түбiрлiк екiлiк ағашы деп аталады. Әрбiр түйiн x үшiн келесi шартты орындайды.

X түбiрi бар сол ағаш астындағы барлық х түйiндерiнiң салмағынан аз немесе тең, онының оң жақ ағаш астындасының түйiндерiнiң салмағы артық немесе түйiн x салмағына тең.

Келесi түрдiң түйiндерiмен мұндай ағаш өкiлдiк етедi

Node = (element, key, left, right, parent)

T ағашқа рұқсат сiлтеме root көмегiмен жүзеге асырылады.

Екiлiк iздестiру ағашымен операциясы. Көрсетемiз, екiлiк iздестiру ағаштары операция Search, Minimum, Maximum, Successor және Predecessor уақытқа орындауға мүмкiндiк береді (h), ағаштың биiктiгi h.

1. (Search) iздестiру. Iздестiрудiң процедурасы k және x iздестiрудi iстелетiн ағаш астынданың түбiрiне көрсеткiш кiре берiске iзделiп отырған кiлт алады. Ол (егер болса) k немесе (егер мұндай шың жоқ жағдайда) nil кiлтпен шыңға көрсеткiштi қайтарады.

Procedure Search (x, k);

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