درخت مسابقه

درخت مسابقه (به انگلیسی: Tournament tree) یک نوع درخت دودویی است. درخت مسابقه به دو نوع درخت برنده و درخت بازنده تقسیم می‌شود. راس‌های درخت مسابقه به دو نوع رئوس خارجی (برگ‌ها) و رئوس داخلی (رئوس غیر برگ) تقسیم‌بندی می‌شوند. راس‌های خارجی نماینده بازیکنان هستند و رئوس داخلی هر کدام نتیجه تک‌مسابقه (به انگلیسی: Match) بین برنده‌های دو زیر درخت خود را در خود نگه می‌دارند.

درخت برنده

در درخت برنده (به انگلیسی: Winner tree) هر راس داخلی باید بازیکن برنده بین دو راس فرزند خود را ذخیره کند و در انتها ریشه درخت حاوی بازیکنی خواهد بود که در تمام تک‌مسابقه‌ها برنده شده‌است. اگر برنده را در هر تک‌مسابقه بازیکنی در نظر بگیریم که مقدار آن کمتر است، در این صورت ریشه درخت اشاره به بازیکنی خواهد داشت که کمترین مقدار را بین تمام بازیکنان دارد. از کاربردهای این داده ساختار می‌توان به الگوریتم مرتب‌سازی مسابقه‌ای اشاره نمود.

پیاده‌سازی درخت برنده به زبان پایتون

در ادامه پیاده‌سازی درخت برنده با استفاده از آرایه به زبان پایتون آمده است.
import mathdef build(A, B, x, l, r):
    if l == r:
        B[x] = (A[l], 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) + 1][0] < B[2 * x][0]:
            B[x] = B[(2 * x) + 1]
        else:
            B[x] = B[2 * x]def pop(B):
    result = B[1][0]
    index = B[1][1]
    B[index] = None
    while index > 1:
        index = index // 2
        if B[index * 2] is None:
            minimum = B[(index * 2) + 1]
        elif B[(index * 2) + 1] is None:
            minimum = B[index * 2]
        else:
            minimum = min(B[index * 2], B[(index * 2) + 1])
        if minimum == B[index]:
            break
        B[index] = minimum
    return resultdef minimum(B):
    return B[1][0]def replace_minimum(B, value):
    result = B[1][0]
    index = B[1][1]
    B[index] = (value, index)
    while index > 1:
        index = index // 2
        if B[index * 2] is None:
            minimum = B[(index * 2) + 1]
        elif B[(index * 2) + 1] is None:
            minimum = B[index * 2]
        else:
            minimum = min(B[index * 2], B[(index * 2) + 1])
        if minimum == B[index]:
            break
        B[index] = minimum
    return resultA = [-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))

درخت بازنده

در درخت بازنده (به انگلیسی: Loser tree) هر راس، بازنده تک‌مسابقه را در خود ذخیره می‌کند اما برنده را به راس پدر خود می‌فرستد. در نتیجه ریشه حاوی بازنده تک‌مسابقهٔ نهایی خواهد بود و برنده نهایی را باید در راسی جداگانه از درخت ذخیره کنیم.

پیاده‌سازی درخت بازنده به زبان پایتون

در ادامه پیاده‌سازی درخت بازنده با استفاده از آرایه به زبان پایتون آمده است. حافظه اضافی که برنده نهایی مسابقه را نگه می‌دارد، در خانه صفر آرایه لحاظ شده‌است.
import mathdef rec_build(A, B, x, l, r):
    if l == r:
        B[x] = (A[l], x)
        return B[x]
    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 b[0] < a[0]:
            B[x] = a
            return b
        else:
            B[x] = b
            return adef build(A):
    n = len(A)
    tree = [None] * (2 ** (math.ceil(math.log2(n)) + 1))
    tree[0] = rec_build(A, tree, 1, 0, n - 1)
    return treedef pop(B):
    result = B[0][0]
    index = B[0][1]
    B[index] = None
    minimum = None
    while index > 1:
        index = index // 2
        if minimum is None:
            minimum, B[index] = B[index], minimum
        elif B[index] is None:
            pass
        else:
            minimum, B[index] = min(B[index], minimum), max(B[index], minimum)
    B[0] = minimum
    return resultdef minimum(B):
    return B[0][0]def replace_minimum(B, value):
    result = B[0][0]
    index = B[0][1]
    B[index] = (value, index)
    minimum = B[index]
    while index > 1:
        index = index // 2
        if minimum is None:
            minimum, B[index] = B[index], minimum
        elif B[index] is None:
            pass
        else:
            minimum, B[index] = min(B[index], minimum), max(B[index], minimum)
    B[0] = minimum
    return resultA = [-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))