Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनरी इंडेक्स्ड ट्री या फेनविक ट्री


संख्याओं के एक फ्लैट सरणी की तुलना में, फेनविक ट्री दो ऑपरेशन्स के बीच बेहतर संतुलन प्रदान करता है: तत्व अद्यतन और प्रीफिक्स सम गणना। m संख्याओं के फ्लैट सरणी के मामले में, हम या तो तत्वों को संग्रहीत कर सकते हैं, या प्रीफिक्स योग को। पहले उदाहरण में, प्रीफिक्स योग की गणना के लिए रैखिक समय की आवश्यकता होती है; दूसरे उदाहरण में, सरणी तत्वों को संशोधित या अद्यतन करने के लिए रैखिक समय की आवश्यकता होती है (दोनों उदाहरणों में, अन्य ऑपरेशन को स्थिर समय में पूरा किया जा सकता है)। फेनविक ट्री दोनों ऑपरेशन्स को O(log m) समय में पूरा करने की अनुमति देते हैं। यह संख्याओं को एक ट्री के रूप में प्रस्तुत करके प्राप्त किया जाता है, जहां प्रत्येक नोड का मान उस सबट्री में संख्याओं के योग के रूप में माना जाता है। ट्री संरचना ऑपरेशन्स को केवल O(log m) नोड एक्सेस का उपयोग करके पूरा करने की अनुमति देती है।

एक-आधारित सरणी पर विचार करके, एक फेनविक ट्री को सबसे आसानी से समझा जा सकता है। प्रत्येक तत्व जिसका इंडेक्स j 2 की घात है, पहले j तत्वों का योग समाहित करता है। जिन तत्वों के इंडेक्स दो (अलग) 2 की घातों के योग को दर्शाते हैं, उनमें पिछली 2 की घात के बाद से तत्वों का योग होता है। मूल रूप से, प्रत्येक तत्व अपने पैरेंट के बाद से मानों के योग को समाहित करता है, और उस पैरेंट को इंडेक्स में न्यूनतम या लीस्ट-सिग्निफिकेंट बिट को क्लियर करके पाया जाता है।

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

उदाहरण के लिए, मान लीजिए कोई पहले ग्यारह मानों का योग निकालना चाहता है। ग्यारह बाइनरी में 1011 है। इसमें तीन 1 बिट्स हैं, इसलिए तीन तत्वों को जोड़ा जाना चाहिए: 1000, 1010, और 1011। इनमें क्रमशः मान 1-8, 9-10, और 11 के योग होते हैं।

एक सरल C कार्यान्वयन निम्नानुसार है।

उदाहरण

#define LSB(i) ((i) & -(i)) // न्यूनतम या लीस्ट सिग्निफिकेंट बिट को छोड़कर सभी बिट्स को शून्य करता है int A1[SIZE]; int sum(int i) // इंडेक्स 1 से i तक का योग लौटाता है{    int sum = 0;    while (i > 0)    sum += A1[i], i -= LSB(i);    return sum; } void add(int i, int k) // इंडेक्स i वाले तत्व में k जोड़ता है{    while (i < SIZE)    A1[i] += k, i += LSB(i); } 

  1. C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम ढूंढेगा।बाइनरी ट्री का स्पाइरल सम  बाइनरी ट्री के स्पाइरल ट्रैवर्सल में मिलने वाले नोड्स का योग है।ट्री के स्पाइरल ट्रैवर्सल में, नोड्स को रूट से लीफ नोड तक ट्रैवर्स कि

  1. C++ में बाइनरी ट्री में अधिकतम पथ योग C++ में बाइनरी ट्री में अधिकतम पथ योग

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड एक मान रखता है। हमारा कार्य बाइनरी ट्री के दो पत्तों के बीच अधिकतम पथ योग ढूंढने के लिए एक प्रोग्राम बनाना है। यहां, हमें एक पत्ते नोड से दूसरे पत्ते नोड तक का पथ ढूंढना है जो मानों का अधिकतम योग प्रदान करेगा। यह अधिकतम योग पथ रूट न

  1. बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज