Dasturchi, frilanser, gik va introvert
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.
B-tree 2-3 tree’ga o’xshash, ammo bir necha jihatlar bilan farqlanadi. Har bir node’da M-1 gacha key qo’shiladi. Bunda M bitta blokdagi ma’lumotlar soni.
Red-black tree’dagi node’ning binary search tree node’idan farqi – unga color atributi qo’shilgan. Color node’ning qizil yoki qizilmas ekanini aniqlash uchun kerak bo’ladi.