درخت وب بدوی

برای مجموعه جهانی {u-۱،… ،۲،۱،۰ یک ساختار Van Emde Boas یا VEB بدوی با اعضای زیر می‌توان تعریف کرد که این ساختار نام دارد:
۱. هر ساختار حاوی یک عضو u است، که نشاندهنده اندازه مجموعه جهانی است. اگر u=2 آنگاه در سطح اولیه هستیم و ساختار حاوی یک آرایه A۰..۱ از دوبیت است. در غیر این صورت u=22k برای یک عدد صحیح k>=۱ و بنابراین u>=۴.
۲. summary که اشاره گر به ساختار است.
۳. آرایه‌ای به نام cluster که دارای تا عنصر است. که این عناصر اشاره گر به ساختار هستند.
بنابراین اطلاعات درون یک ساختار وقتی که u
V.max
۶return V.max
۷else min-low=vEB-TREE-MINIMUM(V.clusterhigh(x))
۸if min-low!= NIL and low(x)>min-low
۹offset=vEB-TREE-PREDECESSOR(V.clusterhigh(x)،high(x))
۱۰return index(high(x)،offset)
۱۱else pred-cluster=vEB-TREE-PREDECESSOR(V.summary،high(x))
۱۲if pred-cluster == NIL
۱۳if V.min!= NIL and x> V.min
۱۴return V.min
۱۵else return NIL
۱۶else offset=vEB-TREE-MAXIMUM(V.clusterpred-cluster)
۱۷return index(pred-cluster،offset)
خطوط ۱۳ تا ۱۴ حالت اضافی را تشکیل می‌دهند. این حالت وقتی رخ می‌دهد که عنصر ما قبل x (در صورت وجود) در خوشه مربوط به x قرار ندارد. در vEB-TREE-SUCCESSOR اطمینان داشتیم که اگر عنصر مابعد x بیرون خوشه مربوط به آن قرار داشته باشد، آن گاه باید در یک خوشه با شماره بالاتر باشد. ولی اگر عنصر ماقبل x مقدار کمینه در درخت V باشد، آنگاه عنصر ماقبل در هیچ خوشه‌ای نخواهد بود. خط ۱۳ این وضعیت را چک می‌کند و خط ۱۴ متناسبا مقدار کمینه را بازخواهد گرداند. اما این حالت اضافی در زمان اجرای رویه vEB-TREE-PREDECESSOR تاثیری نخواهد داشت و بنابراین vEB-TREE-PREDECESSOR در بدترین حالت در زمان اجرا می‌شود.
درج یک عنصر
در رویهPROTO-vEB-INSERT دو فراخوانی بازگشتی انجام میشد: یکی برای درج خود عنصر و یکی برای درج شماره خوشه عنصر در نماینده ساختار. رویه vEB-TREE-INSERT فقط یک فراخوانی بازگشتی انجام می‌دهد. وقتی یک عنصر را درج می‌کنیم خوشه‌ای را که این عنصر در آن قرار می‌گیرد یا عنصر دیگری دارد یا ندارد. اگر خوشه از قبل حاوی عنصر دیگری باشد، آن گاه شماره خوشه هم از قبل در نماینده قرار دارد و دیگر نیازی به فراخوانی بازگشتی نیست. اگر خوشه عنصر دیگری نداشته باشد، عنصر درج شده تنها عنصر خوشه خواهد بود و بنابراین به بازگشت برای درج یک عنصر در یک درخت vEB تهی نداریم:
vEB-EMPTY-TREE-INSERT(V،x)
۱V.min=x
۲V.max=x
با دسترسی داشتن این رویه در زیر شبه کدی برای vEB-TREE-INSERT ارائه می‌کنیم که فرض می‌کند x از قبل عنصری از مجموعه متناظر با درخت vEB نیست:
vEB-TREE-INSERT(V،x)
۱if V.min==NIL
۲vEB-EMPTY-TREE-INSERT(V،x)
۳else if x ۲
۶if vEB-TREE-MINIMUM(V.clusterhigh(x))==NIL
۷vEB-TREE-INSERT(V.summary،high(x))
۸vEB-EMPTY-TREE-INSERT(V.clusterhigh(x)،low(x))
۹else vEB-TREE-INSERT(V.clusterhigh(x)،low(x))
۱۰if x>V.max
۱۱V.max=x
این رویه به این صورت کار می‌کند که خط ۱ چک می‌کند که V یک درخت vEB تهی است یا نه و اگر تهی بود خط ۲ این حالت را حل می‌کند. خطوط ۳ تا ۱۱ فرض می‌کنند که v تهی نیست و بنابراین یک عنصر در یکی از خوشه‌های V درج می‌کنند. ولی عنصری که درج می‌شود لزوما عنصر x داده شده نیست. اگر x max خطوط ۱۰ و ۱۱ به هنگام شازی max را بر عهده خواهند داشت. در این حالت نیز زمان اجرای الگوریتم است.
حذف یک عنصر
رویه فرض می‌کند که عنصر x عضوی از مجموعه متناظر با درخت vEB دریافت شده V است.
vEB-TREE-DELETE(V،x)
۱if V.min==V.max
۲V.min = NIL
۳V.max = NIL
۴else if V.u==۲
۵if x==۰
۶V.min=۱
۷else V.min=۰
۸V.max = V.min
۹else if x==V.min
۱۰first-cluster = vEB-TREE-MINIMUM(V.summary)
۱۱x= index(first-cluster ، vEB-TREE-MINIMUM(V.clusterfirst-cluster))
۱۲V.min = x
۱۳vEB-TREE-DELETE(V.clusterhigh(x)،low(x))
۱۴if vEB-TREE-MINIMUM(V.clusterhigh(x)== NIL
۱۵vEB-TREE-DELETE(V.summary، high(x))
۱۶if x== V.max
۱۷summary-max=vEB-TREE-MAXIMUM(V.summary)
۱۸if summary-max == NIL
۱۹V.max = V.min
۲۰else V.max = index (summary-max ،vEB-TREE-MAXIMUM(V.clustersummary-max))
۲۱else if x== V.max
۲۲V.max= index (high(x)،vEB-TREE-MAXIMUM(V.clusterhigh(x)))
این الگوریتم نیز در بدترین حالت در زمان اجرا می‌شود.