Kategoriya

Algoritmlar

Oktabr 26, 2020by Sherzod Shermukhamedov

1D interval search. Intervallar kesişmasini topiş

1D interval search (1D interval qidiruv) deb berilgan interval asosida u bilan kesişadigan boşqa intervallarni topişga aytiladi.

Oktabr 22, 2020by Sherzod Shermukhamedov

2D range search. KD-tree

Masala. Berilgan kartadan ma'lum bir yuza içiga kirgan nuqtalar sonini topiş kerak. Ularni dasturda qanday qilib topamiz? Eng keraklisi, nuqtalarni dasturda qanday ifodalaymiz?

Oktabr 20, 2020by Sherzod Shermukhamedov

2D line segment intersection. Sweep line algoritmi

Masala. N ta gorizontal va vertikal çiziqlar berilgan. Çiziqlarning kesişgan nuqtalarini topiş kerak. Har bir çiziqning çap va öng - boşlaniş va tugaş nuqtalari ma'lum.

Oktabr 18, 2020by Sherzod Shermukhamedov

1D range search. Binary search tree'dan berilgan oraliqdagi qiymatlarni topiş

1d range search (one dimension range search, bir ölçamli oraliq qidiruv) deb, röyxatdan berilgan oraliqda yotgan elementlarni topişga aytiladi.

Oktabr 17, 2020by Sherzod Shermukhamedov

AVL-Tree ustida amallar. API yoziş

AVL-Tree'ga tegişli bölgan amallar törtta - çapga buriş; öngga buriş; avval çapga, keyin öngga buriş; avval öngga, keyin çapga buriş. Ular haqida avvalgi maqolada töxtalganimiz bois, bu yerda faqat kod yoziş bilan çeklanamiz.

Oktabr 15, 2020by Sherzod Shermukhamedov

Balanced search tree. AVL-tree

AVL-tree (kaşfiyotçilari Adelson-Velsky va Landis'lardan olingan) yana bir balanslangan binary search tree. AVL-tree'ga ötişdan oldin, balanced binary tree haqida eslab olamiz.

Oktabr 14, 2020by Sherzod Shermukhamedov

Balanced search tree. B-tree

B-tree 2-3 tree'ga öxşaş, ammo bir neça jihatlar bilan farqlanadi. Har bir node'da M-1 gaça key qöşiladi. Bunda M bitta blokdagi ma'lumotlar soni.

Oktabr 13, 2020by Sherzod Shermukhamedov

Red-black tree ustida amallar. API yoziş

Red-black tree'dagi node'ning binary search tree node'idan farqi - unga color atributi qöşilgan. Color node'ning qizil yoki qizilmas ekanini aniqlaş uçun kerak böladi.

Oktabr 12, 2020by Sherzod Shermukhamedov

Balanced search tree. Red-black tree

2-3 tree haqida tanişib çiqqan bölsangiz, unda node qöşişda köp şartlarni hisobga oliş kerak bölardi. Umuman, 2-3 tree'ni kodda ifodalaş qiyin edi. Red-black tree mana şu insertdagi qiyinçiliklarga yeçim sifatida keladi.

Oktabr 11, 2020by Sherzod Shermukhamedov

Balanced search tree. 2-3 tree

Balanced search tree'da biz binary search tree'ning uzunligini kamaytiriş hisobiga, worst case'ni O (log N) gaça tuşiramiz.