درخت مسابقه

درخت مسابقه یک نوع درخت دودویی است. درخت مسابقه به دو نوع درخت برنده و درخت بازنده تقسیم می‌شود. راس‌های درخت مسابقه به دو نوع رئوس خارجی (برگ‌ها) و رئوس داخلی (رئوس غیر برگ) تقسیم‌بندی می‌شوند. راس‌های خارجی نماینده بازیکنان هستند و رئوس داخلی هر کدام نتیجه تک‌مسابقه بین برنده‌های دو زیر درخت خود را در خود نگه می‌دارند.
درخت برنده
پیاده‌سازی مرتب‌سازی مسابقه‌ای با درخت برنده
در درخت برنده هر راس داخلی باید بازیکن برنده بین دو راس فرزند خود را ذخیره کند و در انتها ریشه درخت حاوی بازیکنی خواهد بود که در تمام تک‌مسابقه‌ها برنده شده است. اگر برنده را در هر تک‌مسابقه بازیکنی در نظر بگیریم که مقدار آن کمتر است، در این صورت ریشه درخت اشاره به بازیکنی خواهد داشت که کمترین مقدار را بین تمام بازیکنان دارد. از کاربردهای این داده ساختار می‌توان به الگوریتم مرتب‌سازی مسابقه‌ای اشاره نمود.
عملیات روی درخت برنده
ایجاد درخت:
رئوس خارجی نماینده عناصر می‌شوند و سپس هر راس داخلی برنده بین دو فرزند خود را ذخیره کرده و به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی برنده نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر خواهد بود. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از است.
حذف عنصر کمینه (بیشینه):
زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. چون ارتفاع درخت از است زمان حذف از می‌شود.
جایگزینی عنصر کمینه (بیشینه):
زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. چون ارتفاع درخت از است زمان جایگزینی نیز از می‌شود.
پیاده‌سازی درخت برنده به زبان پایتون
در ادامه پیاده‌سازی درخت برنده با استفاده از آرایه به زبان پایتون آمده است.
import math
def build(A, B, x, l, r):
if l == r:
Bx = (Al, x)
else:
mid = (l + r) // 2
build(A, B, 2 * x, l, mid)
build(A, B, (2 * x) + 1, mid + 1, r)
if B(2 * x) + 10
1:
index = index // 2
if Bindex * 2 is None:
minimum = B(index * 2) + 1
elif B(index * 2) + 1 is None:
minimum = Bindex * 2
else:
minimum = min(Bindex * 2, B(index * 2) + 1)
if minimum == Bindex:
break
Bindex = minimum
return result
def minimum(B):
return B10
def replace_minimum(B, value):
result = B10
index = B11
Bindex = (value, index)
while index > 1:
index = index // 2
if Bindex * 2 is None:
minimum = B(index * 2) + 1
elif B(index * 2) + 1 is None:
minimum = Bindex * 2
else:
minimum = min(Bindex * 2, B(index * 2) + 1)
if minimum == Bindex:
break
Bindex = minimum
return result
A = -8, 3, 17, 57, 0, -19, 21, 5, 965 , 2, 0, 1, 34, 83
n = len(A)
B = None * (2 ** (math.ceil(math.log2(n)) + 1))
build(A, B, 1, 0, n - 1)
print(replace_minimum(B, -7))
print(pop(B))
print(minimum(B))
درخت بازنده
در درخت بازنده هر راس، بازنده تک‌مسابقه را در خود ذخیره می‌کند اما برنده را به راس پدر خود می‌فرستد. در نتیجه ریشه حاوی بازنده تک‌مسابقه نهایی خواهد بود و برنده نهایی را باید در راسی جداگانه از درخت ذخیره کنیم.
عملیات روی درخت بازنده
ایجاد درخت:
رئوس خارجی نماینده عناصر می‌شوند و مقدار خود را به پدر به عنوان نتیجه می‌دهند. سپس هر راس داخلی بازنده عناصر داده شده توسط دو فرزند خود را ذخیره کرده و برنده آن‌ها را به عنوان نتیجه به راس پدر خود می‌دهد. به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی بازنده تک‌مسابقه نهایی خواهد بود و برنده نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر را به عنوان نتیجه به راسی جداگانه می‌دهد. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از است.
حذف عنصر کمینه (بیشینه):
زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم. سپس کافی است راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود دهند تا درخت جدید ساخته شود. چون ارتفاع درخت از است زمان حذف از می‌شود.
جایگزینی عنصر کمینه (بیشینه):
زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم. سپس راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود می‌دهند تا درخت جدید ساخته شود. چون ارتفاع درخت از است زمان جایگزینی نیز از می‌شود.
پیاده‌سازی درخت بازنده به زبان پایتون
در ادامه پیاده‌سازی درخت بازنده با استفاده از آرایه به زبان پایتون آمده است. حافظه اضافی که برنده نهایی مسابقه را نگه می‌دارد، در خانه صفر آرایه لحاظ شده است.
import math
def rec_build(A, B, x, l, r):
if l == r:
Bx = (Al, x)
return Bx
else:
mid = (l + r) // 2
a = rec_build(A, B, 2 * x, l, mid)
b = rec_build(A, B, (2 * x) + 1, mid + 1, r)
if b0
1:
index = index // 2
if minimum is None:
minimum, Bindex = Bindex, minimum
elif Bindex is None:
pass
else:
minimum, Bindex = min(Bindex, minimum), max(Bindex, minimum)
B0 = minimum
return result
def minimum(B):
return B00
def replace_minimum(B, value):
result = B00
index = B01
Bindex = (value, index)
minimum = Bindex
while index > 1:
index = index // 2
if minimum is None:
minimum, Bindex = Bindex, minimum
elif Bindex is None:
pass
else:
minimum, Bindex = min(Bindex, minimum), max(Bindex, minimum)
B0 = minimum
return result
A = -8, 3, 17, 57, 0, -19, 21, 5, 965 , 2, 0, 1, 34, 83
B = build(A)
print(replace_minimum(B, -7))
print(pop(B))
print(minimum(B))
هرم (علوم رایانه)
درخت دودویی
مرتب‌سازی مسابقه‌ای