এখানে আমরা টুর্নামেন্ট ট্রি, উইনার এবং লুজার ট্রি দেখতে পাব। টুর্নামেন্ট ট্রি হল একটি সম্পূর্ণ বাইনারি ট্রি যেখানে n বাহ্যিক নোড এবং n – 1টি অভ্যন্তরীণ নোড রয়েছে। বাহ্যিক নোডগুলি খেলোয়াড়দের প্রতিনিধিত্ব করে এবং অভ্যন্তরীণ নোডগুলি দুই খেলোয়াড়ের মধ্যে ম্যাচের বিজয়ীকে প্রতিনিধিত্ব করে৷ এই গাছ সিলেকশন ট্রি নামেও পরিচিত।
টুর্নামেন্ট গাছের কিছু বৈশিষ্ট্য আছে। এগুলো নিচের মত -
-
এই গাছ মূল। তাই বৃক্ষের লিঙ্ক এবং পিতামাতা থেকে শিশুদের দিকে নির্দেশিত পথ, এবং একটি অনন্য উপাদান রয়েছে যার মধ্যে পিতামাতা নেই
-
প্যারেন্ট ভ্যালু সাধারণ যেকোন তুলনা অপারেটরের কাছে সেই নোডের কম বা সমান, যতক্ষণ পর্যন্ত পিতামাতা এবং বাচ্চাদের আপেক্ষিক মান গাছ জুড়ে অপরিবর্তনীয় থাকে ততক্ষণ ব্যবহার করা যেতে পারে।
-
2 এর শক্তি নয় এমন অনেকগুলি নোড সহ গাছে গর্ত থাকে। গাছের যেকোনো জায়গায় গর্ত থাকতে পারে।
-
এই গাছটি বাইনারি স্তূপের একটি সঠিক সাধারণীকরণ
-
রুট টুর্নামেন্টের সামগ্রিক বিজয়ীর প্রতিনিধিত্ব করবে।
দুই ধরনের টুর্নামেন্ট ট্রি −
-
বিজয়ী গাছ
-
লুজার ট্রি
বিজয়ী গাছ
উইনার ট্রি হল একটি সম্পূর্ণ বাইনারি ট্রি, যেখানে প্রতিটি নোড তার দুটি সন্তানের ছোট বা বড়কে প্রতিনিধিত্ব করছে, তাকে উইনার ট্রি বলা হয়। মূলটি গাছের সবচেয়ে ছোট বা সবচেয়ে বড় নোডকে ধরে রাখে। টুর্নামেন্ট ট্রির বিজয়ী হল সমস্ত সিকোয়েন্সের সবচেয়ে ছোট বা সবচেয়ে বড় n কী। এটা দেখা সহজ যে বিজয়ী গাছ O(log n) সময়ে গঠিত হতে পারে।
উদাহরণ − ধরুন কিছু কী আছে, 3, 5, 6, 7, 20, 8, 2, 9
লুজার গাছ
Looser Trees হল n প্লেয়ারদের জন্য সম্পূর্ণ বাইনারি ট্রি যেখানে n এক্সটার্নাল নোড এবং n – 1 টি ইন্টারনাল নোড থাকে। ম্যাচের লুজারটি অভ্যন্তরীণ নোডগুলিতে সংরক্ষণ করা হয়। কিন্তু এই সামগ্রিক বিজয়ী গাছে সংরক্ষণ করা হয় [0]। লোজার হল একটি বিকল্প উপস্থাপনা, যেটি সংশ্লিষ্ট নোডে একটি ম্যাচের লুজারকে সঞ্চয় করে। লোজারটির একটি সুবিধা হল, বিজয়ী গাছের আউটপুট হওয়ার পরে গাছটিকে পুনর্গঠন করতে, এই পথে নোডগুলির ভাইবোনের পরিবর্তে পাতা থেকে মূল পর্যন্ত পথে নোড পরীক্ষা করাই যথেষ্ট।
উদাহরণ − একটি শিথিল গাছ গঠন করতে, আমাদের প্রথমে বিজয়ী গাছ তৈরি করতে হবে৷
ধরুন কিছু কী আছে, 10, 2, 7, 6, 5, 9, 12, 1। তাই আমরা প্রথমে সর্বনিম্ন বিজয়ী গাছ তৈরি করব।
এখন, আমরা প্রতিটি অভ্যন্তরীণ নোডে ম্যাচের লুজার সংরক্ষণ করব।
