درخت قربانی

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

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

تئوری

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

size(left) <= α*size(node)
size(right) <= α*size(node)

که در آن اندازه را می‌توان به صورت بازگشتی مانند زیر تعریف کرد:

function size(node)
 if node = nil
 return 0
 else
 return size(node->left) + size(node->right) + 1
end

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

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

height(tree) <= log1/α(NodeCount) + 1

درختان قربانی تضمین نمی‌کنند که α-وزن-تعادل در همه زمان‌ها نگه داشته شود اما همیشه تقریباً α-ارتفاع-متعادل می‌باشند :

height(scapegoat tree) <= log1/α(NodeCount) + 1

این باعث می‌شود درختان قربانی شبیه به درختان سرخ-سیاه شوند که در هر دوی اینها دارای محدودیت در ارتفاع درخت هستیم. هر چند این دو درخت تا حد زیادی در پیاده‌سازی اینکه کجا باید چرخش یا متعادل سازی دوباره رخ دهد متفاوت‌اند. در حالی که درختان سرخ-سیاه اطلاعات اضافی مانند رنگ در هر گره ذخیره می‌کنند که مکان گره را با آن تشخیص می‌دهیم، درختان قربانی یک قربانی که α-وزن-متعادل نیست را برای انجام عملیات توازن پیدا می‌کنند. این تقریباً شبیه به درختان AVL است که در آن چرخش بستگی به 'تعادل' گره‌ها دارد، اما تشخیص تعادل در این دو درخت بسیار متفاوت است. از آنجا که درختان AVL در هر بار درج و حذف مقدار تعادل درخت را بررسی می‌کنند، این مقدار معمولاً در هر گره ذخیره می‌شود؛ درختان قربانی تنها زمانی قادر به محاسبه این مقدار هستند که به آن نیاز پیدا می‌کنند، که این تنها زمانی رخ می‌دهد که بخواهیم یک قربانی پیدا کنیم.

بر خلاف اکثر درختان جستجوی خود متعادل دیگر درختان قربانی کاملاً برای متعادل سازی خودشان انعطاف‌پذیر هستند. آن‌ها از هر α به‌طوری‌که α بین 0.5 و 1 است پیروی می‌کنند. یک α با مقدار نزدیک به ۱ یک توازن کمتر را نتیجه می‌دهد که درج را سریع تر ولی جستجو و حذف را کندتر می‌کند و برای αهای نزدیک ۰٫۵ بالعکس؛ بنابراین در برنامه‌های عملی یک α می‌تواند بسته به اینکه چه مقدار این عملیات‌ها باید انجام شوند انتخاب شود.

عملیات‌ها

درج

درج کردن با همان ایده‌های اساسی یک درخت جستجوی دودویی نامتعادل پیاده‌سازی شده‌است البته با کمی تغییرات قابل توجه.

هنگام پیدا کردن نقطه درج عمق گره جدید نیز باید ثبت شود. این عمل از طریق یک شمارنده ساده انجام می‌گیرد که با هر پله از جستجو افزایش می‌یابد که به‌طور مؤثر تعداد یال‌های بین ریشه و محل درج گره است. اگر این گره α-ارتفاع-تعادل (تعریف بالا) را نقض کند یک توازن دوباره مورد نیاز است.

برای توازن دوباره، یک زیردرخت کامل که ریشه اش قربانی است تحت عملیات توازن دوباره قرار می‌گیرد. قربانی تعریف شده‌است به عنوان جد یک گره درج شده که α-وزن متعادل نیست. همیشه یک جد اینچنینی وجود خواهد داشت. ایجاد توازن دوباره در هر یک از آن‌ها ویژگی α-ارتفاع-تعادل را بازیابی خواهد کرد.

یکی از راه‌های پیدا کردن یک قربانی این است که از گره جدید به سمت ریشه حرکت کنیم و اولین گرهی را که α-وزن-متعادل نیست انتخاب کنیم.

