درخت جست‌وجوی دودویی رو با ترتیب درج بساز

قانون جای هر عدد

درخت جست‌وجوی دودویی هر عدد کوچک‌تر از یک گره رو سمت چپ و هر عدد بزرگ‌تر رو سمت راست می‌ذاره. شبیه‌ساز عددهای ۱ تا تعداد انتخاب‌شده رو یکی‌یکی به ترتیب مشخص‌شده وارد می‌کنه.

چرا ترتیب ورود مهمه؟

درج پی‌درپی عددهای رو به بالا، هر بار به انتهای شاخهٔ راست می‌رسه؛ عددهای رو به پایین هم زنجیر سمت چپ می‌سازن. درج از میانه‌ها می‌تونه شاخه‌ها رو کوتاه‌تر نگه داره.

ارتفاع و عمق

height_nodes = 1 + max(height(left),height(right)); avg_depth = sum(depths)/n

ارتفاع این مدل تعداد گره‌ها در بلندترین مسیر از ریشه تا برگ رو می‌شمره؛ ریشه یک سطح حساب می‌شه. میانگین عمق، عمق همهٔ گره‌ها رو جمع و بر تعدادشون تقسیم می‌کنه.

نمرهٔ تعادل این مدل

root_balance = abs(height(left)-height(right))

نمره فقط اختلاف ارتفاع شاخهٔ چپ و راستِ ریشه رو می‌سنجه. نمرهٔ صفر یعنی دو سمت ریشه هم‌ارتفاعن؛ این به‌تنهایی تضمین نمی‌کنه همهٔ گره‌های داخل درخت متوازن باشن.