موضوع مقاله: درخت گسترده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت گسترده | مقدمه: درخت گسترده یک درخت جستجوی دودویی خود متوازن است؛ که قابلیت اصلی آن تسهیل فرایند دسترسی به اطلاعاتی است که جدیداً به آن‌ها مراجعه کرده‌ایم. | ## بخش 1: درخت گسترده | برای بسیاری از دنباله‌های غیر تصادفی، این درخت بهتر از سایر درخت‌های جستجو عمل می‌کند. در این درخت همهٔ عملیات معمول در درخت جستجوی دودویی با عمل پایه گسترش ترکیب می‌شوند. به این معنی که برای یک عنصر خاص درخت را باز می‌آراید تا عنصر در ریشهٔ درخت قرار بگیرد. یک راه انجام این کار این است که ابتدا یک جستجو برای یافتن عنصر مورد نظر انجام دهیم و سپس آن را به بالای درخت برسانیم. مزایا کارایی بهتر: کارایی بهتر برای یک درخت گسترده به خود متوازنی آن بستگی دارد و به این که عناصری که بارها دسترسی یافته‌اند به ریشه نزدیکتر شوند تا سریعتر مورد دسترسی قرار بگیرند. این تقریباً برای تمام کاربردهای عملی این ساختار مزیتی است که برای پیاده‌سازی حافظه نهان و الگوریتم بازیافت حافظه بسیار مفید است. پیاده‌سازی ساده‌تر: پیاده‌سازی ساده‌تری نسبت به دیگر درخت‌های جستجوی دودویی خود متوازن، مانند درخت قرمز سیاه یا درخت ای‌وی‌ال دارد. امکان ایجاد یک نسخه پایدار: که اجازه دسترسی به هر دو نسخه قبلی و جدید را پس از بروزرسانی می‌دهد. این می‌تواند در برنامه‌نویسی تابعی مفید باشد و به فضا در هر بروزرسانی نیاز دارد. بر خلاف سایر انواع درختان خود متوازن به خوبی با گره حاوی کلیدهای هویت کار می‌کند. | ## بخش 2: درخت گسترده | یک طراحی دقیق عملیات پیدا کردن می‌تواند چپ‌ترین یا راست‌ترین گرهٔ کلید داده شده را برگرداند. معایب درختانی می‌توانند وجود داشته باشند که توزیع دادهٔ ورودی را کمی سریع‌تر انجام می‌دهند. عملکرد ضعیف در دسترسی یکنواخت: عملکرد درخت گسترده به‌طور قابل توجهی بدتر از درخت جستجوی دودویی متعادل ساده برای دسترسی یکنواخت است. یکی از بدترین حالت‌های الگوریتم درخت گسترده دسترسی ترتیبی به همه عناصر در درخت مرتب شده‌است که درخت را کاملاً نامتعادل می‌کند (این n دسترسی دارد که هرکدام از است). دوباره مورد دسترسی قرار دادن عنصر اول، باعث می‌شود که عملیاتی که از است اجرا شود تا درخت دوباره متوازن شود (قبل بازگشت عنصر اول). این تأخیر قابل توجهی برای عملیات نهایی است، با این حال، تحقیقات اخیر نشان می‌دهد که متعادل‌سازی تصادفی می‌تواند از اثر عدم تعادل جلوگیری کند و بازدهی مشابه سایر الگوریتم‌های خود متوازن بدهد. عملیات‌های گسترش گسترش هنگامی که یک گره x مورد دسترسی قرار می‌گیرد، ساختار درختی گسترده روی آن انجام می‌شود تا آن را در ریشه قرار دهد. برای این مقصود یک توالی از مرحله‌های گسترش به‌انجام می‌رسد که هر مرحله این حرکت را بیش‌تر پیش می‌برد؛ و x را به ریشه نزدیکتر می‌کند. با انجام عملیات گسترش در گره مورد نظر بعد از هر دسترسی، گره‌ای که اخیراً مورد دسترسی قرار گرفته در نزدیکی ریشه درخت نگه داشته می‌شود و تقریباً متعادل باقی می‌ماند. هر مرحله به سه عامل بستگی دارد: آیا x فرزند چپ یا راست گره پدر خود p است، آیا گره p ریشه‌است یا نه، و اگر نه آیا گره p فرزند چپ یا راست پدر خود g است، (g پدربزرگ x می‌شود). | ## بخش 3: درخت گسترده | سه مرحله گسترش عبارتند از: مرحله زیگ این مرحله هنگامی انجام می‌گیرد که p ریشه باشد. این مرحله برای متوازن کردن درخت به‌وجود آمده‌است و تنها به عنوان آخرین مرحله، زمانی که x دارای عمق فرد در آغاز عملیات است، اجرا می‌شود. وسط مرحله زیگ-زاگ این مرحله هنگامی اجرا می‌شود که p ریشه نباشد و x فرزند راست و p فرزند چپ باشد (یا بر عکس). درخت ابتدا روی لبه بین x ,p دوران می‌کند و سپس روی لبه بین x و پدر جدیدش g دوران می‌کند. وسط مرحله زیگ-زیگ این مرحله وقتی اجرا می‌شود که p ریشه نباشد و هر دوی x و p فرزندان راست یا چپ باشند. مراحل زیگ‌-زیگ تنها چیزی است که ساختارهای درختی درهم را از روش معرفی شده از سوی آلن و مونرو متمایز می‌سازند. وسط درج برای درج گره x به درخت اسپلی، ما ابتدا آن را مانند درخت دودویی جستجوی نرمال درج می‌کنیم. اگر x دو بچه داشت، ما مقدار آن را با راست‌ترین گرهٔ زیر درخت چپ آن یا چپ‌ترین گرهٔ زیر درخت راست آن جایگزین می‌کنیم. | ## جمع‌بندی | برنامه درخت اسپلی به زبان C در برنامهٔ زیر ایده ساختن درخت اسپلی، به زبان C است: X گره‌ای است که عملیات اسپلی روی آن اجرا می‌شود و root ریشه درخت است.