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

درخت ون امد بوآس. یک درخت 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 داده شده
برای سادگی کار، یک عدد صحیح k را در log2 m = k قرار دهید . M=2m را تعریف کنید. T یک درخت vEB بالای جهان {0, . . . , M - 1} } یک منحنی ریشه ای دارد که آرایه T. children به طول M1/2 را ذخیره می کند. [T. children[i یک اشاره گر به درخت vEB است که برای مقدارهای {iM1/2, . . . , ( i+1 ) M1/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. children[i قرار می گیرد که در آن i = ⌊ x / M 1 / 2 ⌋ . درخت کمکی T. aux نگه می دارد که کدام زیر مجموعه ها ( children ) غیر خالی هستند. پس T. aux مقدار j را شامل می شود که این فقط در صورتی است که [T. children[j غیر خالی است .