2D range search. KD-tree
Masala. Berilgan kartadan ma’lum bir yuza ichiga kirgan nuqtalar sonini topish kerak. Ularni dasturda qanday qilib topamiz? Eng keraklisi, nuqtalarni dasturda qanday ifodalaymiz?
Dasturchi, frilanser, gik va introvert
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.
2-3 tree haqida tanishib chiqqan bo’lsangiz, unda node qo’shishda ko’p shartlarni hisobga olish kerak bo’lardi. Umuman, 2-3 tree’ni kodda ifodalash qiyin edi. Red-black tree mana shu insertdagi qiyinchiliklarga yechim sifatida keladi.
Balanced search tree’da biz binary search tree’ning uzunligini kamaytirish hisobiga, worst case’ni O (log N) gacha tushiramiz.
Agile yondashuvi jamoalarni innovatsiya qilishga, o’zgarishlarga tezda reaksiya bildirishga undaydi. Shu sababli kompaniyalar agile metodologiyasini qo’llashga, shu jumladan, Scrum, Kanban, Lean kabi freymvorklaridan foydalanishga harakat qilishadi.