Teg

#binary search tree

Oktabr 28, 2020by Sherzod Shermukhamedov

2D rectangle intersection search

2D rectangle intersection search deb, berilgan N ta to'g'ri to'rtburchaklar orasidan ustma-ust tushganlarini topishga aytiladi.

Oktabr 26, 2020by Sherzod Shermukhamedov

1D interval search. Intervallar kesishmasini topish

1D interval search (1D interval qidiruv) deb berilgan interval asosida u bilan kesishadigan boshqa intervallarni topishga aytiladi.

Oktabr 18, 2020by Sherzod Shermukhamedov

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

1d range search (one dimension range search, bir o'lchamli oraliq qidiruv) deb, ro'yxatdan berilgan oraliqda yotgan elementlarni topishga aytiladi.

Oktabr 17, 2020by Sherzod Shermukhamedov

AVL-Tree ustida amallar. API yozish

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.

Oktabr 15, 2020by Sherzod Shermukhamedov

Balanced search tree. AVL-tree

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.

Oktabr 14, 2020by Sherzod Shermukhamedov

Balanced search tree. B-tree

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.

Oktabr 13, 2020by Sherzod Shermukhamedov

Red-black tree ustida amallar. API yozish

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.

Oktabr 12, 2020by Sherzod Shermukhamedov

Balanced search tree. Red-black tree

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.

Oktabr 11, 2020by Sherzod Shermukhamedov

Balanced search tree. 2-3 tree

Balanced search tree'da biz binary search tree'ning uzunligini kamaytirish hisobiga, worst case'ni O (log N) gacha tushiramiz.

Oktabr 8, 2020by Sherzod Shermukhamedov

Binary search tree ustida amallar. API yozish

BSTga element qo'shish, o'chirish, qidirish, maksimum/minimum elementni chiqarish uchun API yozamiz. APIning tuzilishi quyidagicha bo'ladi.