درخت تلفیقی

دانشنامه عمومی

درخت تلفیقی نوعی داده ساختار درخت گونه است که یک آرایه ارتباطی را روی اعداد صحیح w بیتی پیاده سازی می کند. این درخت از فضایی به مقدار ( O ( n استفاده کرده و جستجو را در زمان ( O ( logw n انجام می دهد که به طور تقریبی از درخت سنتی – به نام درخت دودویی جستجوی خود تعادلی - سریع تر بوده و در واقع از درخت وان آمده باوس ( van Emde Boas tree ) در حالتی که w بزرگ است، بهتر می باشد. این نوع درخت سرعت خود را با بهره گیری از عملیات مخصوصی که در زمان ثابت انجام می شود، به دست می آورد که این عملیات می تواند توسط کلمه ( در معنای رایانه ای ) انجام شود. درخت های تلفیقی در سال ۱۹۹۰ توسط مایکل فردمن ( Michael Fred man ) و دان ویلارد ( Dan Willard ) اختراع شد. از زمان انتشار نسخه اصلی مقاله فردمن و ویلارد، چندین پیشرفت انجام شده است. در سال ۱۹۹۹ نشان داده شد که چگونه می توان درخت های تلفیقی را تحت مدل AC0 پیاده سازی کرد، به گونه ای که ضرب دیگر زمان ثابتی را به خود اختصاص ندهد. یک نسخه پویایی از درخت های تلفیقی با استفاده از جداول درهم سازی در سال ۱۹۹۶ پیشنهاد شد که با زمان اجرای مورد انتظار ( O ( logw n مطابقت داشت. یک نسخه پویای دیگر با استفاده از درخت نمایی در سال ۲۰۰۷ پیشنهاد شد که در بدترین حالت به زمان اجرای ( O ( logw n + log log u برای هر عملیات رسید. در این معادله u اندازه بزرگترین کلید است. این مسئله هم چنان باز است تا جایی که درخت تلفیقی با احتمال بالایی به ( O ( logw n در هر عملیات برسد.
یک درخت ترکیبی اساساً یک B - tree با عوامل شاخه ای w1/5 ( هر توان کوچک دیگری نیز ممکن است ) است که باعث می شود ارتفاع درخت از ( O ( logw n باشد. برای این که به زمان اجرای مطلوب از لحاظ بروزرسانی و پاسخ گویی برسیم، درخت باید توانایی جستجوی یک گره با کلید w1/5 به بالا را در زمان ثابت ( O ( n داشته باشد. این خواسته ما با روش فشرده سازی "sketching" برآورده می شود. در این روش کلیدها به صورتی در می آید که در یک machine word جای گیرد. در واقع این روش اجازه می دهد که مقایسه ها به صورت موازی انجام گیرد. در ادامه این مقاله اجرا در یک static Fusion Tree که پاسخ گویی مطلوب را پشتیبانی می کند، توصیف می کنیم.
Sketching تابعی است که طبق آن هر کلید w بیتی منسوب به یک node شامل k تا کلید است که در k - 1 بیت فشرده شده است. هر کلید x می تواند این طور در نظر گرفته شود که یک مسیر کامل در یک درخت دودویی با ارتفاع w، از ریشه تا برگِ مطابق با x است. جهت تمایز دو مسیر کافی است به سر شاخه ها نگاه کنیم ( محل انشعاب بین دو شاخه، یعنی محل اولین بیتی که دو کلید متفاوت می شوند ) . بدیهی است که k تا مسیر در کنار هم k - 1 نقطه انشعاب دارند؛ بنابراین حداکثر k - 1 بیت نیاز است تا بتوانیم بین هر جفت از k تا کلید تمایز قائل شویم.
عکس درخت تلفیقی
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران

بپرس