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.
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.
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.