درخت قربانی

در علوم رایانه یک **درخت قربانی **(یا درخت بز طلیعه) یک توازن درخت جستجوی دودویی است که توسط آرن اندرسون و دوباره توسط Igal Galperin و Ronald L. Rivest. اختراع شده. این درخت برای پیدا کردن از (O(log n و برای درج و حذف از آنالیز استهلاکی (O(log n پیروی می‌کند.

برخلاف اکثر درختان جستجوی دودویی خود متعادل دیگر که برای مراجعه از (O(log n پیروی می‌کنند درختان قربانی هیچ حافظه سربار اضافی برای هر گره ندارد: یک گره تنها یک کلید و دو اشاره گر به گره‌های فرزند دارد. این باعث می‌شود درختان قربانی با توجه به تراز ساختار داده‌ها آسان تر پیاده‌سازی شوند و می‌تواند سربار گره‌ها را تا یک سوم کاهش دهد. 

## تئوری
به یک درخت جستجوی دودویی وزن-متعادل می‌گوییم اگر نیمی از گره‌ها در سمت چپ ریشه و نیم دیگر در سمت راست آن باشند.
یک گره α-وزن-متعادل با معیار تعادل وزنی زیر تعریف می‌شود:

 size(left) left) + size(node->right) + 1
 end

وقتی α برابر ۱ باشد توصیف یک لینک لیست متعادل را خواهیم داشت در حالی که با α برابر ۰٫۵ تقریباً یک درخت دودویی کامل داریم.

یک درخت جستجوی دودویی که α-وزن-متعادل است **α-ارتفاع-متعادل **نیز باید باشد، که:

 height(tree) I(v) = \operatorname{max}(|\operatorname{left}(v) - \operatorname{right}(v)| - 1, 0) \ 

بلافاصله بعد از ساختن دوبارهٔ یک زیر درخت که ریشه‌اش v می‌باشد: I(*v*) = ۰.

**Lemma:** دقیقاً قبل از ساختن دوباره یک زیردرخت که ریشه‌اش v می‌باشد:
I(v) = \Omega (|v|) \ 
(\Omega \  نماد O بزرگ است)

اثبات lemma:

اگر v_0 ریشهٔ زیردرخت بلافاصله بعد از ساختن دوباره باشد h(v_0) = \log(|v_0| + 1) \ . اگر \Omega (|v_0|) تعداد درج‌های منحط باشد (که به ازای هر درج ارتفاع گره یکی بیشتر می‌شود)، آنگاه:
I(v) = \Omega (|v_0|) \ ،
h(v) = h(v_0) + \Omega (|v_0|) \  و
\log(|v|) \le \log(|v_0| + 1) + 1 \ .

تا وقتی I(v) = \Omega (|v|) قبل از توازن دوباره، آنگاه به اندازهٔ \Omega (|v|) آیتم در زیردرخت با ریشهٔ v درج شده بود که به توازن دوباره منجر نشده بود. هر کدام از این درج‌ها می‌توانند در O(\log n) انجام شوند. درج آخر که منجر به توازن دوباره می‌شود به اندازهٔ O(|v|) هزینه دارد. با استفاده از آنالیز استهلاکی واضح است که هزینهٔ سرشکن هر درج O(\log n) است:

{\Omega (|v|) O(\log{n}) + O(|v|) \over \Omega (|v|)} = O(\log{n}) \ 

### حذف
درختان قربانی غیرمعمول اند از این لحاظ که حذف کردن در آن‌ها آسان تر است از درج کردن. برای اضافه کردن عملیات حذف، درختان قربانی باید یک مقدار اضافی در ساختار دادهٔ درخت ذخیره کنند. این ویژگی، که به آن MaxNodeCount می‌گوییم بیشترین NodeCount ای می‌باشد که داریم که وقتی کل درخت دوباره ساخته می‌شود برابر NodeCount قرار می‌گیرد و بعد از هر درج برابر(max(MaxNodeCount, NodeCount می‌شود.

برای حذف یک آیتم به صورت معمولی عمل می‌کنیم همان‌طور که از یک درخت جستجو ی معمولی حذف می‌کنیم، ولی اگر:

 NodeCount n آیتم دارد و همین الان متوازن شده‌است یعنی یک درخت دودویی کامل است. حداکثر n/2 - 1 حذف می‌تواند انجام گیرد قبل از اینکه درخت نیاز به توازن دوباره داشته باشد. هر کدام از این حذف‌ها O(\log{n}) زمان می‌برند (زمان لازم برای پیدا کردن آیتم و حذف آن). تعداد n/2 حذف منجر به ساخت دوبارهٔ درخت شده و O(\log{n}) + O(n) (یا همان O(n)) زمان می‌برند. با استفاده از آنالیز استهلاکی واضح است که هزینهٔ سرشکن هر حذف O(\log{n}) می‌باشد:

{\sum_{1}^ O(\log{n}) + O(n) \over {n \over 2}} = 
 = 
O(\log{n})

### جستجو
جستجوی درخت قربانی از درخت جستجوی دودویی استاندارد گرفته نشده و دارای بدترین اوردر زمانی (O(log n می‌باشد. این در مقایسه با درختان اسپلی است که بدترین اوردر (O(n دارند. حافظه سربار کاهش یافتهٔ گره‌ها در درخت قربانی در مقایسه با درختان جستجوی دودویی خود-متعادل می‌تواند مکان رفرنس‌ها و ذخیره‌سازی را پیشرفت دهد.

## جستارهای وابسته
* درخت اسپلی
* درختان
* چرخش درخت
* درخت ای وی ال
* درخت بی
* درخت تی
* لیست ساختمان‌های داده

## منابع

## پیوند به بیرون
* قربانی درخت اپلت توسط Kubo Kovac
* قربانی درختان: Galperin و Rivest مقاله توصیف قربانی درختان
* در مشاوره از یک مجموعه‌ای از کارشناسان و جستجو (نسخه کامل مقاله)
* باز ساختمان داده - فصل ۸ - قربانی درختان

رده:جستجوی درخت‌ها
رده:داده ساختارهای استهلاکی
رده:درخت‌های دودویی