موضوع مقاله: درخت مسابقه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت مسابقه | مقدمه: راس‌های درخت مسابقه به دو نوع رئوس خارجی (برگ‌ها) و رئوس داخلی (رئوس غیر برگ) تقسیم‌بندی می‌شوند. | ## بخش 1: درخت مسابقه | راس‌های خارجی نماینده بازیکنان هستند و رئوس داخلی هر کدام نتیجه تک‌مسابقه بین برنده‌های دو زیر درخت خود را در خود نگه می‌دارند. درخت برنده انگشتی|500px|چپ|پیاده‌سازی مرتب‌سازی مسابقه‌ای با درخت برنده در درخت برنده هر راس داخلی باید بازیکن برنده بین دو راس فرزند خود را ذخیره کند و در انتها ریشه درخت حاوی بازیکنی خواهد بود که در تمام تک‌مسابقه‌ها برنده شده‌است. اگر برنده را در هر تک‌مسابقه بازیکنی در نظر بگیریم که مقدار آن کمتر است، در این صورت ریشه درخت اشاره به بازیکنی خواهد داشت که کمترین مقدار را بین تمام بازیکنان دارد. از کاربردهای این داده ساختار می‌توان به الگوریتم مرتب‌سازی مسابقه‌ای اشاره نمود. عملیات روی درخت برنده ایجاد درخت: رئوس خارجی نماینده عناصر می‌شوند و سپس هر راس داخلی برنده بین دو فرزند خود را ذخیره کرده و به این ترتیب تا ریشه پیش می‌رویم. در نهایت ریشه حاوی برندهٔ نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر خواهد بود. به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از است. | ## بخش 2: درخت مسابقه | حذف عنصر کمینه (بیشینه): زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. جایگزینی عنصر کمینه (بیشینه): زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم و سپس تک‌مسابقاتی که روی مسیر بین آن عنصر و ریشه وجود دارد را دوباره انجام می‌دهیم تا درخت جدید ساخته شود. پیاده‌سازی درخت برنده به زبان پایتون در ادامه پیاده‌سازی درخت برنده با استفاده از آرایه به زبان پایتون آمده است. در نتیجه ریشه حاوی بازنده تک‌مسابقهٔ نهایی خواهد بود و برنده نهایی را باید در راسی جداگانه از درخت ذخیره کنیم. عملیات روی درخت بازنده ایجاد درخت: رئوس خارجی نماینده عناصر می‌شوند و مقدار خود را به پدر به عنوان نتیجه می‌دهند. سپس هر راس داخلی بازنده عناصر داده شده توسط دو فرزند خود را ذخیره کرده و برنده آن‌ها را به عنوان نتیجه به راس پدر خود می‌دهد. در نهایت ریشه حاوی بازندهٔ تک‌مسابقهٔ نهایی خواهد بود و برنده نهایی (عنصر کمینه یا بیشینه) بین تمام عناصر را به عنوان نتیجه به راسی جداگانه می‌دهد. | ## بخش 3: درخت مسابقه | به دلیل اینکه تعداد کل رئوس ضریبی از تعداد عناصر می‌شود، در نتیجه زمان ایجاد درخت از است. حذف عنصر کمینه (بیشینه): زمانی که بخواهیم عنصر کمینه (بیشینه) را حذف کنیم، مقدار آن را مثبت بی‌نهایت (منفی بی‌نهایت) می‌کنیم. سپس کافی است راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود دهند تا درخت جدید ساخته شود. جایگزینی عنصر کمینه (بیشینه): زمانی که بخواهیم عنصر کمینه (بیشینه) را جایگزین کنیم، مقدار جدید را به آن می‌دهیم. سپس راس‌های روی مسیر بین آن عنصر و ریشه از پایین به بالا مقدار گرفته شده از فرزند خود را با مقدار ذخیره شده در خود مقایسه کرده و بازنده را در خود ذخیره کرده و برنده را به پدر خود می‌دهند تا درخت جدید ساخته شود. پیاده‌سازی درخت بازنده به زبان پایتون در ادامه پیاده‌سازی درخت بازنده با استفاده از آرایه به زبان پایتون آمده است. | ## جمع‌بندی | حافظه اضافی که برنده نهایی مسابقه را نگه می‌دارد، در خانه صفر آرایه لحاظ شده‌است.