Fizika-matematika fakulteti

XULOSA

  Qidirish algoritmi juda samarasiz va ko’p vaqtni talab qiladi. Ushbu muammoni bartaraf etish va yo'q qilish uchun biz o'z-o'zini muvozanatlaydigan daraxtining g'oyasini taqdim etamiz: balandlikni tekshirish va aylantirish orqali yanada muvozanatli tuzilishga ega bo'ladi; shu sababli ba'zi ma'lumotlarni qidirishga kamroq vaqt ketadi. O'z-o'zidan muvozanatlanadigan ikkilik qidirish daraxti (BST) - bu har doim avtomatik ravishda o'zining balandligini imkon qadar minimal darajada saqlashga harakat qiladi (kiritish yoki o'chirish kabi operatsiyalarni bajargandan keyin ham). Shunday qilib, biz BST-larni o'z-o'zini balanslash uchun har doim minimal balandlik ( log ) yaxlitlanishi haqida ma’lumotga ega bo’ldik.

Shunday qilib, biz 2-3 daraxt bilan samarali qidiruvni kafolatlay olamiz. Har bir tugunga har bir operatsiya uchun talab qilinadigan vaqt miqdori doimiy son bilan bog'lanadi va ikkala operatsiya ham bitta yo'lda tugunlarni tekshiradi, shuning uchun har qanday qidirish yoki kiritishning umumiy qiymati logarifmik bo'lishi kafolatlanadi.

Ma'lumotlar bilan to'lib-toshgan dunyoda, odamlar trillionlab yozuvlarga ega jadvallarni saqlashadi, haqiqat shundaki, bunday jadvallarda ushbu operatsiyalarning istalganini bir necha o'nlab taqqoslash amali bilan bajarish imkoniyati mavjud.