درخت قربانی
در علوم رایانه یک درخت قربانی (یا درخت بز طلیعه) یک توازن درخت جستجوی دودویی است که توسط آرن اندرسون و دوباره توسط Igal Galperin و Ronald L. Rivest. اختراع شده. این درخت برای پیدا کردن از (O(log n و برای درج و حذف از آنالیز استهلاکی (O(log n پیروی می‌کند.
بر خلاف اکثر درختان جستجوی دودویی خود متعادل دیگر که برای مراجعه از (O(log n پیروی می‌کنند درختان قربانی هیچ حافظه سربار اضافی برای هر گره ندارد: یک گره تنها یک کلید و دو اشاره گر به گره‌های فرزند دارد. این باعث می‌شود درختان قربانی با توجه به تراز ساختار داده‌ها آسان تر پیاده‌سازی شوند و می‌تواند سربار گره‌ها را تا یک سوم کاهش دهد.
به یک درخت جستجوی دودویی وزن-متعادل می‌گوییم اگر نیمی از گره‌ها در سمت چپ ریشه و نیم دیگر در سمت راست آن باشند. یک گره α-وزن-متعادل با معیار تعادل وزنی زیر تعریف می‌شود:
که در آن اندازه را می‌توان به صورت بازگشتی مانند زیر تعریف کرد:
وقتی α برابر ۱ باشد توصیف یک لینک لیست متعادل را خواهیم داشت در حالی که با α برابر ۰٫۵ تقریباً یک درخت دودویی کامل داریم.
یک درخت جستجوی دودویی که α-وزن-متعادل است α-ارتفاع-متعادل نیز باید باشد، که:
درختان قربانی تضمین نمی‌کنند که α-وزن-تعادل در همه زمان‌ها نگه داشته شود اما همیشه تقریباً α-ارتفاع-متعادل می‌باشند :
این باعث می‌شود درختان قربانی شبیه به درختان سرخ-سیاه شوند که در هر دوی اینها دارای محدودیت در ارتفاع درخت هستیم. هر چند این دو درخت تا حد زیادی در پیاده‌سازی اینکه کجا باید چرخش یا متعادل سازی دوباره رخ دهد متفاوت‌اند. در حالی که درختان سرخ-سیاه اطلاعات اضافی مانند رنگ در هر گره ذخیره می‌کنند که مکان گره را با آن تشخیص می‌دهیم، درختان قربانی یک قربانی که α-وزن-متعادل نیست را برای انجام عملیات توازن پیدا می‌کنند. این تقریباً شبیه به درختان AVL است که در آن چرخش بستگی به 'تعادل' گره‌ها دارد، اما تشخیص تعادل در این دو درخت بسیار متفاوت است. از آنجا که درختان AVL در هر بار درج و حذف مقدار تعادل درخت را بررسی می‌کنند، این مقدار معمولاً در هر گره ذخیره می‌شود؛ درختان قربانی تنها زمانی قادر به محاسبه این مقدار هستند که به آن نیاز پیدا می‌کنند، که این تنها زمانی رخ می‌دهد که بخواهیم یک قربانی پیدا کنیم.
بر خلاف اکثر درختان جستجوی خود متعادل دیگر درختان قربانی کاملاً برای متعادل سازی خودشان انعطاف‌پذیر هستند. آن‌ها از هر α به‌طوری‌که α بین 0.5 و 1 است پیروی می‌کنند. یک α با مقدار نزدیک به ۱ یک توازن کمتر را نتیجه می‌دهد که درج را سریع تر ولی جستجو و حذف را کندتر می‌کند و برای αهای نزدیک ۰٫۵ بالعکس؛ بنابراین در برنامه‌های عملی یک α می‌تواند بسته به اینکه چه مقدار این عملیات‌ها باید انجام شوند انتخاب شود.
درج کردن با همان ایده‌های اساسی یک درخت جستجوی دودویی نامتعادل پیاده‌سازی شده‌است البته با کمی تغییرات قابل توجه.
هنگام پیدا کردن نقطه درج عمق گره جدید نیز باید ثبت شود. این عمل از طریق یک شمارنده ساده انجام می‌گیرد که با هر پله از جستجو افزایش می‌یابد که به‌طور مؤثر تعداد یال‌های بین ریشه و محل درج گره است. اگر این گره α-ارتفاع-تعادل (تعریف بالا) را نقض کند یک توازن دوباره مورد نیاز است.
برای توازن دوباره، یک زیردرخت کامل که ریشه اش قربانی است تحت عملیات توازن دوباره قرار می‌گیرد. قربانی تعریف شده‌است به عنوان جد یک گره درج شده که α-وزن متعادل نیست. همیشه یک جد اینچنینی وجود خواهد داشت. ایجاد توازن دوباره در هر یک از آن‌ها ویژگی α-ارتفاع-تعادل را بازیابی خواهد کرد.
یکی از راه‌های پیدا کردن یک قربانی این است که از گره جدید به سمت ریشه حرکت کنیم و اولین گرهی را که α-وزن-متعادل نیست انتخاب کنیم.
صعود به ریشه به "(O(log n" فضای ذخیره‌سازی معمولاً در پشته یا اشاره گر پدر نیاز دارد. در واقع این می‌تواند با داشتن اشاره گر به پدر در هر فرزند اجتناب شود.
برای تشخیص اینکه آیا یک گره بالقوه قربانی است یا نه ما نیاز به بررسی α-وزن-تعادل آن داریم. برای انجام این کار ما می‌توانیم به تعریف آن برگردیم:
اما بهینه‌سازی بزرگی می‌تواند انجام شود با توجه به این که ما در حال حاضر دو تا از سه اندازه را می‌دانیم و فقط سومی نیاز به محاسبه شدن دارد.
برای نشان دادن این موضوع مثال زیر را در نظر بگیرید. فرض کنید که ما در حال بازگشت به ریشه باشیم:
اما:
این مورد بی‌اهمیت دانسته شده:
که در آن x = این گره x + 1 = پدر و (size(sibling تنها فراخوانی تابع مورد نیاز است.
هنگامی که قربانی یافت شد، زیردرختی که ریشه در قربانی دارد به‌طور کامل بازسازی شده کاملاً متعادل است. این را می‌توان توسط پیمایش گره‌های زیردرخت برای پیدا کردن ارزش هایشان در ترتیب سورت شده و به صورت بازگشتی انتخاب میانه به عنوان ریشهٔ زیردرخت در "(O(n" انجام داد.
همان‌طور که عملیات توازن "(O(n" زمان (وابسته به تعداد گره‌های زیردرخت) می‌برد، درج کردن دارای بدترین عملکرد از "(O(n" می‌باشد. اما از آنجا که این بدترین سناریو سرشکن می‌شود درج کردن در آنالیز استهلاکی (O(log n زمان می‌برد.
تعادل گره "v به صورت" ماکس "قدر مطلق تفاوت در اندازه بین فرزند چپ و راست آن منهای ۱" یا "۰" تعریف می‌شود. به عبارت دیگر:
formula_1
بلافاصله بعد از ساختن دوبارهٔ یک زیر درخت که ریشه‌اش v می‌باشد: I("v") = ۰.
Lemma: دقیقاً قبل از ساختن دوباره یک زیردرخت که ریشه‌اش v می‌باشد: formula_2
اثبات lemma:
اگر formula_4 ریشهٔ زیردرخت بلافاصله بعد از ساختن دوباره باشد formula_5. اگر formula_6 تعداد درج‌های منحط باشد (که به ازای هر درج ارتفاع گره یکی بیشتر می‌شود)، آنگاه: formula_7، formula_8 و formula_9.
تا وقتی formula_10 قبل از توازن دوباره، آنگاه به اندازهٔ formula_11 آیتم در زیردرخت با ریشهٔ formula_12 درج شده بود که به توازن دوباره منجر نشده بود. هر کدام از این درج‌ها می‌توانند در formula_13 انجام شوند. درج آخر که منجر به توازن دوباره می‌شود به اندازهٔ formula_14 هزینه دارد. با استفاده از آنالیز استهلاکی واضح است که هزینهٔ سرشکن هر درج formula_13 است:
formula_16
درختان قربانی غیرمعمول اند از این لحاظ که حذف کردن در آن‌ها آسان تر است از درج کردن. برای اضافه کردن عملیات حذف، درختان قربانی باید یک مقدار اضافی در ساختار دادهٔ درخت ذخیره کنند. این ویژگی، که به آن MaxNodeCount می‌گوییم بیشترین NodeCount ای می‌باشد که داریم که وقتی کل درخت دوباره ساخته می‌شود برابر NodeCount قرار می‌گیرد و بعد از هر درج برابر(max(MaxNodeCount, NodeCount می‌شود.
برای حذف یک آیتم به صورت معمولی عمل می‌کنیم همان‌طور که از یک درخت جستجو ی معمولی حذف می‌کنیم، ولی اگر:
آنگاه عملیات توازن دوباره را روی کل درخت انجام می‌دهیم، باید به یاد داشته باشیم که MaxNodeCount را برابر NodeCount قرار دهیم.
این عملیات حذف را در بدترین حالت خود یعنی (O(log n قرار می‌دهد؛ هرچند این هزینه سرشکن شده و به (O(log n تبدیل می‌شود.
تذکر: پاراگراف زیر کاملاً غلط است! حد اکثر n/2 -1 باید به حداقل (O(n تغییر یابند، و پیچیدگی زمانی باید برای هر سطح از درخت جداگانه در نظر گرفته شود
فرض کنید درخت قربانی formula_17 آیتم دارد و همین الان متوازن شده‌است یعنی یک درخت دودویی کامل است. حداکثر formula_18 حذف می‌تواند انجام گیرد قبل از اینکه درخت نیاز به توازن دوباره داشته باشد. هر کدام از این حذف‌ها formula_19 زمان می‌برند (زمان لازم برای پیدا کردن آیتم و حذف آن). تعداد formula_20 حذف منجر به ساخت دوبارهٔ درخت شده و formula_21 (یا همان formula_22) زمان می‌برند. با استفاده از آنالیز استهلاکی واضح است که هزینهٔ سرشکن هر حذف formula_19 می‌باشد:
formula_24
جستجوی درخت قربانی از درخت جستجوی دودویی استاندارد گرفته نشده و دارای بدترین اوردر زمانی (O(log n می‌باشد. این در مقایسه با درختان اسپلی است که بدترین اوردر (O(n دارند. حافظه سربار کاهش یافتهٔ گره‌ها در درخت قربانی در مقایسه با درختان جستجوی دودویی خود-متعادل می‌تواند مکان رفرنس‌ها و ذخیره‌سازی را پیشرفت دهد.