درخت وب بدوی

برای مجموعه جهانی {u-۱،... ،۲،۱،۰} یک ساختار Van Emde Boas یا VEB بدوی با اعضای زیر می‌توان تعریف کرد که این ساختار $proto-VEB(u)$ نام دارد:

۱. هر ساختار حاوی یک عضو u است، که نشاندهنده اندازه مجموعه جهانی است. اگر u=2 آنگاه در سطح اولیه هستیم و ساختار حاوی یک آرایه [A[۰..۱ از دوبیت است. در غیر این صورت u=2²ᵏ برای یک عدد صحیح k>=۱ و بنابراین u>=۴.

۲. summary که اشاره گر به ساختار$proto-VEB({\sqrt {u}})$ است.

۳. آرایه‌ای به نام cluster که دارای ${\sqrt {u}}$ تا عنصر است. که این عناصر اشاره گر به${\sqrt {u}}$ ساختار $proto-VEB({\sqrt {u}})$ هستند. بنابراین اطلاعات درون یک ساختار $proto-VEB({\sqrt {u}})$ وقتی که u<=۴ حاوی اندازه مجموعه جهانی u، یک اشاره گر summary به یک ساختار $proto-VEB({\sqrt {u}})$ و یک آرایه[cluster[۰.. √u-۱ از ${\sqrt {u}}$ اشاره گر به ساختارهای $proto-VEB({\sqrt {u}})$ است. عنصر x که x<u (و بزرگتر از ۰ است) به صورت بازگشتی در عنصر شماره(low(x خوشه(به انگلیسی: Cluster) شماره(high(x ذخیره می‌شود.

اعمال بر روی یک ساختار وب بدوی

در این قسمت ابتدا اعمال پرسشی شامل: MEMBER, MINIMUM , SUCCESSOR را بررسی می‌کنیم که ساختار VEB را تغییر نمی‌دهد. سپس در مورد DELETE و INSERT بحث می‌کنیم. اعمال MAXIMUM و PREDECESSOR را که به ترتیب مشابه MINIMUM و SUCCESSOR هستند.

تعیین وجود یک مقدار در مجموعه (تابع MEMBER)

برای انجام(MEMBER(x باید یک بیت متناظر با x در ساختار(proto-VEB(2 مناسب پیدا کنیم. با صرف نظر از تمام ساختارهای summary، می‌توانیم این کار را در زمان(O(lglgu انجام دهیم. رویه زیر یک ساختار VEB بدوی V و یک مقدار x را دریافت می‌کند و یک بیت باز می‌گرداند که نشان می‌دهد آیا مقدار x در مجموعه متناظر با v موجود است یا نه.

PROTO-vEB-MEMBER(V , x)
1	if V.u==۲
2		return V.A[x]
3	else return PROTO-vEB-MEMBER(V.cluster[high(x)] , low(x))

رویه PROTO-vEB-MEMBER به صورت زیر کار می‌کند: خط ۱ تست می‌کند که آیا در حالت پایه که در آن(proto-VEB(2 است، هستیم یا نه. اگر در حالت پایه قرار داشتیم باید بیت مناسب آرایه A را برگردانیم که این کار را در خط ۲ انجام می‌دهیم. در غیر این صورت متناسبا در ساختار بدوی کوچکتری فرو می‌رویم. مقدار(high(x می‌گوید کدام ساختار$proto-VEB({\sqrt {u}})$ را ملاقات کرده‌ایم و(low(x تعیین می‌کند که هم‌اکنون بر روی کدام یک از عناصر ساختار$proto-VEB({\sqrt {u}})$ قرار داریم. برای تعیین زمان اجرای PROTO-vEB-MEMBER فرض کنید(T(u نشاندهنده زمان اجرا بر روی یک ساختار (proto-VEB(u باشد. هر فراخوانی بازگشتی به زمان ثابت نیاز دارد، البته غیر از زمان مورد نیاز برای فراخوانی بازگشتی دیگری که از طریق آن انجام می‌شود. وقتی یک PROTO-vEB-MEMBER یک فراخوانی بازگشتی انجام می‌دهد، این فراخوانی را بر روی یک ساختار $proto-VEB({\sqrt {u}})$ انجام می‌دهد. بنابراین می‌توانیم زمان اجرا را به وسیله رابطه بازگشتی:T(u)=T(√u)+O(1) توصیف کنیم که جواب این رابطه:T(u)=O(lglgu)است.

یافتن عنصر کمینه

اگر مجموعه مورد نظر تهی باشد رویه MINUMUM مقدار NIL را برمی گرداند و اگر $PROTO-VEB-MINIMUM(v)$ عنصر کمینه را در ساختار VEB بدوی باز می‌گرداند.

PROTO-VEB-MINIMUM(v)
1	if V.u==۲
2		if V.A[0]==۱
3			return 0
4		else if V.A[1]==۱
5			return 1
6		else return NIL
7	else min-cluster=PROTO-VEB-MINIMUM(V.summary)
8		if min-cluster==NIL
9			return NIL
10		else offset=PROTO-VEB-MINIMUM(v.cluster[min.cluster])
11			return index(min-cluster, offset)

این رویه به این صورت کار می‌کند. خط ۱ وجود حالت پایه را چک می‌کند، که در خطوط ۲ تا ۶ به صورت سر راست اداره می‌شود. خطوط ۷ تا ۱۱ مدیریت حالت بازگشتی را بر عهده دارند. ابتدا خط ۷ اولین خوشه‌ای را که حاوی عنصری از مجموعه‌است، پیدا می‌کند.. این کار با فراخوانی بازگشتی$PROTO-VEB-MINIMUM(v)$ بر روی V.summary انجام می‌شود، که خود یک ساختار $proto-VEB({\sqrt {u}})$ است. خط ۷ شماره خوشه را به متغیر min-cluster نسبت می‌دهد. اگر مجموعه تهی باشد، در این صورت فراخوانی بازگشتی NIL را باز میگرداند. در غیر این صورت عنصر کمینه مجموعه جایی در خوشه شماره min-cluster است. فراخوانی بازگشتی در خط شماره ۱۰ شماره عنصر کمینه در خوشه را می‌یابد. نهایتاً خط ۱۱ مقدار عنصر کمینه را از شماره خوشه و اندیس عنصر کمینه درون آن می‌سازد و این مقدار را برمیگرداند. با فرض اینکه T(u) نشاندهنده زمان اجرای بدترین حالت برای $PROTO-VEB-MINIMUM(v)$ بر روی یک ساختار $proto-VEB(u)$ باشد. رابطه بازگشتی زیر را داریم: T(u)=2T(√u)+O(1) که جواب این رابطه بازگشتی برابر: T(u)=O(lgu) پس زمان اجرای این الگوریتم در بدترین حالت O(lgu) است.

یافتن عنصر مابعد

عملیات successor حتی از MINIMUM هم بدتر است. در بدترین حالت این عملیات دو فرخوانی بازگشتی انجام می‌دهد، به همراه یک فراخوانی $PROTO-VEB-MINIMUM(v)$. رویه$PROTO-VEB-SUCCESSOR(V,x)$ کوچکترین عنصری را در ساختار VEB بدوی V باز می‌گرداند که بزرگتر از x است و Nil اگر هیچ عنصری در V از x بزرگتر نباشد. این رویه نیازی ندارد که x عنصری از مجموعه باشد ولی فرض می‌کند ۰<=x<V

PROTO-VEB-SUCCESSOR(V,x)
1	if V.u==۲
2		if x==0 and V.A[1]==۱
3			return 1
4		else return NIL
5	else offset=PROTO-VEB-SUCCESSOR(V.cluster[high(x)],low(x))	
6		if offset!= NIL
7			return index(high(x), offset)
8		else succ-cluster=PROTO-VEB-SUCCESSOR(V.summary , high(x))	
9			if succ-cluster ==NIL
10				return NIL
11			else offset=PROTO-VEB-MINIMUM(V.cluster[succ-cluster])	
12				return index(succ-cluster, offset)

مانند قبل خط ۱ وجود حالت پایه را بررسی می‌کند که در خطوط ۲ تا ۴ به صورت سر راست اداره می‌شود. تنها حالتی که در آن x می‌تواند در ساختار PROTO-VEB(2) یک عنصر ما بعد داشته باشد، این است که داشته باشیم X=0 و A[1]=1 باشد. خطوط ۵ تا ۱۲ حالت بازگشتی را اداره می‌کند. خط ۵ در خوشه x به دنبال یک عنصر مابعد برای x می‌گردد و نتیجه را به متغیر offset نسبت می‌دهد. خط ۶ تعیین می‌کند که آیا x در خوشه خود یک عنصر مابعد دارد یا نه، اگر داشت، خط ۷ آن را محاسبه کرده و مقدار عنصر مابعد را باز می‌گرداند. در غیر این صورت باید در خوشه‌های دیگر جستجو را ادامه دهیم. خط ۸ شماره خوشه نا تهی بعدی را به succ-cluster نسبت می‌دهد که برای یافتن آن از اطلاعات خلاصه استفاده شده‌است. خط ۹ چک می‌کند که succ-cluster برابر با NIL است با خیر و اگر تمام خوشه‌های دیگر تهی باشد خط ۱۰ مقدار NIL را باز می‌گرداند. اگر succ-cluster غیر NIL باشد خط ۱۱ اولین عنصر درون خوشه را به offset نسبت می‌دهد. خط ۱۲ عنصر کمینه در آن خوشه را محاسبه کرده و باز می‌گرداند. در بدترین حالت $PROTO-VEB-SUCCESSOR(V,x)$ دو بار به صورت بازگشتی بر روی proto-VEB(√u) فراخوانی می‌کند و یک فراخوانی از $PROTO-VEB-MINIMUM(v)$ بر روی یک ساختار proto-VEB(√u) انجام می‌دهد. پس رابطه بازگشتی آن در بدترین حالت به صورت روبرو توصیف می‌شود:

$T(u)=2T({\sqrt {u}})+O(lg({\sqrt {u}}))$

جواب این رابطه بازگشتی $T(u)=O(lgulglgu)$ است. بنابراین این رویه به صورت حدی از$PROTO-VEB-MINIMUM(v)$ کندتر است.

درج یک عنصر(INSERT)

برای درج یک عنصر باید آن را درخوشه مناسب قرار دهیم و همچنین بیت نماینده آن خوشه را برابر با ۱ بگذاریم. رویه $PROTO-VEB-INSERT(v)$ مقدار x را در ساختار VEB بدوی v درج می‌کند.

PROTO-VEB-INSERT(V,x)
1	if V.u==۲
2		V.A[1]=۱
3	else PROTO-VEB-INSERT(V.cluster[high(x)],x)
4		PROTO-VEB-INSERT(V.summary,high(x))

در حالت پایه، خط ۲ بیت مناسب در آرایه A را برابر با ۱ قرار می‌دهد. در حالت بازگشتی، فراخوانی بازگشتی در خط ۳ مقدار x را در خوشه مناسب درج می‌کند و خط ۴ بیت نماینده آن خوشه را با ۱ مقدار دهی می‌کند. چون.... در بدترین حالت دو فراخوانی بازگشتی انجام می‌دهد، رابطه بازگشتی... زمان اجرای آن را توصیف می‌کند. بنابراین این رویه در زمان... اجرا می‌شود.

حذف یک عنصر(DELETE)

در عملیات درج می‌توانستیم هنگام درج بیت نماینده را برابر با ۱ قرار دهیم اما هنگام حذف همیشه نمی‌توانیم بیت نماینده را برابر با ۰ قرار دهیم. باید تعیین کنیم که آیا یک بیت ۱ در خوشه وجود دارد یا خیر. بنابراین باید تمام ${\sqrt {u}}$ بیت دورن خوشه را بررسی کنیم تا ببینیم که آیا هیچ یک از آن‌ها ۱ هستند یا خیر. همچنین می‌توانیم یک خصیصه n عنصری به VEB اضافه کنیم که تعداد عناصر خوشه را می‌شمارد.

بهبود vEB های بدوی

ساختار vEB بدوی توصیف شده دارای بازگشت‌های بیش از حد مجاز است. بنابراین در زیر ساختمان داده‌ای را توضیح می‌دهیم که کمی اطلاعات بیشتری ذخیره می‌کند تا بتواند نیاز به بعضی بازگشتها را برطرف نماید. قبلاً فرض کرده بودیم u=2²ᵏ است که اندازه مجموعه جهانی u را به عناصر یک مجموعه به شدت خلوت منحصر می‌کند. بنابراین از این به بعد اجازه می‌دهیم که اندازه مجموعه جهانی u هر توانی از ۲ باشد و وقتی ${\sqrt {u}}$ یک عدد صحیح نیست (یعنی وقتی u یک توان فرد از ۲ است)آنگاه lgu بیت یک عدد را به دو دسته$\lceil (lgu)/2\rceil$ بیت پر ارزش و$\lfloor (lgu)/2\rfloor$ بیت کم ارزش تقیسم می‌کنیم. برای سادگی ۲ به توان $\lceil (lgu)/2\rceil$ را با ${\sqrt {u.up}}$ و ۲ به توان$\lfloor (lgu)/2\rfloor$ را با ${\sqrt {u.down}}$ نشان می‌دهیم. به طوری که داریم: ${\sqrt {u.up}}.{\sqrt {u.down}}=u$ و وقتی u توان زوجی از ۲ است داریم ${\sqrt {u.up}}={\sqrt {u.down}}=u$ حال توابع کمکی به صورت زیر تعریف می‌شوند:

$high(x)=\lfloor x/({\sqrt {u.down}})\rfloor$

$low(x)=xmod{\sqrt {u.down}}$

$index(x,y)=x.{\sqrt {u.down}}+y$

علاوه بر آن یک درخت VEB دو خصیصه دارد که VEB بدوی فاقد آن است:

عنصرکمینه را در درخت VEB ذخیره می‌کند.

عنصر بیشینه را در درخت VEB ذخیره می‌کند.

عنصر مینیمم در هیچ یک از درختان بازگشتی که آرایه cluster به آن‌ها اشاره می‌کند وجود نخواهد داشت. وقتی درخت vEB دارای دو عنصر یا بیشتر است، نحوه برخورد ما با min متفاوت از max خواهد بود، زیرا عنصر ذخیره شده در min در هیچ یک از خوشه‌ها وجود نخواهد داشت، ولی این مطلب در مورد عنصر ذخیره شده در max صادق نیست. دریک درخت vEB که عنصری ندارد، مستقل از اندازه مجموعه جهانی آن، هر دو مقدار min ، max را برابر NIL قرار می‌دهیم. خصیصه‌های min و max کلید، باعث کاهش تعداد فراخوانی‌های بازگشتی در اعمال درختان VEB را می‌شوند. این خصیصه‌های با ۴ طریق به ما کمک می‌کنند:

۱. اعمال MAXIMUM ، MINIMUM اصلاً نیازی به بازگشت ندارند. برای اینکه به سادگی می‌توانند مقادیر min ، max را بازگردانند.

۲. عملیات SUCCESSOR می‌تواند برای تعیین وجود عنصر مابعد x در high(x) از فراخوانی بازگشتی پرهیز کند چون عنصر مابعد یک مقدار x در خوشه مربوط به همان مقدار است. اگر و فقط اگر x اکیداً کوچکتر از max در آن خوشه باشد یک بحث مشابه در مورد PREDECESSOR و MINIMUM صادق است.

۳. با کمک دو عنصر min ، max می توانیم در زمان ثابت تعیین کنیم که یک درخت vEB هیچ عنصری ندارد، یک عنصر دارد یا حد اقل دو عنصر دارد. که از این امکان در INSERT ، DELETE استفاده می کنیم. الف.اگر min ،max هر دو NIL باشند، آنگاه درخت vEB هیچ عنصری ندارد. ب.اگر min ،max هر دو غیر NIL باشند، ولی با هم برابر باشند، آنگاه درخت vEB دقیقاً یک عنصر دارد. ج.اگر min ،max هر دو غیر NIL باشند ونامساوی، آنگاه درخت vEB دو عنصر یا بیشتر دارد.

۴. درج در درخت vEB تهی یا تک عنصری را می توانیم به سادگی به وسیله به هنگام سازی خصیصه‌های min ، max انجام دهیم.بنابراین درج در درخت تهی یا تک عنصری را می توانیم در زمان ثابت انجام دهیم.که به این ترتیب می توانیم زنجیره فراخوانی‌های بازگشتی را کوتاهتر کنیم.

اعمال بر روی یک درخت vEB

یافتن عنصر کمینه و بیشینه(MINIMUM ، MAXMIMUM)

از آنجاییکه دو عنصر کمینه و بیشینه را در خصیصه‌های min ، max ذخیره می‌کنیم، این دو عملیات تک خطی هستند و در زمان ثابت انجام می‌شوند:

VEB-TREE-MINIMUM(V)
۱	return v.min

VEB-TREE-MAXIMUM(V)
۱	return v.max

تعیین وجود یک مقدار در مجموعه(MEMBER)

رویه زیر حالت بازگشتی مشابه حالت بازگشتی PROTO-vEB-MEMBER دارد، ولی حالت پایه آن کمی متفاوت است. همچنین مستقیماً چک می‌کند که آیا x برابر عناصر کمینه و بیشینه‌است یا خیر. چون درخت‌های vEB بیت‌ها را مانند ساختارهای vEB ذخیره نمی‌کنند، vEB را طوری طراحی می‌کنیم که به جای ۰ و ۱ ،TRUE یاFALSE برگرداند.

VEB-TREE-MEMBER(V،x)
۱	if x==V.min or x==V.max
۲		return TRUE
۳	else if V.u==۲
۴		return FALSE
۵	else return VEB-TREE-MEMBER(V.cluster[high(x)]،low(x))

یافتن عنصر ما بعد(SUCCESSOR)

رویه PROTO-vEB-SUCCESSOR می‌توانست دو فراخوانی انجام دهد: یکی برای تعیین وجود عنصر مابعد x در همان خوشه‌ای که x قرار دارد و اگر چنین نبود یکی هم برای یافتن خوشه حاوی عنصر مابعد x. اما از آنجاییکه می‌توانیم با زمان خطی به عنصر min ، max دسترسی داشته باشیم، می‌توانیم از انجام دو فراخوانی بازگشتی پرهیز کنیم و فقط یک فراخوانی بازگشتی بر روی یک خوشه یا روی نماینده انجام دهیم، ولی نه هر دو با هم.

vEB-TREE-SUCCESSOR(V،x)
۱	if V.u==۲
۲		if x==۰ and V.max==۱
۳			return ۱
۴		else return NIL
۵	else if V.min!=NIL and x<V.min
۶		return V.min
۷	else max-low=vEB-TREE-MAXIMUM(V.cluster[high(x)])
۸		if max-low!= NIL and low(x) <max-low
۹			offset=vEB-TREE-SUCCESSOR(V.cluster[high(x)]،low(x))
۱۰			return index(high(x)،offset)
۱۱		else succ-cluster=vEB-TREE-SUCCESSOR(V.summary،high(x))	
۱۲			if succ-cluster == NIL
۱۳				return NIL
۱۴			else offset=vEB-TREE-MINIMUM(V.cluster[succ-cluster])
۱۵				return index(succ-cluster،offset)

در خطوط ۲ تا ۴، اگر بخواهیم عنصر ما بعد ۰ را پیدا کنیم ۱ در مجموعه ۲ عنصری موجود باشد، در خط ۳ مقدار ۱ بازگردانده خواهد شد. در غیر این صورت حالت پایه در خط ۴ مقدار]] NIL بازخواهد گرداند. اگر در حالت پایه نباشیم، در خط ۵ چک می‌کنیم که اکیداً کوچکتر از عنصر کمینه هست یا نه. اگر اینطور بود، به سادگی در خط ۶ عنصر min را باز میگردانیم. اگر به خط ۷ برسیم خواهیم دانست که درحالت پایه نیستیم و x بزرگتر یا مساوی مقدار کمینه در درخت vEB داده شده V است. خط ۷ عنصر بیشینه در خوشه x را به max-low نسبت می‌دهد. اگر خوشه مربوط به x حاوی عنصری بزرگتر از x باشد، آنگاه خواهیم دانست که عنصر ما بعد x جایی در خوشه مربوط به x قرار دارد. خط ۸ وجود این حالت را چک می‌کند. اگر عنصر ما بعد x درون خوشه x باشد، آن گاه خط ۹ جای آن در خوشه را مشخص می‌کند و خط ۱۰ عنصر مابعد را مشابه خط ۷ رویه PROTO-vEB-SUCCESSOR باز می‌گرداند. اگر x بزرگتر یا مساوی بزرگترین عنصر در خوشه خود باشد، به خط ۱۱ خواهیم رسید. در این حالت خطوط ۱۱ تا ۱۵ عنصر ما بعد را مشابه خطوط ۸ تا ۱۲ رویه PROTO-vEB-SUCCESSOR پیدا خواهند کرد. در هر دو حالت خط ۹ یا خط ۱۱ تنها یک فراخوانی بازگشتی بر روی یک درخت vEB با مجموعه جهانی با اندازه حداکثر $\lfloor {\sqrt {u.up}}\rfloor$ فراخوانی می‌شود. بقیه رویه شامل فراخوانی‌های vEB-TREE-MAXIMUM vEB-TREE-MINIMUM، به زمان (O(۱ نیاز دارد. پس الگوریتم (vEB-TREE-SUCCESSOR(V،x در بدترین حالت از$O(lglgu)$ است.

یافتن عنصر ما قبل

رویه vEB-TREE-PREDECESSOR(V،x) هم مانند vEB-TREE-SUCCESSOR(V،x) است اما یک حالت از آن بیشتر دارد:

vEB-TREE-PREDECESSOR(V،x)
۱	if V.u==۲
۲		if x==۰ and V.min==۰
۳			return ۰
۴		else return NIL
۵	else if V.max!=NIL and x>V.max
۶		return V.max
۷	else min-low=vEB-TREE-MINIMUM(V.cluster[high(x)])
۸		if min-low!= NIL and low(x)>min-low
۹			offset=vEB-TREE-PREDECESSOR(V.cluster[high(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.cluster[pred-cluster])
۱۷				return index(pred-cluster،offset)

خطوط ۱۳ تا ۱۴ حالت اضافی را تشکیل می‌دهند. این حالت وقتی رخ می‌دهد که عنصر ما قبل x (در صورت وجود) در خوشه مربوط به x قرار ندارد. در vEB-TREE-SUCCESSOR اطمینان داشتیم که اگر عنصر مابعد x بیرون خوشه مربوط به آن قرار داشته باشد، آن گاه باید در یک خوشه با شماره بالاتر باشد. ولی اگر عنصر ماقبل x مقدار کمینه در درخت V باشد، آنگاه عنصر ماقبل در هیچ خوشه‌ای نخواهد بود. خط ۱۳ این وضعیت را چک می‌کند و خط ۱۴ متناسبا مقدار کمینه را بازخواهد گرداند. اما این حالت اضافی در زمان اجرای رویه vEB-TREE-PREDECESSOR تأثیری نخواهد داشت و بنابراین vEB-TREE-PREDECESSOR در بدترین حالت در زمان$O(lglgu)$ اجرا می‌شود.

درج یک عنصر

در رویه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<V.min
4		exchange x with V.min
5		if V.u>۲
۶			if vEB-TREE-MINIMUM(V.cluster[high(x)])==NIL
۷				vEB-TREE-INSERT(V.summary،high(x))
۸				vEB-EMPTY-TREE-INSERT(V.cluster[high(x)]،low(x))
۹			else vEB-TREE-INSERT(V.cluster[high(x)]،low(x))
۱۰		if x>V.max
۱۱			V.max=x

این رویه به این صورت کار می‌کند که خط ۱ چک می‌کند که V یک درخت vEB تهی است یا نه و اگر تهی بود خط ۲ این حالت را حل می‌کند. خطوط ۳ تا ۱۱ فرض می‌کنند که v تهی نیست و بنابراین یک عنصر در یکی از خوشه‌های V درج می‌کنند. ولی عنصری که درج می‌شود لزوماً عنصر x داده شده نیست. اگر x<min باشد (همانطور که در خط ۳ چک می‌شود) آنگاه x باید تبدیل به min شود. ولی نمی‌خواهیم عنصر min اولیه را از دست بدهیم و بنابراین باید آن را در یکی از خوشه‌های V درج کنیم. در این حالت خط ۴ را با min جابه جا می‌کند تا min اولیه را در یکی از خوشه‌های V درج کنیم. خطوط ۶ تا ۹ فقط زمانی اجرا می‌شود که V یک درخت vEB پایه نباشد. خط ۶ تعیین می‌کند که آیا خوشه‌ای که x درون آن قرار خواهد گرفت تهی است یا نه. اگر چنین بود خط ۷ شماره خوشه x را در درخت درج می‌کند و خط ۸ عملیات ساده درج x در یک مجموعه تهی را انجام می‌دهد. اگر خوشه از قبل تهی باشد آنگاه خط ۹ عنصر x را در خوشه مناسب درج می‌کند. در این حالت به هنگام سازی خلاصه ضروری نیست چرا که شماره خوشه x از قبل عضوی از خلاصه‌است. در آخر اگر داشته باشیم x> max خطوط ۱۰ و ۱۱ به هنگام شازی max را بر عهده خواهند داشت. در این حالت نیز زمان اجرای الگوریتم $O(lglgu)$ است.

حذف یک عنصر

رویه $vEB-TREE-DELETE(V,x)$ فرض می‌کند که عنصر 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.cluster[first-cluster]))
۱۲		V.min = x
۱۳		vEB-TREE-DELETE(V.cluster[high(x)]،low(x))
۱۴		if vEB-TREE-MINIMUM(V.cluster[high(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.cluster[summary-max]))
۲۱	else if x== V.max
۲۲		V.max= index (high(x)،vEB-TREE-MAXIMUM(V.cluster[high(x)]))

این الگوریتم نیز در بدترین حالت در زمان $O(lglgu)$ اجرا می‌شود.

منابع

• مقدمه ای بر طراحی الگوریتم - دهقان طرزه
• کتاب طراحی الگوریتم - جعفر نژاد قمی
• کتاب ارشد طراحی الگوریتم - هادی یوسفی
• درس و کنکور طراحی الگوریتم - نوشته مهندس حمید رضا مقسمی - انتشارات گسترش علوم پایه