এখানে আমরা টুর্নামেন্ট ট্রি, উইনার এবং লুজার ট্রি দেখব। টুর্নামেন্ট ট্রি হল একটি কমপ্লিট বাইনারি ট্রি যেখানে nটি এক্সটার্নাল নোড এবং n-1টি ইন্টারনাল নোড থাকে। এক্সটার্নাল নোডগুলো প্লেয়ারকে প্রতিনিধিত্ব করে, এবং ইন্টারনাল নোডগুলো দুজন প্লেয়ারের মধ্যকার ম্যাচের উইনারকে প্রতিনিধিত্ব করে। এই ট্রিকে সিলেকশন ট্রিও বলা হয়।
টুর্নামেন্ট ট্রির কিছু বৈশিষ্ট্য রয়েছে। সেগুলো নিচের মতো −
এই ট্রি রুটেড। তাই ট্রিতে লিংক এবং পেরেন্ট থেকে চাইল্ডে নির্দেশিত পথ রয়েছে, এবং একটি অনন্য উপাদান আছে যার কোনো পেরেন্ট নেই।
পেরেন্টের মান সেই নোডের চেয়ে কম বা সমান যেকোনো কমপैरিজন অপারেটর ব্যবহার করা যেতে পারে যতক্ষণ না পেরেন্ট এবং চাইল্ডের সাপেক্ষ মান ট্রি 전체ে অপরিবর্তিত থাকে।
যে ট্রিগুলোর নোডের সংখ্যা 2-এর ঘাত নয়, সেগুলো হোল ধারণ করে। হোল ট্রির যেকোনো জায়গায় থাকতে পারে।
এই ট্রি বাইনারি হিপের একটি সঠিক জেনারেলাইজেশন।
রুট পুরো টুর্নামেন্টের সামগ্রিক উইনারকে প্রতিনিধিত্ব করে।
টুর্নামেন্ট ট্রির দুটি ধরন রয়েছে −
উইনার ট্রি
লুজার ট্রি
উইনার ট্রি
উইনার ট্রি হল একটি কমপ্লিট বাইনারি ট্রি, যেখানে প্রতিটি নোড তার দুটি চাইল্ডের ছোট বা বড় মানকে প্রতিনিধিত্ব করে, তাকে উইনার ট্রি বলা হয়। রুট ট্রির সবচেয়ে ছোট বা বড় নোড ধারণ করে। টুর্নামেন্ট ট্রির উইনার হল সব সিকোয়েন্সে সবচেয়ে ছোট বা বড় n কী। সহজেই দেখা যায় উইনার ট্রি O(log n) টাইমে তৈরি করা যায়।
উদাহরণ − ধরি কিছু কী আছে, 3, 5, 6, 7, 20, 8, 2, 9
লুজার ট্রি
লুজার ট্রি হল n প্লেয়ারের জন্য কমপ্লিট বাইনারি ট্রি যেখানে n এক্সটার্নাল নোড এবং n-1 ইন্টারনাল নোড থাকে। ম্যাচের লুজার ইন্টারনাল নোডে সংরক্ষিত থাকে। কিন্তু এই ট্রিতে সামগ্রিক উইনার tree[0]-এ সংরক্ষিত থাকে। লুজার একটি বিকল্প উপস্থাপনা, যা ম্যাচের লুজারকে সংশ্লিষ্ট নোডে সংরক্ষণ করে। লুজারের একটি সুবিধা হল, উইনার ট্রি আউটপুট দেওয়ার পর ট্রি রিস্ট্রাকচার করতে হলে, লিফ থেকে রুট পর্যন্ত পথের নোডগুলো পরীক্ষা করলেই চলে, সিবলিং নোডগুলো চেক করতে হয় না।
উদাহরণ − লুজার ট্রি बनाने için প্রথমে উইনার ট্রি তৈরি করতে হবে।
ধরি কিছু কী আছে, 10, 2, 7, 6, 5, 9, 12, 1। তাহলে আমরা মিনিমাম উইনার ট্রি তৈরি করব।
এখন, আমরা প্রতিটি ইন্টারনাল নোডে ম্যাচের লুজার সংরক্ষণ করব।
