درخت مسابقه
درخت مسابقه یک نوع درخت دودویی است. درخت مسابقه به دو نوع درخت برنده و درخت بازنده تقسیم می‌شود. راس‌های درخت مسابقه به دو نوع رئوس خارجی (برگ‌ها) و رئوس داخلی (رئوس غیر برگ) تقسیم‌بندی می‌شوند. راس‌های خارجی نماینده بازیکنان هستند و رئوس داخلی هر کدام نتیجه تک‌مسابقه بین برنده‌های دو زیر درخت خود را در خود نگه می‌دارند.
در درخت برنده هر راس داخلی باید بازیکن برنده بین دو راس فرزند خود را ذخیره کند و در انتها ریشه درخت حاوی بازیکنی خواهد بود که در تمام تک‌مسابقه‌ها برنده شده‌است. اگر برنده را در هر تک‌مسابقه بازیکنی در نظر بگیریم که مقدار آن کمتر است، در این صورت ریشه درخت اشاره به بازیکنی خواهد داشت که کمترین مقدار را بین تمام بازیکنان دارد. از کاربردهای این داده ساختار می‌توان به الگوریتم مرتب‌سازی مسابقه‌ای اشاره نمود.
رئوس خارجی نماینده عناصر می‌شوند و سپس هر راس داخلی برنده بین دو فرزند خود را ذخیره کرده و به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی برندهٔ نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر خواهد بود. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از formula_1 است. زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. چون ارتفاع درخت از formula_3 است زمان حذف از formula_3 می‌شود. زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. چون ارتفاع درخت از formula_3 است زمان جایگزینی نیز از formula_3 می‌شود.
در ادامه پیاده‌سازی درخت برنده با استفاده از آرایه به زبان پایتون آمده است.
import math def build(A, B, x, l, r):
def pop(B):
def minimum(B):
def replace_minimum(B, value):
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)) در درخت بازنده هر راس، بازنده تک‌مسابقه را در خود ذخیره می‌کند اما برنده را به راس پدر خود می‌فرستد. در نتیجه ریشه حاوی بازنده تک‌مسابقهٔ نهایی خواهد بود و برنده نهایی را باید در راسی جداگانه از درخت ذخیره کنیم.
رئوس خارجی نماینده عناصر می‌شوند و مقدار خود را به پدر به عنوان نتیجه می‌دهند. سپس هر راس داخلی بازنده عناصر داده شده توسط دو فرزند خود را ذخیره کرده و برنده آن‌ها را به عنوان نتیجه به راس پدر خود می‌دهد. به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی بازندهٔ تک‌مسابقهٔ نهایی خواهد بود و برنده نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر را به عنوان نتیجه به راسی جداگانه می‌دهد. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از formula_1 است. زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم. سپس کافی است راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود دهند تا درخت جدید ساخته شود. چون ارتفاع درخت از formula_3 است زمان حذف از formula_3 می‌شود. زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم. سپس راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود می‌دهند تا درخت جدید ساخته شود. چون ارتفاع درخت از formula_3 است زمان جایگزینی نیز از formula_3 می‌شود.
در ادامه پیاده‌سازی درخت بازنده با استفاده از آرایه به زبان پایتون آمده است. حافظه اضافی که برنده نهایی مسابقه را نگه می‌دارد، در خانه صفر آرایه لحاظ شده‌است. import math def rec_build(A, B, x, l, r):
def build(A):
def pop(B):
def minimum(B):
def replace_minimum(B, value):
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))
Donald Knuth, The Art of Computer Programming, Sorting and Searching, Volume 3, 1973. Stepanov, Alexander and Aaron Kershenbaum. Using Tournament Trees to Sort, Brooklyn: Center for Advanced Technology in Telecommunications, 1986. https://www.cise.ufl.edu/~sahni/cop3530/slides/lec252.pdf