Fizika-matematika fakulteti

Ildizni ajratish. Agar qo'shilish joyidan ildizgacha bo'lgan butun yo'l bo'ylab 3 ta tugunga ega bo'lsak, vaqtincha 4-tugunni ildizga ulaymiz. Bunday holda bitta 3 tugundan iborat bo'lgan daraxtni kiritish kabi aniq harakatni davom ettirishimiz mumkin. Vaqtinchalik 4-tugunni uchta 2-tugunga bo'ldik va daraxtning balandligini 1-ga oshiramiz. Oxirgi o'zgarish mukammal muvozanatni saqlaydi, chunki u ildizda amalga oshiriladi.

9-rasm. Ildizni ajratish.

Mahalliy o'zgarishlar. Vaqtinchalik 4-tugunni 2-3 daraxtga bo'lish quyida umumlashtirilgan oltita o'zgarishlardan birini o'z ichiga oladi. 4-tugun ildiz bo'lishi mumkin; bu chap tugun yoki 2-tugunning o'ng farzandi bo'lishi mumkin; yoki u uchta tugunning chap bolasi, o'rta bolasi yoki o'ng bolasi bo'lishi mumkin. 2-3 daraxtni kiritish algoritmining asosi shundan iboratki, ushbu o'zgarishlarning barchasi faqat lokal(mahalliy)dir: daraxtning biron bir qismi ko'rsatilgan tugunlar va bog'lanishlardan tashqari hech qanday tekshirilishi yoki o'zgartirilishi kerak emas. Har bir transformatsiya uchun o'zgartirilgan havolalar soni kichik bir doimiy son bilan cheklangan. Xususan, daraxtning biron bir joyida belgilangan naqshlarni topsak, nafaqat pastki qismida transformatsiyalar samarali bo'ladi. O'zgartirishlarning har biri 4-tugundan bitta tugmachaning ota-onasiga kalitlardan birini uzatadi va so'ngra daraxtning boshqa qismiga tegmasdan bog'lanishlarni o'zgartiradi.

10-rasm. Mahalliy o’zgarishlar.