درخت وب بدوی
برای مجموعه جهانی {u-۱،... ،۲،۱،۰} یک ساختار Van Emde Boas یا VEB بدوی با اعضای زیر می‌توان تعریف کرد که این ساختار formula_1 نام دارد:
۱. هر ساختار حاوی یک عضو u است، که نشاندهنده اندازه مجموعه جهانی است. اگر u=2 آنگاه در سطح اولیه هستیم و ساختار حاوی یک آرایه [A[۰..۱ از دوبیت است. در غیر این صورت u=2²ᵏ برای یک عدد صحیح k>=۱ و بنابراین u>=۴.
۲. summary که اشاره گر به ساختارformula_2 است.
۳. آرایه‌ای به نام cluster که دارای formula_3 تا عنصر است. که این عناصر اشاره گر بهformula_3 ساختار formula_2 هستند. بنابراین اطلاعات درون یک ساختار formula_2 وقتی که u<=۴ حاوی اندازه مجموعه جهانی u، یک اشاره گر summary به یک ساختار formula_2 و یک آرایه[cluster[۰.. √u-۱ از formula_3 اشاره گر به ساختارهای formula_2 است. عنصر x که xبازگشتی در عنصر شماره(low(x خوشه شماره(high(x ذخیره می‌شود.
در این قسمت ابتدا اعمال پرسشی شامل: MEMBER, MINIMUM , SUCCESSOR را بررسی می‌کنیم که ساختار VEB را تغییر نمی‌دهد. سپس در مورد DELETE و INSERT بحث می‌کنیم. اعمال MAXIMUM و PREDECESSOR را که به ترتیب مشابه MINIMUM و SUCCESSOR هستند.
برای انجام(MEMBER(x باید یک بیت متناظر با x در ساختار(proto-VEB(2 مناسب پیدا کنیم. با صرف نظر از تمام ساختارهای summary، می‌توانیم این کار را در زمان(O(lglgu انجام دهیم. رویه زیر یک ساختار VEB بدوی V و یک مقدار x را دریافت می‌کند و یک بیت باز می‌گرداند که نشان می‌دهد آیا مقدار x در مجموعه متناظر با v موجود است یا نه.
رویه PROTO-vEB-MEMBER به صورت زیر کار می‌کند: خط ۱ تست می‌کند که آیا در حالت پایه که در آن(proto-VEB(2 است، هستیم یا نه. اگر در حالت پایه قرار داشتیم باید بیت مناسب آرایه A را برگردانیم که این کار را در خط ۲ انجام می‌دهیم. در غیر این صورت متناسبا در ساختار بدوی کوچکتری فرو می‌رویم. مقدار(high(x می‌گوید کدام ساختارformula_2 را ملاقات کرده‌ایم و(low(x تعیین می‌کند که هم‌اکنون بر روی کدام یک از عناصر ساختارformula_2 قرار داریم. برای تعیین زمان اجرای PROTO-vEB-MEMBER فرض کنید(T(u نشاندهنده زمان اجرا بر روی یک ساختار (proto-VEB(u باشد. هر فراخوانی بازگشتی به زمان ثابت نیاز دارد، البته غیر از زمان مورد نیاز برای فراخوانی بازگشتی دیگری که از طریق آن انجام می‌شود. وقتی یک PROTO-vEB-MEMBER یک فراخوانی بازگشتی انجام می‌دهد، این فراخوانی را بر روی یک ساختار formula_2 انجام می‌دهد. بنابراین می‌توانیم زمان اجرا را به وسیله رابطه بازگشتی:' توصیف کنیم که جواب این رابطه:'است.
اگر مجموعه مورد نظر تهی باشد رویه MINUMUM مقدار NIL را برمی گرداند و اگر formula_13 عنصر کمینه را در ساختار VEB بدوی باز می‌گرداند.
این رویه به این صورت کار می‌کند. خط ۱ وجود حالت پایه را چک می‌کند، که در خطوط ۲ تا ۶ به صورت سر راست اداره می‌شود. خطوط ۷ تا ۱۱ مدیریت حالت بازگشتی را بر عهده دارند. ابتدا خط ۷ اولین خوشه‌ای را که حاوی عنصری از مجموعه‌است، پیدا می‌کند.. این کار با فراخوانی بازگشتیformula_13 بر روی V.summary انجام می‌شود، که خود یک ساختار formula_2 است. خط ۷ شماره خوشه را به متغیر min-cluster نسبت می‌دهد. اگر مجموعه تهی باشد، در این صورت فراخوانی بازگشتی NIL را باز میگرداند. در غیر این صورت عنصر کمینه مجموعه جایی در خوشه شماره min-cluster است. فراخوانی بازگشتی در خط شماره ۱۰ شماره عنصر کمینه در خوشه را می‌یابد. نهایتاً خط ۱۱ مقدار عنصر کمینه را از شماره خوشه و اندیس عنصر کمینه درون آن می‌سازد و این مقدار را برمیگرداند. با فرض اینکه T(u) نشاندهنده زمان اجرای بدترین حالت برای formula_13 بر روی یک ساختار formula_1 باشد. رابطه بازگشتی زیر را داریم:
عملیات successor حتی از MINIMUM هم بدتر است. در بدترین حالت این عملیات دو فرخوانی بازگشتی انجام می‌دهد، به همراه یک فراخوانی formula_13. رویهformula_19 کوچکترین عنصری را در ساختار VEB بدوی V باز می‌گرداند که بزرگتر از x است و Nil اگر هیچ عنصری در V از x بزرگتر نباشد. این رویه نیازی ندارد که x عنصری از مجموعه باشد ولی فرض می‌کند ۰<=x max خطوط ۱۰ و ۱۱ به هنگام شازی max را بر عهده خواهند داشت. در این حالت نیز زمان اجرای الگوریتم formula_40 است.
رویه formula_43 فرض می‌کند که عنصر x عضوی از مجموعه متناظر با درخت vEB دریافت شده V است.
این الگوریتم نیز در بدترین حالت در زمان formula_44 اجرا می‌شود.