पायथन का उपयोग करके सेगमेंट ट्री कैसे बनाया जाए ...... मैंने निम्नलिखित कोड की कोशिश की:#

def built(arr,start,end,tree,tn):
    if end==start:
        tree[tn]=arr[start]
        return
    mid=(start+end)/2
    built(arr,start,mid,tree,2*tn)
    built(arr,mid+1,end,tree,2*tn+1)
    tree[tn]=tree[2*tn]+tree[2*tn+1]


arr=[1,2,3,4,5,6]
tree=[0,0,0,0,0,0,0,0,0,0,0,0]
built(arr,0,5,tree,1)
for i in tree:
    print (i)

कोड में क्या गलत है ...... रन टाइम एरर दे रहा है (सूची असाइनमेंट इंडेक्स सीमा से बाहर है)

0
aabbccdd 29 मार्च 2018, 21:54

2 जवाब

मैं यह पता लगाने की कोशिश में भी कुछ समय बिताता हूं:

खंड वृक्ष इस प्रकार है:

                  21
            /           \
           6             15      
        /   \       /      \
       3     3     9        6
     / \          / \
    1   2        4   5 

हालांकि, ऐसा लगता है कि इसमें केवल 11 नोड्स हैं, लेकिन लापता हिस्सा 0s है, असली पेड़ इस तरह है:

                  21
            /           \
           6             15      
        /   \       /      \
       3     3     9        6
     / \    / \   / \      / \
    1   2  0   0 4   5    0   0

हमें 0s की आवश्यकता है क्योंकि 0s गुम होने से भ्रम पैदा हो सकता है, उदाहरण के लिए, यदि 0s गुम है तो हम 4 नहीं बता सकते हैं और 5 9 के बच्चे हैं।

क्योंकि सेगमेंट ट्री पूर्ण बाइनरी और संतुलित है (हम इसे हमेशा हिस्सों में विभाजित करते हैं)। यहां हमारे पास पेड़ की लंबाई होनी चाहिए> = 16 इंडेक्स 1 से पेड़ शुरू होने पर विचार करना।

हम पेड़ आवंटित कर सकते हैं = [0 के लिए _ इन रेंज(16)] और सही उत्तर प्राप्त कर सकते हैं: [0, 21, 6, 15, 3, 3, 9, 6, 1, 2, 0, 0, 4, 5, 0, 0]।

यहां बताया गया है कि हम 4n कैसे प्राप्त करते हैं: यदि सरणी की लंबाई 2^i नहीं है, तो पेड़ की ऊंचाई कम से कम logn⎦ + 1 होनी चाहिए, इसलिए कुल ट्री नोड्स 2*2^(logn+1) = 2^(logn) होंगे। + 2) = 4 * 2^लोगन = 4 * एन

इसलिए हम आम तौर पर 4n आकार के पेड़ आवंटित करते हैं।

आप इस कोड को चलाने का स्टैक भी बना सकते हैं, कुछ चक्कर लगाने के बाद, पेड़ [१२] ४ होगा, इसलिए कोड को 'इंडेक्स आउट ऑफ़ रेंज' त्रुटि मिलती है।

0
XueYu 26 अप्रैल 2018, 07:05

पेड़ की ऊंचाई से नीचे जाने का कोई बिंदु नहीं है, उस स्थिति में आप प्रारंभ> अंत की जांच कर सकते हैं और सही होने पर वापस आ सकते हैं।

def built(arr,start,end,tree,tn):
    if end==start:
        tree[tn]=arr[start]
        return
    elif start > end:
        return
    mid=(start+end)/2
    built(arr,start,mid,tree,2*tn)
    built(arr,mid+1,end,tree,2*tn+1)
    tree[tn]=tree[2*tn]+tree[2*tn+1]


arr=[1,2,3,4,5,6]
tree=[0,0,0,0,0,0,0,0,0,0,0,0]
built(arr,0,5,tree,1)
for i in tree:
    print (i)

आप 2 * (2 ** h) - 1 . के रूप में ट्री बनाने के लिए ऐरे को इनिशियलाइज़ कर सकते हैं

0
Pravin 19 जिंदा 2019, 15:48