Dasturchi, frilanser, gik va introvert
Agar biz o’zimiz hash funksiya yozadigan bo’lsak, albatta collision’da nima qilish kerakligini ham aniqlab olishimiz kerak. Collision’ning yechimi sifatida ikki usul keltirilgan: Separate chaining va Linear probing.
Hash table (hashtable, hash, hash map) – key’larni value juftlarini bog’laydigan ma’lumot tuzilmasi. Kodda ko’pincha assotsiativ array (Javascriptda object) ko’rinishida ifodalanadi. Hash table’ning dictionary’dan farqi – array indekslari integer bo’lib, hash funksiya yordamida generatsiya qilinadi va indekslar unikal bo’ladi.
Shanba kuni Ratchaburi viloyatini aylanib keldik. Ratchaburi Bangkokdan 1.5 soatlik yo’l, turistik joyi ko’p emas. Bir-ikki kunlik sayohat uchun yetarli, «для галочки». Dastlab, «Khao Ngu Stone Park»ga kirdik. Park – oddiy park, qoyalar orasida ko’l bor. Tabiiy hududga kichik o’zgarishlar kiritilgan – ko’prik va ko’l ustidan yo’l qurilgan.
2D rectangle intersection search deb, berilgan N ta to’g’ri to’rtburchaklar orasidan ustma-ust tushganlarini topishga aytiladi.
1D interval search (1D interval qidiruv) deb berilgan interval asosida u bilan kesishadigan boshqa intervallarni topishga aytiladi.
Masala. Berilgan kartadan ma’lum bir yuza ichiga kirgan nuqtalar sonini topish kerak. Ularni dasturda qanday qilib topamiz? Eng keraklisi, nuqtalarni dasturda qanday ifodalaymiz?
Masala. N ta gorizontal va vertikal chiziqlar berilgan. Chiziqlarning kesishgan nuqtalarini topish kerak. Har bir chiziqning chap va o’ng – boshlanish va tugash nuqtalari ma’lum.
1d range search (one dimension range search, bir o’lchamli oraliq qidiruv) deb, ro’yxatdan berilgan oraliqda yotgan elementlarni topishga aytiladi.
AVL-Tree’ga tegishli bo’lgan amallar to’rtta – chapga burish; o’ngga burish; avval chapga, keyin o’ngga burish; avval o’ngga, keyin chapga burish. Ular haqida avvalgi maqolada to’xtalganimiz bois, bu yerda faqat kod yozish bilan cheklanamiz.
AVL-tree (kashfiyotchilari Adelson-Velsky va Landis’lardan olingan) yana bir balanslangan binary search tree. AVL-tree’ga o’tishdan oldin, balanced binary tree haqida eslab olamiz.