درخت وب بدوی کیست؟ توضیح بده.
برای مجموعه جهانی {u-۱،... ،۲،۱،۰} یک ساختار Van Emde Boas یا VEB بدوی با اعضای زیر می‌توان تعریف کرد که این ساختار formula_1 نام دارد:۱. هر ساختار حاوی یک عضو u است، که نشاندهنده اندازه مجموعه جهانی است. اگر u=2 آنگاه در سطح اولیه هستیم و ساختار حاوی یک آرایه [A[۰..۱ از دوبیت است. در غیر این صورت u=2²ᵏ برای یک عدد صحیح k&gt;=۱ و بنابراین u&gt;=۴.۲. summary که اشاره گر به ساختارformula_2 است.۳. آرایه‌ای به نام cluster که دارای formula_3 تا عنصر است. که این عناصر اشاره گر بهformula_3 ساختار formula_2 هستند.بنابراین اطلاعات درون یک ساختار formula_2 وقتی که u&lt;=۴ حاوی اندازه مجموعه جهانی u، یک اشاره گر summary به یک ساختار formula_2 و یک آرایه[cluster[۰.. √u-۱ از formula_3 اشاره گر به ساختارهای formula_2 است. عنصر x که xPROTO-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))&lt;/pre&gt;رویه 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 عنصری از مجموعه باشد ولی فرض می‌کند ۰&lt;=x&lt;Vمانند قبل خط ۱ وجود حالت پایه را بررسی می‌کند که در خطوط ۲ تا ۴ به صورت سر راست اداره می‌شود. تنها حالتی که در آن x می‌تواند در ساختار PROTO-VEB(2) یک عنصر ما بعد داشته باشد، این است که داشته باشیم X=0 و A[1]=1 باشد. خطوط ۵ تا ۱۲ حالت بازگشتی را اداره می‌کند. خط ۵ در خوشه x به دنبال یک عنصر مابعد برای x می‌گردد و نتیجه را به متغیر offset نسبت می‌دهد. خط ۶ تعیین می‌کند که آیا xدر خوشه خود یک عنصر مابعد دارد یا نه، اگر داشت، خط ۷ آن را محاسبه کرده و مقدار عنصر مابعد را باز می‌گرداند. در غیر این صورت باید در خوشه‌های دیگر جستجو را ادامه دهیم. خط ۸ شماره خوشه نا تهی بعدی را به succ-cluster نسبت می‌دهد که برای یافتن آن از اطلاعات خلاصه استفاده شده‌است. خط ۹ چک می‌کند که succ-cluster برابر با NIL است با خیر و اگر تمام خوشه‌های دیگر تهی باشد خط ۱۰ مقدار NIL را باز می‌گرداند. اگر succ-cluster غیر NIL باشد خط ۱۱ اولین عنصر درون خوشه را به offset نسبت می‌دهد. خط ۱۲ عنصر کمینه در آن خوشه را محاسبه کرده و باز می‌گرداند. در بدترین حالت formula_19 دو بار به صورت بازگشتی بر روی proto-VEB(√u) فراخوانی می‌کند و یک فراخوانی از formula_13 بر روی یک ساختار proto-VEB(√u) انجام می‌دهد. پس رابطه بازگشتی آن در بدترین حالت به صورت روبرو توصیف می‌شود: formula_22جواب این رابطه بازگشتی formula_23 است. بنابراین این رویه به صورت حدی ازformula_13 کندتر است.درج یک عنصر(INSERT).برای درج یک عنصر باید آن را درخوشه مناسب قرار دهیم و همچنین بیت نماینده آن خوشه را برابر با ۱ بگذاریم. رویه formula_25 مقدار x را در ساختار VEB بدوی v درج می‌کند.در حالت پایه، خط ۲ بیت مناسب در آرایه A را برابر با ۱ قرار می‌دهد. در حالت بازگشتی، فراخوانی بازگشتی در خط ۳ مقدار x را در خوشه مناسب درج می‌کند و خط ۴ بیت نماینده آن خوشه را با ۱ مقدار دهی می‌کند. چون... در بدترین حالت دو فراخوانی بازگشتی انجام می‌دهد، رابطه بازگشتی... زمان اجرای آن را توصیف می‌کند. بنابراین این رویه در زمان... اجرا می‌شود.حذف یک عنصر(DELETE).در عملیات درج می‌توانستیم هنگام درج بیت نماینده را برابر با ۱ قرار دهیم اما هنگام حذف همیشه نمی‌توانیم بیت نماینده را برابر با ۰ قرار دهیم. باید تعیین کنیم که آیا یک بیت ۱ در خوشه وجود دارد یا خیر. بنابراین باید تمام formula_3 بیت دورن خوشه را بررسی کنیم تا ببینیم که آیا هیچ یک از آن‌ها ۱ هستند یا خیر. همچنین می‌توانیم یک خصیصه n عنصری به VEB اضافه کنیم که تعداد عناصر خوشه را می‌شمارد.بهبود vEB های بدوی.ساختار vEB بدوی توصیف شده دارای بازگشت‌های بیش از حد مجاز است. بنابراین در زیر ساختمان داده‌ای را توضیح می‌دهیم که کمی اطلاعات بیشتری ذخیره می‌کند تا بتواند نیاز به بعضی بازگشتها را برطرف نماید. قبلاً فرض کرده بودیم u=2²ᵏ است که اندازه مجموعه جهانی u را به عناصر یک مجموعه به شدت خلوت منحصر می‌کند. بنابراین از این به بعد اجازه می‌دهیم که اندازه مجموعه جهانی u هر توانی از ۲ باشد و وقتی formula_3 یک عدد صحیح نیست (یعنی وقتی u یک توان فرد از ۲ است)آنگاه lgu بیت یک عدد را به دو دستهformula_28 بیت پر ارزش وformula_29 بیت کم ارزش تقیسم می‌کنیم. برای سادگی ۲ به توان formula_28 را با formula_31 و ۲ به توانformula_29 را با formula_33 نشان می‌دهیم. به طوری که داریم: formula_34 و وقتی u توان زوجی از ۲ است داریم formula_35 حال توابع کمکی به صورت زیر تعریف می‌شوند:formula_36formula_37formula_38علاوه بر آن یک درخت 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 ذخیره می‌کنیم، این دو عملیات تک خطی هستند و در زمان ثابت انجام می‌شوند:تعیین وجود یک مقدار در مجموعه(MEMBER).رویه زیر حالت بازگشتی مشابه حالت بازگشتی PROTO-vEB-MEMBER دارد، ولی حالت پایه آن کمی متفاوت است. همچنین مستقیماً چک می‌کند که آیا x برابر عناصر کمینه و بیشینه‌است یا خیر. چون درخت‌های vEB بیت‌ها را مانند ساختارهای vEB ذخیره نمی‌کنند، vEB را طوری طراحی می‌کنیم که به جای ۰ و ۱ ،TRUE یاFALSE برگرداند.یافتن عنصر ما بعد(SUCCESSOR).رویه PROTO-vEB-SUCCESSOR می‌توانست دو فراخوانی انجام دهد: یکی برای تعیین وجود عنصر مابعد x در همان خوشه‌ای که x قرار دارد و اگر چنین نبود یکی هم برای یافتن خوشه حاوی عنصر مابعد x. اما از آنجاییکه می‌توانیم با زمان خطی به عنصر min ، max دسترسی داشته باشیم، می‌توانیم از انجام دو فراخوانی بازگشتی پرهیز کنیم و فقط یک فراخوانی بازگشتی بر روی یک خوشه یا روی نماینده انجام دهیم، ولی نه هر دو با هم.در خطوط ۲ تا ۴، اگر بخواهیم عنصر ما بعد ۰ را پیدا کنیم ۱ در مجموعه ۲ عنصری موجود باشد، در خط ۳ مقدار ۱ بازگردانده خواهد شد. در غیر این صورت حالت پایه در خط ۴ مقدار]] NIL بازخواهد گرداند. اگر در حالت پایه نباشیم، در خط ۵ چک می‌کنیم که اکیداً کوچکتر از عنصر کمینه هست یا نه. اگر اینطور بود، به سادگی در خط ۶ عنصر min را باز میگردانیم. اگر به خط ۷ برسیم خواهیم دانست که درحالت پایه نیستیم و x بزرگتر یا مساوی مقدار کمینه در درخت vEB داده شده V است. خط ۷ عنصر بیشینه در خوشه x را به max-low نسبت می‌دهد. اگر خوشه مربوط به x حاوی عنصری بزرگتر از x باشد، آنگاه خواهیم دانست که عنصر ما بعد x جایی در خوشه مربوط به x قرار دارد. خط ۸ وجود این حالت را چک می‌کند. اگر عنصر ما بعد x درون خوشه x باشد، آن گاه خط ۹ جای آن در خوشه را مشخص می‌کند و خط ۱۰ عنصر مابعد را مشابه خط ۷ رویه PROTO-vEB-SUCCESSOR باز می‌گرداند. اگر x بزرگتر یا مساوی بزرگترین عنصر در خوشه خود باشد، به خط ۱۱ خواهیم رسید. در این حالت خطوط ۱۱ تا ۱۵ عنصر ما بعد را مشابه خطوط ۸ تا ۱۲ رویه PROTO-vEB-SUCCESSOR پیدا خواهند کرد. در هر دو حالت خط ۹ یا خط ۱۱ تنها یک فراخوانی بازگشتی بر روی یک درخت vEB با مجموعه جهانی با اندازه حداکثر formula_39 فراخوانی می‌شود. بقیه رویه شامل فراخوانی‌های vEB-TREE-MAXIMUM vEB-TREE-MINIMUM، به زمان (O(۱ نیاز دارد. پس الگوریتم (vEB-TREE-SUCCESSOR(V،x در بدترین حالت ازformula_40 است.یافتن عنصر ما قبل.رویه vEB-TREE-PREDECESSOR(V،x) هم مانند vEB-TREE-SUCCESSOR(V،x) است اما یک حالت از آن بیشتر دارد:خطوط ۱۳ تا ۱۴ حالت اضافی را تشکیل می‌دهند. این حالت وقتی رخ می‌دهد که عنصر ما قبل x (در صورت وجود) در خوشه مربوط به x قرار ندارد. در vEB-TREE-SUCCESSOR اطمینان داشتیم که اگر عنصر مابعد x بیرون خوشه مربوط به آن قرار داشته باشد، آن گاه باید در یک خوشه با شماره بالاتر باشد. ولی اگر عنصر ماقبل x مقدار کمینه در درخت V باشد، آنگاه عنصر ماقبل در هیچ خوشه‌ای نخواهد بود. خط ۱۳ این وضعیت را چک می‌کند و خط ۱۴ متناسبا مقدار کمینه را بازخواهد گرداند. اما این حالت اضافی در زمان اجرای رویه vEB-TREE-PREDECESSOR تأثیری نخواهد داشت و بنابراین vEB-TREE-PREDECESSOR در بدترین حالت در زمانformula_40 اجرا می‌شود.درج یک عنصر.در رویهPROTO-vEB-INSERT دو فراخوانی بازگشتی انجام میشد: یکی برای درج خود عنصر و یکی برای درج شماره خوشه عنصر در نماینده ساختار. رویه vEB-TREE-INSERT فقط یک فراخوانی بازگشتی انجام می‌دهد. وقتی یک عنصر را درج می‌کنیم خوشه‌ای را که این عنصر در آن قرار می‌گیرد یا عنصر دیگری دارد یا ندارد. اگر خوشه از قبل حاوی عنصر دیگری باشد، آن گاه شماره خوشه هم از قبل در نماینده قرار دارد و دیگر نیازی به فراخوانی بازگشتی نیست. اگر خوشه عنصر دیگری نداشته باشد، عنصر درج شده تنها عنصر خوشه خواهد بود و بنابراین به بازگشت برای درج یک عنصر در یک درخت vEB تهی نداریم:با دسترسی داشتن این رویه در زیر شبه کدی برای vEB-TREE-INSERT ارائه می‌کنیم که فرض می‌کند x از قبل عنصری از مجموعه متناظر با درخت vEB نیست:این رویه به این صورت کار می‌کند که خط ۱ چک می‌کند که V یک درخت vEB تهی است یا نه و اگر تهی بود خط ۲ این حالت را حل می‌کند. خطوط ۳ تا ۱۱ فرض می‌کنند که v تهی نیست و بنابراین یک عنصر در یکی از خوشه‌های V درج می‌کنند. ولی عنصری که درج می‌شود لزوماً عنصر x داده شده نیست. اگر x&lt;min باشد (همانطور که در خط ۳ چک می‌شود) آنگاه x باید تبدیل به min شود. ولی نمی‌خواهیم عنصر min اولیه را از دست بدهیم و بنابراین باید آن را در یکی از خوشه‌های V درج کنیم. در این حالت خط ۴ را با min جابه جا می‌کند تا min اولیه را در یکی از خوشه‌های V درج کنیم. خطوط ۶ تا ۹ فقط زمانی اجرا می‌شود که V یک درخت vEB پایه نباشد. خط ۶ تعیین می‌کند که آیا خوشه‌ای که x درون آن قرار خواهد گرفت تهی است یا نه. اگر چنین بود خط ۷ شماره خوشه x را در درخت درج می‌کند و خط ۸ عملیات ساده درج x در یک مجموعه تهی را انجام می‌دهد. اگر خوشه از قبل تهی باشد آنگاه خط ۹ عنصر x را در خوشه مناسب درج می‌کند. در این حالت به هنگام سازی خلاصه ضروری نیست چرا که شماره خوشه x از قبل عضوی از خلاصه‌است. در آخر اگر داشته باشیم x&gt; max خطوط ۱۰ و ۱۱ به هنگام شازی max را بر عهده خواهند داشت. در این حالت نیز زمان اجرای الگوریتم formula_40 است.حذف یک عنصر.رویه formula_43 فرض می‌کند که عنصر x عضوی از مجموعه متناظر با درخت vEB دریافت شده V است.این الگوریتم نیز در بدترین حالت در زمان formula_44 اجرا می‌شود.