درخت جستجوی دودویی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Y.samadzadeh (بحث | مشارکت‌ها) اضافه کردن سه عکس به حذف گره |
Y.samadzadeh (بحث | مشارکت‌ها) افزودن متن به انواع درخت |
||
خط ۱۵۶:
== انواع ==
درخت جستجوی دودویی گونه‌های مختلفی دارد. [[درخت ای‌وی‌ال]] و [[درخت سرخ-سیاه]] از جمله [[درخت جستجوی دودویی خود-متوازن]] هستند. [[درخت اسپلی]] نوعی درخت دودویی است که عناصری که مکرراً مورد استفاده قرار می‌گیرند را به صورت خودکار به ریشه درخت نزدیک می‌کند تا دسترسی به آن‌ها راحت‌تر شود. در یک [[تریپ]]، (tree heap) هر گره یک اولویت دارد که این اولویت به شکل تصادفی به گره اختصاص می‌یابد و گره والد اولویت بیشتری نسبت به فرزندش دارد. [[درخت تانگو|درختان تانگو]] نوعی درخت جستجوی دودویی هستند که برای جستجوهای بسیار سریع مورد استفاده قرار می‌گیرند.
درختان جست و جوی دودویی هستند که برای کاهش حافظه ی استفاده شده . به طور گسترده برای پایگاه داده های درون حافظه ای استفاده می شود.
درخت تباهیده درختی است که در آن هر والد فقط یک فرزند دارد . در واقع می توان گفت هر والد فقط یک گره دارد. ای درخت متوازن نیست و در بدترین حالت مانند یک لیست پیوندی عمل می کند. اگر با درج عنصر جدید در درخت تابع افزودن گره ، ارتفاع درخت را متوازن نکند، می توان به سادگی از بک درخت تباهیده کنک گرفت به طوری که آن را با داده های از قبل مرتب شده پر کرد. در واقع به این معنی که این درخت به صورت یک لیست پیوندی عمل خواهد
کرد.
مقایسه عملکرد ها
D. A. Heger در سال ۲۰۰۴ روشی برای مقایسه عملکرد درخت های جست و جوی دودویی ارائه داد. در این مقایسه تریپ را به عنوان بهترین عملکرد در حالت میانگین معرفی کرد در حالی که در همین مقایسه درخت سرخ-سیاه کمترین اختلافرا بین بدترین حالت و بهترین حالتش دارد هرچند به طور میانگین تریپ بهتر ازآن عمل می کند.
== جستارهای وابسته ==
| |||