2D rectangle intersection search
2D rectangle intersection search deb, berilgan N ta töğri törtburçaklar orasidan ustma-ust tuşganlarini topişga aytiladi.
#binary search tree
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.
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.
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.
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.
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.
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.
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.
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.
Binary search tree ustida amallar. API yoziş
BSTga element qöşiş, öçiriş, qidiriş, maksimum/minimum elementni çiqariş uçun API yozamiz. APIning tuzilişi quyidagiça böladi.