डेटा संरचना में टूर्नामेंट पेड़, विजेता पेड़ और हारने वाले पेड़

यहां हम टूर्नामेंट ट्री, विनर और लूजर ट्री देखेंगे। टूर्नामेंट ट्री n बाहरी नोड्स और n-1 आंतरिक नोड्स के साथ एक पूर्ण बाइनरी ट्री है। बाहरी नोड्स खिलाड़ियों का प्रतिनिधित्व करते हैं, और आंतरिक नोड्स दो खिलाड़ियों के बीच मैच के विजेता का प्रतिनिधित्व करते हैं। इस पेड़ को सेलेक्शन ट्री के नाम से भी जाना जाता है।

टूर्नामेंट पेड़ों के कुछ गुण हैं। ये नीचे की तरह हैं -

• यह पेड़ जड़ है। तो पेड़ में लिंक और माता-पिता से बच्चों के लिए निर्देशित पथ, और माता-पिता के बिना एक अनूठा तत्व है

• किसी भी तुलना ऑपरेटर के लिए मूल मान उस नोड से कम या उसके बराबर है, जब तक कि माता-पिता और बच्चों के सापेक्ष मूल्य पूरे पेड़ में अपरिवर्तनीय हैं, तब तक इसका उपयोग किया जा सकता है

• कई नोड्स वाले पेड़ जिनमें 2 की शक्ति नहीं होती है, उनमें छेद होते हैं। छेद पेड़ के किसी भी स्थान पर मौजूद हो सकते हैं।

• यह पेड़ बाइनरी हीप्स का उचित सामान्यीकरण है

• रूट टूर्नामेंट के समग्र विजेता का प्रतिनिधित्व करेगा।

टूर्नामेंट ट्री दो प्रकार के होते हैं -

• विजेता ट्री

• लूजर ट्री

विजेता ट्री

विनर ट्री एक पूर्ण बाइनरी ट्री है, जिसमें प्रत्येक नोड अपने दो बच्चों में से छोटे या बड़े का प्रतिनिधित्व करता है, विजेता ट्री कहलाता है। जड़ पेड़ का सबसे छोटा या सबसे बड़ा नोड धारण कर रहा है। टूर्नामेंट ट्री का विजेता सभी अनुक्रमों में सबसे छोटा या सबसे बड़ा n कुंजी है। यह देखना आसान है कि विजेता ट्री O(log n) समय में बन सकता है।

उदाहरण - मान लीजिए कि कुछ कुंजियाँ हैं, 3, 5, 6, 7, 20, 8, 2, 9

लूसर ट्री

लूजर ट्री n प्लेयर्स के लिए पूर्ण बाइनरी ट्री हैं जहां n बाहरी नोड्स और n-1 आंतरिक नोड मौजूद हैं। मैच के हारने वाले को आंतरिक नोड्स में संग्रहीत किया जाता है। लेकिन इसमें ओवरऑल विनर को ट्री [0] पर स्टोर किया जाता है। लूसर एक वैकल्पिक प्रतिनिधित्व है, जो मैच के लूजर को संबंधित नोड पर संग्रहीत करता है। हारने वाले का एक फायदा यह है कि, विजेता ट्री के आउटपुट के बाद ट्री को पुनर्गठित करने के लिए, इस पथ पर नोड्स के सिबलिंग के बजाय पत्ती से जड़ तक के रास्ते पर नोड की जांच करना पर्याप्त है।

उदाहरण - लूजर ट्री बनाने के लिए, हमें सबसे पहले विनर ट्री बनाना होगा।

मान लीजिए कुछ कुंजियाँ हैं, 10, 2, 7, 6, 5, 9, 12, 1। तो हम सबसे पहले न्यूनतम विजेता ट्री बनाएंगे।

अब, हम हारे हुए मैच को प्रत्येक आंतरिक नोड में संग्रहित करेंगे।