صعود به ریشه به (O(log n فضای ذخیره‌سازی معمولاً در پشته یا اشاره گر پدر نیاز دارد. در واقع این می‌تواند با داشتن اشاره گر به پدر در هر فرزند اجتناب شود.

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

size(left) <= α*size(node)
size(right) <= α*size(node)

اما بهینه‌سازی بزرگی می‌تواند انجام شود با توجه به این که ما در حال حاضر دو تا از سه اندازه را می‌دانیم و فقط سومی نیاز به محاسبه شدن دارد.

برای نشان دادن این موضوع مثال زیر را در نظر بگیرید. فرض کنید که ما در حال بازگشت به ریشه باشیم:

size(parent) = size(node) + size(sibling) + 1

اما:

size(inserted node) = ۱.

این مورد بی‌اهمیت دانسته شده:

size[x+1] = size[x] + size(sibling) + 1

که در آن x = این گره x + 1 = پدر و (size(sibling تنها فراخوانی تابع مورد نیاز است.

هنگامی که قربانی یافت شد، زیردرختی که ریشه در قربانی دارد به‌طور کامل بازسازی شده کاملاً متعادل است. این را می‌توان توسط پیمایش گره‌های زیردرخت برای پیدا کردن ارزش هایشان در ترتیب سورت شده و به صورت بازگشتی انتخاب میانه به عنوان ریشهٔ زیردرخت در (O(n انجام داد.

همان‌طور که عملیات توازن (O(n زمان (وابسته به تعداد گره‌های زیردرخت) می‌برد، درج کردن دارای بدترین عملکرد از (O(n می‌باشد. اما از آنجا که این بدترین سناریو سرشکن می‌شود درج کردن در آنالیز استهلاکی (O(log n زمان می‌برد.

طرح اثبات برای هزینه درج کردن

تعادل گره v به صورت ماکس "قدر مطلق تفاوت در اندازه بین فرزند چپ و راست آن منهای ۱" یا "۰" تعریف می‌شود. به عبارت دیگر:

$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|)\leq \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 <= α*MaxNodeCount

آنگاه عملیات توازن دوباره را روی کل درخت انجام می‌دهیم، باید به یاد داشته باشیم که MaxNodeCount را برابر NodeCount قرار دهیم.

این عملیات حذف را در بدترین حالت خود یعنی (O(log n قرار می‌دهد؛ هرچند این هزینه سرشکن شده و به (O(log n تبدیل می‌شود.

طرح اثبات برای هزینهٔ حذف

تذکر: پاراگراف زیر کاملاً غلط است! حد اکثر n/2 -1 باید به حداقل (O(n تغییر یابند، و پیچیدگی زمانی باید برای هر سطح از درخت جداگانه در نظر گرفته شود

فرض کنید درخت قربانی $n$

آیتم دارد و همین الان متوازن شده‌است یعنی یک درخت دودویی کامل است. حداکثر

n/2-1

حذف می‌تواند انجام گیرد قبل از اینکه درخت نیاز به توازن دوباره داشته باشد. هر کدام از این حذف‌ها

O(\log {n})

زمان می‌برند (زمان لازم برای پیدا کردن آیتم و حذف آن). تعداد

n/2

حذف منجر به ساخت دوبارهٔ درخت شده و

O(\log {n})+O(n)

(یا همان

O(n)

) زمان می‌برند. با استفاده از آنالیز استهلاکی واضح است که هزینهٔ سرشکن هر حذف

O(\log {n})

می‌باشد:

${\sum _{1}^{n \over 2}O(\log {n})+O(n) \over {n \over 2}}={{n \over 2}O(\log {n})+O(n) \over {n \over 2}}=O(\log {n})$

جستجو

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

جستارهای وابسته

منابع

↑ Andersson, Arne (1989). Improving partial rebuilding by using simple balance criteria. Proc. Workshop on Algorithms and Data Structures. Journal of Algorithms. Springer-Verlag. pp. 393–402. doi:10.1007/3-540-51542-9_33.
↑ Galperin, Igal; Rivest, Ronald L. (1993). "Scapegoat trees". Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms: 165–174.

پیوند به بیرون

[anderson1-1] Andersson, Arne (1989). Improving partial rebuilding by using simple balance criteria. Proc. Workshop on Algorithms and Data Structures. Journal of Algorithms. Springer-Verlag. pp. 393–402. doi:10.1007/3-540-51542-9_33.

[galperin_rivest-2] Galperin, Igal; Rivest, Ronald L. (1993). "Scapegoat trees". Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms: 165–174.