موضوع مقاله: درخت قربانی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت قربانی | مقدمه: برخلاف اکثر درختان جستجوی دودویی خود متعادل دیگر که برای مراجعه از (O(log n پیروی می‌کنند درختان قربانی هیچ حافظه سربار اضافی برای هر گره ندارد: یک گره تنها یک کلید و دو اشاره گر به گره‌های فرزند دارد. | ## بخش 1: درخت قربانی | این باعث می‌شود درختان قربانی با توجه به تراز ساختار داده‌ها آسان تر پیاده‌سازی شوند و می‌تواند سربار گره‌ها را تا یک سوم کاهش دهد. تئوری به یک درخت جستجوی دودویی وزن-متعادل می‌گوییم اگر نیمی از گره‌ها در سمت چپ ریشه و نیم دیگر در سمت راست آن باشند. هر چند این دو درخت تا حد زیادی در پیاده‌سازی اینکه کجا باید چرخش یا متعادل سازی دوباره رخ دهد متفاوت‌اند. در حالی که درختان سرخ-سیاه اطلاعات اضافی مانند رنگ در هر گره ذخیره می‌کنند که مکان گره را با آن تشخیص می‌دهیم، درختان قربانی یک قربانی که α-وزن-متعادل نیست را برای انجام عملیات توازن پیدا می‌کنند. این تقریباً شبیه به درختان AVL است که در آن چرخش بستگی به 'تعادل' گره‌ها دارد، اما تشخیص تعادل در این دو درخت بسیار متفاوت است. از آنجا که درختان AVL در هر بار درج و حذف مقدار تعادل درخت را بررسی می‌کنند، این مقدار معمولاً در هر گره ذخیره می‌شود؛ درختان قربانی تنها زمانی قادر به محاسبه این مقدار هستند که به آن نیاز پیدا می‌کنند، که این تنها زمانی رخ می‌دهد که بخواهیم یک قربانی پیدا کنیم. برخلاف اکثر درختان جستجوی خود متعادل دیگر درختان قربانی کاملاً برای متعادل سازی خودشان انعطاف‌پذیر هستند. یک α با مقدار نزدیک به ۱ یک توازن کمتر را نتیجه می‌دهد که درج را سریع تر ولی جستجو و حذف را کندتر می‌کند و برای αهای نزدیک ۰٫۵ بالعکس؛ بنابراین در برنامه‌های عملی یک α می‌تواند بسته به اینکه چه مقدار این عملیات‌ها باید انجام شوند انتخاب شود. عملیات‌ها درج درج کردن با همان ایده‌های اساسی یک درخت جستجوی دودویی نامتعادل پیاده‌سازی شده‌است البته با کمی تغییرات قابل توجه. این عمل از طریق یک شمارنده ساده انجام می‌گیرد که با هر پله از جستجو افزایش می‌یابد که به‌طور مؤثر تعداد یال‌های بین ریشه و محل درج گره است. | ## بخش 2: درخت قربانی | اگر این گره α-ارتفاع-تعادل (تعریف بالا) را نقض کند یک توازن دوباره مورد نیاز است. برای توازن دوباره، یک زیردرخت کامل که ریشه اش قربانی است تحت عملیات توازن دوباره قرار می‌گیرد. یکی از راه‌های پیدا کردن یک قربانی این است که از گره جدید به سمت ریشه حرکت کنیم و اولین گرهی را که α-وزن-متعادل نیست انتخاب کنیم. صعود به ریشه به (O(log n فضای ذخیره‌سازی معمولاً در پشته یا اشاره گر پدر نیاز دارد. برای تشخیص اینکه آیا یک گره بالقوه قربانی است یا نه ما نیاز به بررسی α-وزن-تعادل آن داریم. هنگامی که قربانی یافت شد، زیر درختی که ریشه در قربانی دارد به‌طور کامل بازسازی شده کاملاً متعادل است. این را می‌توان توسط پیمایش گره‌های زیردرخت برای پیدا کردن ارزش هایشان در ترتیب سورت شده و به صورت بازگشتی انتخاب میانه به عنوان ریشهٔ زیردرخت در (O(n انجام داد. همان‌طور که عملیات توازن (O(n زمان (وابسته به تعداد گره‌های زیردرخت) می‌برد، درج کردن دارای بدترین عملکرد از (O(n می‌باشد. اما از آنجا که این بدترین سناریو سرشکن می‌شود درج کردن در آنالیز استهلاکی (O(log n زمان می‌برد. طرح اثبات برای هزینه درج کردن تعادل گره v به صورت ماکس "قدر مطلق تفاوت در اندازه بین فرزند چپ و راست آن منهای ۱" یا "۰" تعریف می‌شود. | ## بخش 3: درخت قربانی | به عبارت دیگر: بلافاصله بعد از ساختن دوبارهٔ یک زیر درخت که ریشه‌اش v می‌باشد: I(v) = ۰. Lemma: دقیقاً قبل از ساختن دوباره یک زیردرخت که ریشه‌اش v می‌باشد: ( نماد O بزرگ است) اثبات lemma: اگر ریشهٔ زیردرخت بلافاصله بعد از ساختن دوباره باشد . اگر تعداد درج‌های منحط باشد (که به ازای هر درج ارتفاع گره یکی بیشتر می‌شود)، آنگاه: ، و . تا وقتی قبل از توازن دوباره، آنگاه به اندازهٔ آیتم در زیردرخت با ریشهٔ درج شده بود که به توازن دوباره منجر نشده بود. با استفاده از آنالیز استهلاکی واضح است که هزینهٔ سرشکن هر درج است: حذف درختان قربانی غیرمعمول اند از این لحاظ که حذف کردن در آن‌ها آسان تر است از درج کردن. برای اضافه کردن عملیات حذف، درختان قربانی باید یک مقدار اضافی در ساختار دادهٔ درخت ذخیره کنند. حد اکثر n/2 -1 باید به حداقل (O(n تغییر یابند، و پیچیدگی زمانی باید برای هر سطح از درخت جداگانه در نظر گرفته شود فرض کنید درخت قربانی آیتم دارد و همین الان متوازن شده‌است یعنی یک درخت دودویی کامل است. حداکثر حذف می‌تواند انجام گیرد قبل از اینکه درخت نیاز به توازن دوباره داشته باشد. با استفاده از آنالیز استهلاکی واضح است که هزینهٔ سرشکن هر حذف می‌باشد: جستجو جستجوی درخت قربانی از درخت جستجوی دودویی استاندارد گرفته نشده و دارای بدترین اوردر زمانی (O(log n می‌باشد. | ## جمع‌بندی | حافظه سربار کاهش یافتهٔ گره‌ها در درخت قربانی در مقایسه با درختان جستجوی دودویی خود-متعادل می‌تواند مکان رفرنس‌ها و ذخیره‌سازی را پیشرفت دهد.