Идентифиқатор жадвалини дарахт шаклида тузиш

Идентифиқатор жадвалини дарахт шаклида тузиш.
Идентификатор жадвалида тўлгазиш вақтни оширмасдан қидириш вақтни камайтириш мумкин. Бунинг учун жадвални бинар дарахт кўринишда ташкил қилиш керак. Хар бир тугун элемент тўғрисида маълумотни саклайди. Дарахтни илдизида биринчи элемент ёзилади. Дарахтни хар бир чўққиси иккита шохга эга бўлиши мумкин ўнг шохи ва чап шохи.
Компьютерда дарахтни тугунларини структура турида бўлган кўрсаткич кўринишда таърифлаш мумкин . Масалан
struct daraht
{
char Nid [20]; // идентификатор
daraht * Pshap; // чап тугунни манзили
daraht * Pong; // ўнг тугунни манзили
}
daraht * Ildiz; // дарахтни илдизи
daraht * Tugunj, *Tugun; // дарахтни жорий тугуни
char ident[20]; // жорий идентификатор
Ildiz = new daraht;
Дарахт тузими расмда келтирилган:

Илдиз

Расм2. Дарахт тузилиши.
Дарахтни тўлдириш алгоритмни блок-схемасини кўрайлик.

Расм 3. Дарахт кўринишдаги жадвални тўлдириш блок-схемаси.

Дарахтда элементни қидириш алгоритми блок схемада(Расм 4.) келтирилган.

Расм 4. Дарахтда идентификатор қидириш блок-схемаси.

Мисол сифатида куйидаги идентификаторлар кетма кетлигини кўрайлик GA,D1,L2,E,A12,BC,F. Бу кетма кетлик учун алгоритм бўйича дарахт тузамиз (Расм 5).

Расм 5. Берилган мисол учун тузилган дарахт.
Бу дарахта икки идентификаторлар қидириб кўрамиз A12 ва N1;
Кўрсатилган дарахт бўйича A12 идентификаторни 3 кадамда бор-йўқлигини аникладик N1 идентификаторни 1 қадамда аниқладик.
Берилган усулда солиштириш сонлари ва дарахт шакли идентификаторлар аникланиши кетмакетлигига қаттиқ боғлик.
T_n=N*O(log₂(N)); T_k=O(log₂(N))
Умуман айтиб ўтсак бинар дарахт усулу идентификаторлар жадвалини тузишга анча қулайдир.
6 мавзу. Хэш-функция ва хеш-адреслаш
Хэш-функцияни ишлаш принципи.
Жадвалларни тўлдириш ва қидириш вақти логарифмик боғланиши бу жуда яхши лекин идентификаторлар сони жудаям катта бўлиши мумкин бу холди бошқа усуллар қўллашга тўғри келади.
Хэш-функцияларни қўллаш усуллари яхши натижага олиб келади.
R элементлар тўпламини Z бутун мусбат сонлар тўпламига акс эттирувчи функция . Хэш функция деб номланади. Кирувчи элементлар тўплами хеш функцияни аниқлаш сохасига киради. Хеш функцияни қиймат сохаси деб тўплам қисми М дейилади . Хэш функцияни аниқлаш сохасини қийматлар тўпламига акс эттириш жараёни хэшлаттириш деб тақдим қилинади.
Идентификаторлар жадваллар устида ишлаганда хэш функция идентификаторларни бутун сонларга акс эттириши керак. Шунда хэш функцияни аниқлаш сохаси барча идентификаторлар номлари бўлади. Хэш адреслашда хэш функцияни қиймати бирорта берилганлар массивни элементларини адреси деб хисобланади. Бундан кўриниб турибдики массивни ўлчови фукцияни қийматлар сохасига тенг бўлиши керак. Яни хэш функцияни максимал қиймати компютер хотирасида ошиб кетмаслик керак.

Жадвални тузиш куйидагича бўлади, жорий элементни хэш-функцияси хисобланади. Хосибланган қиймат элементни жойлаштирадиган ячейкани адресини беради.
Шундай қилиб хар қандай идентификатор учун уни хэш функциясини хисоблаш етарли ва шу ячейкага идентификатор юкланади.
Қидиришда хам элементни хэш функцияси хисобланади ва шу адрес бўйича ячейка бўшлиги текширилади агар бўш бўлмаса элемент жадвалда бор акс холда бундай элемент йўқ. Расмда хэш-функцияни ишлаш принципи кўрсатилган.
Бу усул жуда яхши чунки элементни жадвалга юклашга ва қидиришга кетган вакт функцияни хисоблаши билан ўлчанади бу жуда камдир.
Бу усулни иккита камчилиги бор:
Биринчидан хотирани ноэффектив ишлатиш , чунки массивни ўлчови функцияни қийматлар сохасига тенг бўлиши керак, аксинча реал идентификаторлар сони анча кам бўлиши мумкин.
Иккинчидан яхши қаноатлантирадиган хеш-функцияни танлаш муаммоси.
Хэш функцияни танлаш усуллари.
Хэш функцияни хар хил вариантлари мавжуд. Хэш функцияда кўпинча белгилар кетмакетлиги устидан бирор арифметик ёки мантиқ амаллар бажарилади. Масалан дейлик сатрдаги биринси белгини аски қодини натижа қилиб олиш мумкин масалан А харифни коди 65 мана шу қиймат хэш функцияни қиймати деб хисобласа бўлади. Лекин бундай хэш функцияда янги муаммо пайдо бўлади иккита хархил идентификаторлар бир хил харифдан бошланса уларни хэш функция қиймати бир хил бўлиб қолади. Бу холда битта ячейкага иккита идентификаторларни жойлаштириш керак бўлади бу албатта мумкин эмас. Икки ёки кўп идентификаторларни хэш функцияси бир хил қийматга эга бўлган холат коллизия деб номланади.
Албатта коллизияга эга бўлган функцияларни тўғрима тўгри ишлатиб бўлмайди. Назарий коллизияга эга бўлмаган функцияларни тузиш мумкин масалан хар бир харифни кодини кетма кет ёзилиб чиқилса хосил бўлган сон адресни кўрсатиши мумкин , лекин бундай фукция учун массивди узунлиги чексиз бўлиб қолади, вахоланки компютер хотираси чекланган, бундан хулоса қилиш мумкинки коллизиядан кутулиш иложиси йук , шунинг учун коллизияни ишлатадиган усуллар қўллаш керак.