Fizika-matematika fakulteti

3 tugundan iborat daraxtga joylashtirish. Umumiy ishni ko'rib chiqishdan oldin birinchi urinish sifatida, aytaylik, biz bitta bitta 3 tugundan tashkil topgan kichkina 2-3 daraxtga kirishni xohlaymiz. Bunday daraxt ikkita kalitga ega, ammo bitta tugunda yangi kalit uchun joy yo'q. Kiritishni amalga oshirish uchun biz vaqtincha yangi tugmachani 4 tugunga, uchta tugmachali va to'rtta havolaga ega tugun turining tabiiy kengaytmasiga joylashtiramiz. 4-tugunni yaratish qulay, chunki u uchta 2 tugundan tashkil topgan 2-3-daraxtga aylantirish oson, biri o'rta kalitli (ildizida), uchta tugmachasining eng kichigi (ishora qilingan). ildizning chap ulanishi orqali) va uchta kalitning eng kattasi bo'lgan (ildizning o'ng bog'lanishida ko'rsatilgan). Bunday daraxt BST 3-tugunli, shuningdek, barcha null aloqalar ildizdan bir xil masofada joylashgan mukammal qidiruv daraxti. O'rnatishdan oldin daraxtning balandligi 0 ga teng; joylashtirilgandan so'ng, daraxtning balandligi 1. Bu holat juda oddiy, ammo e'tiborga olish kerak, chunki u 2-3 daraxtda balandlikning o'sishini tasvirlaydi.

6-rasm. S element kiritilishi:3 tugundan iborat daraxtga joylashtirish.