درخت جستجوی دودویی متوازن وزن‌دار
درخت جستجوی دودویی متوازن وزن‌دار نوعی خاص از درخت جستجوی دودویی است. این درخت با دانستن احتمال جستجوی هر گره، متوازن می‌گردد. احتمال مورد جستجو قرار گرفتن هر گره، وزن آن گره نامیده می‌شود. در هر زیردرخت گره‌ای که بیشترین وزن را دارد به عنوان ریشه در نظر گرفته می‌شود. بر این اساس سرعت جستجو بهبود پیدا می‌کند.
ساخت این درخت بسیار شبیه به داده ساختار تیریپ است؛ با این تفاوت که وزن گره‌ها به جای آن که به صورت تصادفی انتخاب گردد، بر اساس احتمال مورد جستجو قرار گرفتن تعیین می‌گردد.
تحلیل زمانی
در یک درخت جستجوی دودویی متوازن وزن‌دار با n گره، امید ریاضی طول جستجوی موفق، به مقدار بهینه لگاریتمی (log (n نزدیک است. در درختی که در تصویر مشاهده می‌گردد، این مقدار چنین محاسبه می‌شود:
امید ریاضی طول جستجوی موفق = احتمال جستجوی گره A * عمق گره A + احتمال جستجوی گره C * عمق گره C + ...
۲.۵ = ۰.۱۷ * ۲ + ۰.۰۳ * ۵ + ۰.۰۹ * ۴ + ۰.۱۲ * ۳ + ۰.۲۰ * ۱ + ۰.۱۱ * ۳ + ۰.۱۰ * ۳ + ۰.۱۸ * ۲
در نهایت، مقدار به دست آمده، میانگین تعداد نقاطی را نشان می‌دهد که در یک جستجوی موفق مورد وارسی قرار می‌گیرند.
جستارهای وابسته
- درخت دودویی
- درخت ای‌وی‌ال
- درخت بی
- درخت سرخ-سیاه
- داده ساختار تیریپ
منابع
- Jean-Paul Tremblay and Grant A. Cheston. Data Structures and Software Development in an object-oriented domain, Eiffel Edition. Prentice Hall, 2001. ISBN 0-13-787946-6.