درخت ون امد بوآس

درخت van Emde Boas
گونه
Non-binary tree(درخت غیر دوتایی)
اختراع
1977
مخترع
Peter van Emde Boas
پیچیدگی سیستماتیکدر نماد O بزرگ
مساحت
(O(M
جستجو
(O(log log M
درج
(O(log log M
حذف
(O(log log M
یک درخت van Emde Boas (یا صف اولویت van Emde Boas ) که به اسم درخت vEB نیز خوانده می‌شود، یک درخت ساختار داده است که یک آرایه شرکت پذیر را با m بیت کلیدهای عدد صحیح پیاده‌سازی می‌کند.زمان اجرای این عملیات (O(log m می‌باشد، توجه داشته باشید که m اندازه کلیدها می‌باشد، بنابراین ( O ( Log m در یک درختی که در آن هر کلیدی زیر n مجموعه قرار دارد برابر (O(log n است، به صورت نمایی، این بهتر از یک درخت جستجوی دوتایی خود متعادل می‌باشد. همانطور که در زیر بیان شده، در زمانی که آن‌ها تعداد عناصر زیادی را شامل می‌شوند، بازده مساحتی خوبی دارند. . آن‌ها توسط یک تیم به رهبری پیتر ون امدبوس( Peter van Emde Boas ) در 1997 اختراع شدند.
عملیاتهای پشتیانی شده
عملیاتی که با درخت vEB پشتیبانی می‌شوند آنهایی هستند که آرایه شرکت پذیر مرتب شده دارند که شامل عملیات شرکت پذیر منظم معمولی به همراه دو عملیات منظم دیگر، یافتن بعدی و یافتن قبلی می‌شود:
درج کردن : یک کلید وارد کنید / مقدار به همراه یک کلید عدد m
حذف کردن : کلید را حذف کنید / مقدار به همراه یک کلید داده شده
جستجو : مقدار را با توجه به کلید داده شده پیدا کنید
یافتن بعدی : کلید را پیدا کنید / مقدار به همراه کوچکترین کلید حداقل یک k داده شده
یافتن قبلی : کلید را پیدا کنید / مقدار به همراه بزرگترین کلید حداکثر یک k داده شده
چگونگی عملیات
یک نمونه از درخت vEB با پنج بعد و ساختار کمکی ریشه بعد از اینکه 10 و 1,2,3,5,8 درج شده‌اند..
برای سادگی کار، یک عدد صحیح k را در log 2 m = k قرار دهید . M=2 m را تعریف کنید.
T یک درخت vEB بالای جهان {0,…,M-1 یک منحنی ریشه‌ای دارد که آرایه T.children به طول M 1/2 را ذخیره می‌کند. T.childreni یک اشاره گر به درخت vEB است که برای مقدارهای {iM 1/2 ,…,(i+1)M 1/2 -1 مسئول است. به علاوه ، T دو مقدار T.min و T.max را به همراه یک درخت vEB کمکی، T.aux، ذخیره می‌کند.
اطلاعات در یک درخت vEB به گونه زیر ذخیره شده‌است :
کوچکترین مقدار موجود در درخت در T.min و بزرگترین مقدار در T.max ذخیره می‌شوند. این دو مقدار در هیچ جای دیگر درخت vEB ذخیره نمی‌شود. اگر T خالی است پس ما از قاعده T.max=-1 و T.min=M استفاده می‌کنیم . هر مقدار x دیگر در زیر درخت T.childreni قرار می‌گیرد که در آن . درخت کمکی T.aux نگه می‌دارد که کدام زیر مجموعه‌ها (children) غیر خالی هستند. پس T.aux مقدار j را شامل می‌شود که این فقط در صورتی است که T.childrenj غیر خالی است .
یافتن بعدی
عملیات یافتن بعدی (FindNext(T, x که به دنبال یک جانشین برای یک عنصر x در یک درخت vEB می‌باشد این‌گونه پیش می‌رود : اگر x≤T.min باشد پس جستجو کامل است، و پاسخ T.min است . اگر x>T.max باشد آنوقت عنصر بعدی وجود ندارد ، M را برمی‌گرداند . در غیراینصورت ، i=x/M 1/2 . اگر x≤T.childreni.max باشد، پس مقداری که دنبالش می‌گردید در T.childreni است پس جستجو به حالت بازگشتی در T.childreni ادامه پیدا می‌کند. در غیراینصورت، ما به دنبال مقدار i در T.aux می‌گردیم . این به ما شاخص j را از اولین زیردرخت می‌دهد که شامل یک عنصر بزرگتر از x می‌باشد. الگوریتم سپس به T.childrenj.min بر می‌گردد. عنصر یافت شده در مقطع children نیاز دارد با ارقام بالا ترکیب شود تا یک عنصر کامل بعدی را تشکیل دهد.
FindNext(T, x)
if (x T.max) //no next element
return M
i = floor(x/sqrt(M))
lo = x % sqrt(M)
hi = x - lo
if (lo
T.max باشد، ما T.max را در زیردرخت i که مربوط به T.max است قرار می‌دهیم و سپس T.max = x می‌شود . اگر T.childreni قبلا خالی بوده، پس ما همچنین i را در T.aux قرار می‌دهیم.
در غیر اینصورت، اگر T.min
T.max) // T is empty
T.min = T.max = x;
return
if (T.min = T.max)
if (x T.max)
T.max = x;
return
if (x T.max)
swap(x, T.max)
i = x/sqrt(M)
Insert(T.childreni, x % sqrt(M))
if (T.childreni.min = T.childreni.max)
Insert(T.aux, i)
بهترین راه برای بازدهی این عملیات این است که درج کردن یک عنصر در یک درخت vEB خالی حدود (O(1 زمان ببرد . بنابراین اگرچه بعضی اوقات الگوریتم دو فراخوان بازگشتی دارد، این فقط در زمانی رخ می‌دهد که اولین فراخوان بازگشتی در یک زیردرخت خالی باشد. درست مثل قبل، این عملیات بازگشتی در زمان (T(m)=T(m/2) + O(1 انجام می‌شود .
حذف کردن
حذف از درخت VEB بیشترین مهارت را در میان عملیاتها نیاز دارد. فراخوان (Delete(T, x که یک مقدار x را از درخت (vEB (T حذف می‌کند، همانند زیر عمل می‌کند :
اگر T.min = T.max = x باشد سپس x تنها عنصری است که در درخت ذخیره شده‌است و ما T.min = M و T.max = -1 تا نشان دهیم درخت خالی است .
در غیر اینصورت، اگر x = T.min پس ما نیاز داریم دومین کمترین مقدار y را در درخت vEB پیدا کنیم، آن را از جای فعلیش حذف کنیم و آن وقت T.min=y . دومین کمترین مقدار y یا T.max است یا T.children .min . پس این می‌تواند در زمان (O(1 پیدا شود . در شرایط بعدی، ما y را از زیر درختی که او را در خود جای داده حذف می‌کنیم .
به‌طور مشابه، اگر x = T.max باشد، ما باید دومین بزرگترین مقدار y را در درخت vEB پیدا کنیم، آن را از جایگاهش حذف کنیم و آن وقت T.max=y می‌شود . دومین بزرگترین مقدار y یا T.min است یا T.children .max . پس این می‌تواند در زمان (O(1 پیدا شود . در شرایط بعدی، ما y را از زیر درختی که او را در خود جای داده حذف می‌کنیم .
در شرایطی که T.min ، x یا T.max نیست و T هیچ عنصر دیگری ندارد ما می‌دانیم که x در T نیست و بدون هیچ عملیاتی برمی گردیم.
در غیر اینصورت ما شرایط معمولی را داریم که در آن x≠T.min و x≠T.max است . در این موقع، ما x را از زیر درخت T.childreni که شامل x است، حذف می‌کنیم .
در هر کدام از شرایط فوق، اگر ما آخرین عنصر x یا y را از هر زیر درخت T.childreni حذف کنیم، آنگاه ما i را از T.aux حذف می‌کنیم .
در کد :
Delete(T, x)
if (T.min T.max x)
T.min = M
T.max = -1
return
if (x == T.min)
if (T.aux is empty)
T.min = T.max
return
else
x = T.children .min
T.min = x
if (x == T.max)
if (T.aux is empty)
T.max = T.min
return
else
x = T.children .max
T.max = x
if (T.aux is empty)
return
i = floor(x/sqrt(M))
Delete(T.childreni, x%sqrt(M))
if (T.childreni is empty)
Delete(T.aux, i)
و دوباره اینکه، بازدهی این عملیات وابسته به این حقیقت است که حذف از یک درخت vEB که تنها یک عنصر دارد فقط زمان مشخصی می‌برد . خصوصا، آخرین خط قانون فقط در حالتی اجرا می‌شود که x تنها عنصر در T.childreni قبل از عملیات حذف بوده باشد .
بحث
این تفکر که log m یک عدد صحیح است غیرضروری است . اگر عملیات (x/sqrt(m و (x%sqrt(m با تنها گرفتن ترتیب بالاتر از سقف (m/2) و ترتیب پایین‌تر از کف (m/2) ارقام x به ترتیب می‌توانند جایگزین شوند. در هر ماشین موجود این نسبت به تقسیم و محاسبات باقی‌مانده کارآمد‌تر است .
انجام عملیاتی که در بالا توضیح داده شد از اشاره گرها استفاده می‌کند و یک مساحت کلی را اشغال می‌کند . این می‌تواند این‌گونه دیده شود که عملیات بازگشت این‌گونه است .
حل آن به این ختم می‌شود : .
خوشبختانه با استنتاج ( قیاس کل از جز) می‌توان را ثابت کرد .
در اجراهای کاربردی، به خصوص در ماشین‌هایی که دستورالعمل‌های Find First zero و shift-by-k دارند، عملکرد می‌تواند با یک بار تغییر به یک آرایه رقمی m برابر با اندازه کلمه ( یا یک چند رقمی کوچک) خیلی پیشرفت کند . از آنجایی که همه عملیاتهایی که به روی یک تک کلمه هستند زمان مشخصی می‌برند، این عملکرد اسیمپاتیک (asymptotic ) را تحت تاثیر قرار نمی‌دهد، اما با وجود حفظ کاربردی و مهم زمان و فضا در این مهارت مانع ذخیره اکثر اشاره گرها و ارجاع تعدادی اشاره گر می‌شود.
یک بخش واضح و مثبت درختهای vEB دور انداختن درختهای زیر مجموعه خالی است . این درختهای vEB را در زمانی که خیلی عنصر دارند فشرده می‌کنند چون هیچ درخت زیر مجموعه‌ای به وجود نمی‌آید مگر اینکه چیزی باید به آن‌ها اضافه شود. در ابتدا، هر عنصر اضافه شده حدود (Log(m تا درخت جدید خلق می‌کند که با هم در حدود m/2 اشاره گر دارند. هم‌زمان با اینکه درخت بزرگ می‌شود، زیر درختهای بیشتری دوباره استفاده می‌شوند، به خصوص آنهایی که بزرکتر هستند . در یک درخت کامل با 2m عنصر، فقط مساحت (O(2m استفاده می‌شود و اینکه بر خلاف درخت جستجوی دوتایی بیشتر این مساحت برای ذخیره اطلاعات استفاده می‌شود : حتی برای میلیون‌ها عنصر و هزاران اشاره گر در یک درخت کامل vEB .
در حالی که برای درختهای کوچک بالاسری که به درختهای vEB مربوط است خیلی عظیم است : در ترتیب 2m/2 . به همین دلیل است که آن‌ها در عمل خیلی محبوب نیستند . یک راه مقابله با این محدودیت استفاده از تعداد مشخصی از ارقام در هر مقطع است . ساختارهای دیگر که شامل آزمایشهای y-fast و x-fast می‌شوند نیز پیشنهاد شده‌اند که زمان‌های تحقیق به روزتری دارند، اما فقط از فضای (O(n Log M یا (O(n استفاده می‌کنند که در آن‌ها n تعداد عناصری است که در ساختار اطلاعاتی ذخیره شده‌است .