Fizika-matematika fakulteti

Belgilar jadvali uchun API buyurtma qilingan. Qizil qora BSTlarning eng jozibali xususiyatlaridan biri shundaki, murakkab kod put() (va o'chirish) usullari bilan cheklangan. Bizning standart BST-larda minimal, maksimal, tanlash, daraja, pol va oraliq so'rovlar uchun kodimiz hech qanday o'zgarishsiz ishlatilishi mumkin, chunki u BST-larda ishlaydi va tugun rangiga murojaat qilishning hojati yo'q. Ushbu usullar bilan birga (va o'chirish usullari) bizning buyurtma qilingan jadvalimiz API-ning to'liq bajarilishiga olib keladi. Bundan tashqari, barcha usullar daraxtdagi mukammal muvozanatdan foyda ko'rishadi, chunki ularning barchasi ko'pi bilan daraxt balandligiga mutanosib ravishda vaqt talab qiladi.

• 
  BSTning qizil-qora rangida, eng yomon holatda quyidagi operatsiyalar logarifmik vaqtni oladi: qidirish, qo'shib qo'yish, minimalni topish, maksimalni topish va diapazonlar soni.
  

Hozirda get(), put() va o'chirish operatsiyalarini muhokama qildik. Kafolatlangan logaritmik ishlash har bir algoritm tekshirilayotgan har bir tugun bo'yicha doimiy sonli operatsiyalarni bajaradi.