درخت وب بدوی

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

در این قسمت ابتدا اعمال پرسشی شامل: 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)
1if V.u==۲
2return V.A[x]
3else return PROTO-vEB-MEMBER(V.cluster[high(x)] , low(x))
رویه PROTO-vEB-MEMBER به صورت زیر کار می‌کند:
خط ۱ تست می‌کند که آیا در حالت پایه که در آن(proto-VEB(2 است، هستیم یا نه. اگر در حالت پایه قرار داشتیم باید بیت مناسب آرایه A را برگردانیم که این کار را در خط ۲ انجام می‌دهیم. در غیر این صورت متناسبا در  ساختار بدوی کوچکتری فرو می‌رویم. مقدار(high(x می‌گوید کدام ساختار را ملاقات کرده‌ایم و(low(x تعیین می‌کند که هم‌اکنون بر روی کدام یک از عناصر ساختار قرار داریم. برای تعیین زمان اجرای PROTO-vEB-MEMBER فرض کنید(T(u نشاندهنده زمان اجرا بر روی یک ساختار (proto-VEB(u  باشد. هر فراخوانی بازگشتی به زمان ثابت نیاز دارد، البته غیر از زمان مورد نیاز برای فراخوانی بازگشتی دیگری که از طریق آن انجام می‌شود. وقتی یک PROTO-vEB-MEMBER یک فراخوانی بازگشتی انجام می‌دهد، این فراخوانی را بر روی یک ساختار  انجام می‌دهد. بنابراین می‌توانیم زمان اجرا را به وسیله رابطه بازگشتی:T(u)=T(√u)+O(1) توصیف کنیم که جواب این رابطه:T(u)=O(lglgu)است.

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

اگر مجموعه مورد نظر تهی باشد رویه MINUMUM  مقدار NIL را برمی گرداند و اگر    عنصر کمینه را در ساختار VEB بدوی باز می‌گرداند.
PROTO-VEB-MINIMUM(v)
1if V.u==۲
2if V.A[0]==۱
3return 0
4else if V.A[1]==۱
5return 1
6else return NIL
7else min-cluster=PROTO-VEB-MINIMUM(V.summary)
8if min-cluster==NIL
9return NIL
10else offset=PROTO-VEB-MINIMUM(v.cluster[min.cluster])
11return index(min-cluster, offset)
این رویه به این صورت کار می‌کند. خط ۱ وجود حالت پایه را چک می‌کند، که در خطوط ۲ تا ۶ به صورت سر راست اداره می‌شود. خطوط ۷ تا ۱۱ مدیریت حالت بازگشتی را بر عهده دارند. ابتدا خط ۷ اولین خوشه‌ای را که حاوی عنصری از مجموعه‌است، پیدا می‌کند.. این کار با فراخوانی بازگشتی بر روی V.summary انجام می‌شود، که خود یک ساختار  است. خط ۷ شماره خوشه را به متغیر min-cluster نسبت می‌دهد. اگر مجموعه تهی باشد، در این صورت فراخوانی بازگشتی NIL را باز میگرداند. در غیر این صورت عنصر کمینه مجموعه جایی در خوشه شماره min-cluster است. فراخوانی بازگشتی در خط شماره ۱۰ شماره عنصر کمینه در خوشه را می‌یابد. نهایتاً خط ۱۱ مقدار عنصر کمینه را از شماره خوشه و اندیس عنصر کمینه درون آن می‌سازد و این مقدار را برمیگرداند. با فرض اینکه T(u) نشاندهنده زمان اجرای بدترین حالت برای   بر روی یک ساختار  باشد. رابطه بازگشتی زیر را داریم:
T(u)=2T(√u)+O(1) که جواب این رابطه بازگشتی برابر: T(u)=O(lgu) پس زمان اجرای این الگوریتم در بدترین حالت  O(lgu) است.

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

عملیات successor حتی از MINIMUM هم بدتر است. در بدترین حالت این عملیات دو فرخوانی بازگشتی انجام می‌دهد، به همراه یک فراخوانی . رویه کوچکترین عنصری را در ساختار VEB بدوی V باز می‌گرداند که بزرگتر از x است و Nil اگر هیچ عنصری در V از x بزرگتر نباشد. این رویه نیازی ندارد که x عنصری از مجموعه باشد ولی فرض می‌کند ۰<=x<V
PROTO-VEB-SUCCESSOR(V,x)
1if V.u==۲
2if x==0 and V.A[1]==۱
3return 1
4else return NIL
5else offset=PROTO-VEB-SUCCESSOR(V.cluster[high(x)],low(x))
6if offset!= NIL
7return index(high(x), offset)
8else succ-cluster=PROTO-VEB-SUCCESSOR(V.summary , high(x))
9if succ-cluster ==NIL
10return NIL
11else offset=PROTO-VEB-MINIMUM(V.cluster[succ-cluster])
12return 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(√u) فراخوانی می‌کند و یک فراخوانی از  بر روی یک ساختار proto-VEB(√u) انجام می‌دهد. پس رابطه بازگشتی آن در بدترین حالت به صورت روبرو توصیف می‌شود: 
جواب این رابطه بازگشتی   است. بنابراین این رویه به صورت حدی از کندتر است.

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

برای درج یک عنصر باید آن را  درخوشه مناسب قرار دهیم و همچنین بیت نماینده آن خوشه را برابر با ۱ بگذاریم. رویه       مقدار x را در ساختار VEB بدوی v درج می‌کند.
PROTO-VEB-INSERT(V,x)
1if V.u==۲
2V.A[1]=۱
3else PROTO-VEB-INSERT(V.cluster[high(x)],x)
4PROTO-VEB-INSERT(V.summary,high(x))
در حالت پایه، خط ۲ بیت مناسب در آرایه A را برابر با ۱ قرار می‌دهد. در حالت بازگشتی، فراخوانی بازگشتی در خط ۳ مقدار x را در خوشه مناسب درج می‌کند و خط ۴ بیت نماینده آن خوشه را با ۱ مقدار دهی می‌کند. چون.... در بدترین حالت دو فراخوانی بازگشتی انجام می‌دهد، رابطه بازگشتی... زمان اجرای آن را توصیف می‌کند. بنابراین این رویه در زمان... اجرا می‌شود.

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

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

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

ساختار vEB بدوی توصیف شده دارای بازگشت‌های بیش از حد مجاز است. بنابراین در زیر ساختمان داده‌ای را توضیح می‌دهیم که کمی اطلاعات بیشتری ذخیره می‌کند تا بتواند نیاز به بعضی بازگشتها را برطرف نماید. قبلاً فرض کرده بودیم u=2²ᵏ است که اندازه مجموعه جهانی u را به عناصر یک مجموعه به شدت خلوت منحصر می‌کند. بنابراین از این به بعد اجازه می‌دهیم که اندازه مجموعه جهانی u هر توانی از ۲ باشد و وقتی   یک عدد صحیح نیست (یعنی وقتی u یک توان فرد از ۲ است)آنگاه lgu بیت یک عدد را به دو دسته بیت پر ارزش و بیت کم ارزش تقیسم می‌کنیم. برای سادگی ۲ به توان  را با   و ۲ به توان  را با  نشان می‌دهیم. به طوری که داریم:  و وقتی u  توان زوجی از ۲ است داریم  حال توابع کمکی به صورت زیر تعریف می‌شوند:
علاوه بر آن یک درخت 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 انجام دهیم.بنابراین درج در درخت تهی یا تک عنصری را می توانیم در زمان ثابت انجام دهیم.که به این ترتیب می توانیم زنجیره فراخوانی‌های بازگشتی را کوتاهتر کنیم.

یافتن عنصر کمینه و بیشینه(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 با مجموعه جهانی با اندازه حداکثر  فراخوانی می‌شود. بقیه رویه شامل فراخوانی‌های vEB-TREE-MAXIMUM vEB-TREE-MINIMUM، به زمان (O(۱ نیاز دارد. پس الگوریتم (vEB-TREE-SUCCESSOR(V،x در بدترین حالت از است.

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

رویه 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 در بدترین حالت در زمان اجرا می‌شود.

درج یک عنصر

در رویه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
4exchange x with V.min
5if 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 را بر عهده خواهند داشت. در این حالت نیز زمان اجرای الگوریتم  است.

حذف یک عنصر

رویه  فرض می‌کند که عنصر 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)]))
این الگوریتم نیز در بدترین حالت در زمان  اجرا می‌شود.