यहाँ हम टूर्नामेंट ट्री (Tournament Trees), विजेता ट्री (Winner Trees) और हारने वाला ट्री (Loser Trees) देखेंगे। टूर्नामेंट ट्री n बाहरी नोड्स और n-1 आंतरिक नोड्स के साथ एक पूर्ण बाइनरी ट्री है। बाहरी नोड्स खिलाड़ियों (players) को दर्शाते हैं, और आंतरिक नोड्स दो खिलाड़ियों के बीच मैच के विजेता को दर्शाते हैं। इस ट्री को चयन ट्री (Selection tree) के रूप में भी जाना जाता है।
टूर्नामेंट ट्री के कुछ गुण हैं:
यह ट्री रूटेड है। इसलिए ट्री में लिंक और माता-पिता से बच्चों की ओर निर्देशित पथ, और एक अद्वितीय तत्व है जिसका कोई माता-पिता नहीं है
माता-पिता का मान उस नोड से कम या बराबर होता है, किसी भी तुलना ऑपरेटर का उपयोग किया जा सकता है जब तक कि पूरे ट्री में माता-पिता और बच्चों का सापेक्ष मान अपरिवर्तनीय रहता है
नोड्स की संख्या जो 2 की घात नहीं है, वाले ट्री में छेद (holes) होते हैं। छेद ट्री में कहीं भी मौजूद हो सकते हैं।
यह ट्री बाइनरी हीप का उचित सामान्यीकरण (proper generalization) है
रूट टूर्नामेंट के समग्र विजेता को दर्शाएगा।
टूर्नामेंट ट्री के दो प्रकार हैं:
विजेता ट्री (Winner Tree)
हारने वाला ट्री (Loser Tree)
विजेता ट्री (Winner Tree)
विजेता ट्री एक पूर्ण बाइनरी ट्री है, जिसमें प्रत्येक नोड अपने दो बच्चों में से छोटे या बड़े को दर्शाता है, जिसे विजेता ट्री कहा जाता है। रूट ट्री के सबसे छोटे या सबसे बड़े नोड को रखता है। टूर्नामेंट ट्री का विजेता सभी अनुक्रमों में सबसे छोटी या सबसे बड़ी n कुंजी है। यह देखना आसान है कि विजेता ट्री O(log n) समय में बनाया जा सकता है।
उदाहरण – मान लीजिए कुछ कुंजियाँ हैं: 3, 5, 6, 7, 20, 8, 2, 9
हारने वाला ट्री (Loser Tree)
हारने वाला ट्री n खिलाड़ियों के लिए पूर्ण बाइनरी ट्री है जहां n बाहरी नोड्स और n-1 आंतरिक नोड्स मौजूद हैं। मैच का हारने वाला आंतरिक नोड्स में संग्रहीत होता है। लेकिन इसमें समग्र विजेता tree[0] पर संग्रहीत होता है। हारने वाला एक वैकल्पिक प्रतिनिधित्व है, जो मैच के हारने वाले को संबंधित नोड पर संग्रहीत करता है। हारने वाले का एक लाभ यह है कि, विजेता ट्री के आउटपुट होने के बाद ट्री को पुनर्गठित करने के लिए, पत्ते से जड़ तक के पथ पर नोड की जांच करना पर्याप्त है बजाय इस पथ पर नोड्स के सहोदरों की जांच करने के।
उदाहरण – हारने वाला ट्री बनाने के लिए, हमें पहले विजेता ट्री बनाना होगा।
मान लीजिए कुछ कुंजियाँ हैं: 10, 2, 7, 6, 5, 9, 12, 1। तो हम पहले न्यूनतम विजेता ट्री बनाएंगे।
अब, हम प्रत्येक आंतरिक नोड में मैच के हारने वाले को संग्रहीत करेंगे।
