Binary search tree bilan tanişib çiqqan bölsangiz, ular uçun barça amallar - search / insert / delete'da worst case - O(N) ga, ya'ni daraxtning uzunligiga teng edi (aniqroği, binary search tree - degenerate bölganda).

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

Balansni kafolatlaş uçun, dastlabki qadam - binary search tree node'larida bittadan köp qiymat beriş hisoblanadi. Bu 2-3 search tree'ni işlatgan holda amalga oşiriladi.

2-3 search tree

2-3 search tree - samaradorlikni oşirişga qaratilgan balanced search tree'ning bir körinişi. U node'larga 1 yoki 2 ta qiymat berişni va node çild'larida 3 ta node yoki 2 ta node bölişini nazarda tutadi.

2-node. bitta qiymat, ikkita child. Çap child parent'dan kiçik va öng child parent'dan katta (binary search tree'dagidek).

3-node. ikkita qiymat, uçta child. Çap child - parent'dagi ikki qiymatdan ham kiçik; örtadagi child - ikki qiymat oraliğida (kiçik qiymatdan katta va katta qiymatdan kiçik); öng child - parent'dagi ikki qiymatdan ham katta.

2-3 tree. Image credit: algs4.cs.princeton.edu

2-3 tree hususiyatlari

• Mukammal balansga ega: root'dan leaf'gaça bölgan har bir yöl bir xil uzunlikka ega.
• Symmetrik tartibda: Har bir node özining çap çild'idagi barça node'lardan katta, özining öng çild'idagi barça node'lardan kiçik. 3-node holatida esa, örtadagi child node'lari node'ning ikki qiymati oraliğida.

2-3 tree'da amallar

Biz 2-3 tree uçun kod yozmaymiz, çunki 2-3 tree işini ifodalaş - ayniqsa qöşiş (insert) va öçiriş (delete) uçun qiyin, juda köp şartlarni hisobga oliş kerak böladi. Şu sababli faqat nazariyasini körib çiqamiz.

Search. Qidiruv huddi binary search tree'dagidek böladi. Yagona farqi - uç çild'li node'da qidiruv örtadagi çild'dan davom etişi mumkin.

• Agar qidirilayotgan element node'ning qiymat(lar)idan kiçik bölsa, qidiruv çap çild'dan davom ettiriladi.
• Agar qidirilayotgan element node'ning qiymat(lar)idan katta bölsa, qidiruv öng çild'dan davom ettiriladi.
• Agar qidirilayotgan element 3 çild'li node'ning ikki qiymati orasida bölsa, örtadagi çild'dan davom ettiriladi.

2-3 tree'da qidiriş. algs4.cs.princeton.edu

Insert (2-node). Dastlab qöşilayotgan element qidiriladi. Agar qidiruv 2-node'da töxtasa, şunçaki element ikkinçi key sifatida qöşiladi va node 3-node'ga aylanadi. Binary search tree'da biz yangi child qilib qöşgan bölardik, töğrimi? 2-3 tree'da ikkinçi key bölib qöşiladi. Sababi? Tree'ni mukammal balansda uşlab turiş uçun.

Insert (3-node). Qidiruv 3-node'da töxtadi. Bunday holatda yangi key uçun joy node'da yöq. Qöşişni amalga oşiriş uçun 3-node'ni 4-node'ga özgartiramiz (3 qiymatli node). Oddiy aytganda, node'ga 3-qiymatni qöşamiz.

Keyin 4-node'ni 3 ta 2-node'ga özgartiramiz.

Insert (parent node'i 2-node bölgan 3-node). Qidiruv parenti 2-node bölgan 3-node'da töxtadi. Bunday holatda ham vaqtinça 4-node'ga aylantiramiz, lekin örta key uçun yangi node qöşmasdan, örta key'ni 2-node parent'ga qöşamiz (Rasmda tuşunarliroq).

Insert (parent node'i 3-node bölgan 3-node). Bunda ham vaqtinça 4-node'ga aylantiramiz, keyin örtadagi key'ni parent'ga qöşamiz. Parent 3-node bölgani uçun, yangi key qöşilgaç 4-node bölib qoladi. Parent uçun ham transformatsiyani - örtadagi key'ni parentga beriş amaliyotini qöllaymiz. Şu tariqa, 2-node'li parent'ga yetmagunimizça yoki root'da 3-node qilmagunimizça, 4-node'larning örta key'ini parentga berib boramiz.

2-3 tree'da transformatsiya

Transformatsiya deb 4-node'ni bölişga aytiladi.

2-3 tree'da tree' uzunligi faqat root 4-node bölib qolgandagina bittaga oşiriladi. Bunda 4-node 3 ta 2-node'ga ajratiladi. Örta qiymatdagi 2-node parent bölsa, kiçigi left child, kattasi right child böladi. Faqat root'dan uzunlikni oşiriş bizga 2-3 tree'ning mukammal balansda qolişini ta'minlaydi.

Tahlil

Tree'da barça operatsiyalar uçun worst case tree'ning uzunligiga teng. 2-3 tree'da biz mukammal balansli tree'ga erişganimiz uçun barça operatsiyalar uçun worst case O(log N) ga tuşadi.

• worst case - tree'da barça node'lar 2-node. Tree uzunligi log N ga teng
• best case - tree'da barça node'lar 3-node. Tree uzunligi log₃ N