موضوع مقاله: درخت وب بدوی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت وب بدوی | مقدمه: رویه زیر یک ساختار VEB بدوی V و یک مقدار x را دریافت می‌کند و یک بیت باز می‌گرداند که نشان می‌دهد آیا مقدار x در مجموعه متناظر با v موجود است یا نه. | ## بخش 1: درخت وب بدوی | اگر در حالت پایه قرار داشتیم باید بیت مناسب آرایه A را برگردانیم که این کار را در خط ۲ انجام می‌دهیم. مقدار(high(x می‌گوید کدام ساختار را ملاقات کرده‌ایم و(low(x تعیین می‌کند که هم‌اکنون بر روی کدام یک از عناصر ساختار قرار داریم. هر فراخوانی بازگشتی به زمان ثابت نیاز دارد، البته غیر از زمان مورد نیاز برای فراخوانی بازگشتی دیگری که از طریق آن انجام می‌شود. بنابراین می‌توانیم زمان اجرا را به وسیله رابطه بازگشتی: توصیف کنیم که جواب این رابطه:است. خط ۱ وجود حالت پایه را چک می‌کند، که در خطوط ۲ تا ۶ به صورت سر راست اداره می‌شود. نهایتاً خط ۱۱ مقدار عنصر کمینه را از شماره خوشه و اندیس عنصر کمینه درون آن می‌سازد و این مقدار را برمیگرداند. رابطه بازگشتی زیر را داریم: که جواب این رابطه بازگشتی برابر: پس زمان اجرای این الگوریتم در بدترین حالت است. در بدترین حالت این عملیات دو فرخوانی بازگشتی انجام می‌دهد، به همراه یک فراخوانی . خط ۶ تعیین می‌کند که آیا x در خوشه خود یک عنصر مابعد دارد یا نه، اگر داشت، خط ۷ آن را محاسبه کرده و مقدار عنصر مابعد را باز می‌گرداند. پس رابطه بازگشتی آن در بدترین حالت به صورت روبرو توصیف می‌شود: جواب این رابطه بازگشتی است. درج یک عنصر(INSERT) برای درج یک عنصر باید آن را درخوشه مناسب قرار دهیم و همچنین بیت نماینده آن خوشه را برابر با ۱ بگذاریم. در حالت بازگشتی، فراخوانی بازگشتی در خط ۳ مقدار x را در خوشه مناسب درج می‌کند و خط ۴ بیت نماینده آن خوشه را با ۱ مقدار دهی می‌کند. حذف یک عنصر(DELETE) در عملیات درج می‌توانستیم هنگام درج بیت نماینده را برابر با ۱ قرار دهیم اما هنگام حذف همیشه نمی‌توانیم بیت نماینده را برابر با ۰ قرار دهیم. | ## بخش 2: درخت وب بدوی | بنابراین باید تمام بیت دورن خوشه را بررسی کنیم تا ببینیم که آیا هیچ یک از آن‌ها ۱ هستند یا خیر. همچنین می‌توانیم یک خصیصه n عنصری به VEB اضافه کنیم که تعداد عناصر خوشه را می‌شمارد. بهبود vEB های بدوی ساختار vEB بدوی توصیف شده دارای بازگشت‌های بیش از حد مجاز است. بنابراین در زیر ساختمان داده‌ای را توضیح می‌دهیم که کمی اطلاعات بیشتری ذخیره می‌کند تا بتواند نیاز به بعضی بازگشتها را برطرف نماید. قبلاً فرض کرده بودیم u=2²ᵏ است که اندازه مجموعه جهانی u را به عناصر یک مجموعه به شدت خلوت منحصر می‌کند. بنابراین از این به بعد اجازه می‌دهیم که اندازه مجموعه جهانی u هر توانی از ۲ باشد و وقتی یک عدد صحیح نیست (یعنی وقتی u یک توان فرد از ۲ است)آنگاه lgu بیت یک عدد را به دو دسته بیت پر ارزش و بیت کم ارزش تقیسم می‌کنیم. به طوری که داریم: و وقتی u توان زوجی از ۲ است داریم حال توابع کمکی به صورت زیر تعریف می‌شوند: علاوه بر آن یک درخت VEB دو خصیصه دارد که VEB بدوی فاقد آن است: عنصرکمینه را در درخت VEB ذخیره می‌کند. عنصر مینیمم در هیچ یک از درختان بازگشتی که آرایه cluster به آن‌ها اشاره می‌کند وجود نخواهد داشت. وقتی درخت vEB دارای دو عنصر یا بیشتر است، نحوه برخورد ما با min متفاوت از max خواهد بود، زیرا عنصر ذخیره شده در min در هیچ یک از خوشه‌ها وجود نخواهد داشت، ولی این مطلب در مورد عنصر ذخیره شده در max صادق نیست. با کمک دو عنصر min ، max می توانیم در زمان ثابت تعیین کنیم که یک درخت vEB هیچ عنصری ندارد، یک عنصر دارد یا حد اقل دو عنصر دارد. درج در درخت vEB تهی یا تک عنصری را می توانیم به سادگی به وسیله به هنگام سازی خصیصه‌های min ، max انجام دهیم.بنابراین درج در درخت تهی یا تک عنصری را می توانیم در زمان ثابت انجام دهیم.که به این ترتیب می توانیم زنجیره فراخوانی‌های بازگشتی را کوتاهتر کنیم. اما از آنجاییکه می‌توانیم با زمان خطی به عنصر min ، max دسترسی داشته باشیم، می‌توانیم از انجام دو فراخوانی بازگشتی پرهیز کنیم و فقط یک فراخوانی بازگشتی بر روی یک خوشه یا روی نماینده انجام دهیم، ولی نه هر دو با هم. اگر در حالت پایه نباشیم، در خط ۵ چک می‌کنیم که اکیداً کوچکتر از عنصر کمینه هست یا نه. | ## بخش 3: درخت وب بدوی | اگر به خط ۷ برسیم خواهیم دانست که درحالت پایه نیستیم و x بزرگتر یا مساوی مقدار کمینه در درخت vEB داده شده V است. اگر خوشه مربوط به x حاوی عنصری بزرگتر از x باشد، آنگاه خواهیم دانست که عنصر ما بعد x جایی در خوشه مربوط به x قرار دارد. در هر دو حالت خط ۹ یا خط ۱۱ تنها یک فراخوانی بازگشتی بر روی یک درخت vEB با مجموعه جهانی با اندازه حداکثر فراخوانی می‌شود. این حالت وقتی رخ می‌دهد که عنصر ما قبل x (در صورت وجود) در خوشه مربوط به x قرار ندارد. ولی اگر عنصر ماقبل x مقدار کمینه در درخت V باشد، آنگاه عنصر ماقبل در هیچ خوشه‌ای نخواهد بود. وقتی یک عنصر را درج می‌کنیم خوشه‌ای را که این عنصر در آن قرار می‌گیرد یا عنصر دیگری دارد یا ندارد. اگر خوشه از قبل حاوی عنصر دیگری باشد، آن گاه شماره خوشه هم از قبل در نماینده قرار دارد و دیگر نیازی به فراخوانی بازگشتی نیست. خطوط ۳ تا ۱۱ فرض می‌کنند که v تهی نیست و بنابراین یک عنصر در یکی از خوشه‌های V درج می‌کنند. ولی نمی‌خواهیم عنصر min اولیه را از دست بدهیم و بنابراین باید آن را در یکی از خوشه‌های V درج کنیم. در این حالت خط ۴ را با min جابه جا می‌کند تا min اولیه را در یکی از خوشه‌های V درج کنیم. اگر چنین بود خط ۷ شماره خوشه x را در درخت درج می‌کند و خط ۸ عملیات ساده درج x در یک مجموعه تهی را انجام می‌دهد. در این حالت به هنگام سازی خلاصه ضروری نیست چرا که شماره خوشه x از قبل عضوی از خلاصه‌است. | ## جمع‌بندی | حذف یک عنصر رویه فرض می‌کند که عنصر x عضوی از مجموعه متناظر با درخت vEB دریافت شده V است.