درخت مسابقه

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

درخت برنده

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

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

عملیات روی درخت برنده

ایجاد درخت: $O(n)$

رئوس خارجی نماینده عناصر می‌شوند و سپس هر راس داخلی برنده بین دو فرزند خود را ذخیره کرده و به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی برندهٔ نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر خواهد بود. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از $O(n)$ است.

حذف عنصر کمینه (بیشینه): $O(\log n)$

زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. چون ارتفاع درخت از $O(\log n)$ است زمان حذف از $O(\log n)$ می‌شود.

جایگزینی عنصر کمینه (بیشینه): $O(\log n)$

زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. چون ارتفاع درخت از $O(\log n)$ است زمان جایگزینی نیز از $O(\log n)$ می‌شود.

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

در ادامه پیاده‌سازی درخت برنده با استفاده از آرایه به زبان پایتون آمده است.

import math
def 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 result

def 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 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))

درخت بازنده

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

عملیات روی درخت بازنده

ایجاد درخت: $O(n)$

رئوس خارجی نماینده عناصر می‌شوند و مقدار خود را به پدر به عنوان نتیجه می‌دهند. سپس هر راس داخلی بازنده عناصر داده شده توسط دو فرزند خود را ذخیره کرده و برنده آن‌ها را به عنوان نتیجه به راس پدر خود می‌دهد. به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی بازندهٔ تک‌مسابقهٔ نهایی خواهد بود و برنده نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر را به عنوان نتیجه به راسی جداگانه می‌دهد. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از $O(n)$ است.

حذف عنصر کمینه (بیشینه): $O(\log n)$

زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم. سپس کافی است راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود دهند تا درخت جدید ساخته شود. چون ارتفاع درخت از $O(\log n)$ است زمان حذف از $O(\log n)$ می‌شود.

جایگزینی عنصر کمینه (بیشینه): $O(\log n)$

زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم. سپس راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود می‌دهند تا درخت جدید ساخته شود. چون ارتفاع درخت از $O(\log n)$ است زمان جایگزینی نیز از $O(\log n)$ می‌شود.

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

در ادامه پیاده‌سازی درخت بازنده با استفاده از آرایه به زبان پایتون آمده است. حافظه اضافی که برنده نهایی مسابقه را نگه می‌دارد، در خانه صفر آرایه لحاظ شده‌است.

import math
def 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 a

def 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 tree

def 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 result

def 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 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))

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

منابع

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.