बाइनरी पेड़ में संतुलित रकम

Question

मुझे एक दिलचस्प एल्गोरिदमिक समस्या मिली। हमें एक बाइनरी पेड़ दिया जाता है जिसमें पत्तियों के अलावा प्रत्येक चरम पर मूल्य 0 होता है। पत्तियों में हम दो विकल्प हैं:

1. मूल्य अज्ञात है, लेकिन हम जानते हैं कि यह एक प्राकृतिक संख्या> = 1

2. मूल्य में जाना जाता है और यह एक प्राकृतिक संख्या> = 1

है

समस्या यह तय करना है कि पत्तियों में हर अज्ञात मान को सेट करना संभव है जैसे कि किसी दिए गए पेड़ के प्रत्येक उप-भाग में बाएं और दाएं उपट्री में वर्टेक्स में समान मान होते हैं।

उदाहरण के लिए:

Tree1:

 0 
    /\ 
    0 ? 
/\ 
    0 5 
/\ 
? ? 

जवाब है नहीं - विचार है कि हर प्रश्न चिह्न एक प्राकृतिक संख्या हो गया है को ध्यान में रखकर, यह निश्चित रूप से संभव नहीं

पेड़ 2:

 0 
    / \ 
    0  0 
/\ /\ 
    0 10 ? ? 
/\ 
5 ? 

उत्तर हाँ है - हम प्रत्येक प्रश्न चिह्न में क्रमश: 5, 10, 10 सेट करते हैं।

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

Answer 1

मुझे लगता है कि एक रिकर्सिव समाधान ठीक काम करता है। प्रत्येक नोड में बाएं और दाएं बच्चों का वजन मिलता है।

1. एल और आर दोनों जाना जाता है:: आप निम्नलिखित मामलों है नोड है वैध iff एल == आर
2. न तो एल या आर में जाना जाता है: यह नोड अज्ञात है और बहुलता दो बार है की है कि एल और आर
3. वास्तव में एल या आर में से एक अज्ञात है: यह नोड वैध है अगर ज्ञात बच्चे का वजन अज्ञात बच्चे की गुणा द्वारा विभाजित है। यह वजन ज्ञात बच्चे के वजन से दोगुना है।

यहां विचार यह है कि आपको ट्रैक रखने की आवश्यकता है कि कितने अज्ञात बच्चे एक निश्चित नोड से नीचे हैं, क्योंकि मूल्य केवल पूर्णांक हो सकते हैं। बहुतायत हमेशा युगल होती है क्योंकि, एक नोड पर, भले ही उसके बाएं बच्चे के पास 4 अज्ञात हैं और उसके अधिकार में 1 अज्ञात है, तो 1 अज्ञात को 4 का एक बहु होना होगा और इसलिए इस नोड की बहुतायत 8 होने की आवश्यकता होगी।

नोट: मैं यहां शब्द बहुतायत का उपयोग कर रहा हूं और यह वास्तव में बिल्कुल सही नहीं है, लेकिन मैं उपयोग करने के लिए एक अच्छा शब्द नहीं सोच सका।

यहाँ कोड है, गो में, जो आपके उदाहरण पर इस समाधान को दर्शाता है:

package main 

import (
    "fmt" 
) 

// Assume that (Left == nil) == (Right == nil) 
type Tree struct { 
    Val   int 
    Left, Right *Tree 
} 

func (t *Tree) GetWeight() (weight int, valid bool) { 
    if t.Left == nil { 
    return t.Val, true 
    } 
    l, lv := t.Left.GetWeight() 
    r, rv := t.Right.GetWeight() 
    if !lv || !rv { 
    return 0, false 
    } 
    if l < 0 && r < 0 { 
    if l < r { 
     return 2 * l, true 
    } 
    return 2 * r, true 
    } 
    if l < 0 { 
    return 2 * r, r%(-l) == 0 
    } 
    if r < 0 { 
    return 2 * l, l%(-r) == 0 
    } 
    return r + l, r == l 
} 

func main() { 
    t := Tree{0, 
    &Tree{0, 
     &Tree{0, 
     &Tree{Val: 5}, 
     &Tree{Val: -1}, 
     }, 
     &Tree{Val: 10}, 
    }, 
    &Tree{0, 
     &Tree{Val: -1}, 
     &Tree{Val: -1}, 
    }, 
    } 
    w, v := t.GetWeight() 
    fmt.Printf("%d, %t\n", w, v) 
    t = Tree{0, 
    &Tree{0, 
     &Tree{0, 
     &Tree{Val: -1}, 
     &Tree{Val: -1}, 
     }, 
     &Tree{Val: 5}, 
    }, 
    &Tree{Val: -1}, 
    } 
    w, v = t.GetWeight() 
    fmt.Printf("%d, %t\n", w, v) 
} 

Answer 2

यह समानांतर है। आप प्रत्येक चरम पर समीकरणों (और गणना) विलय, जड़ों की ओर पत्तियों से समीकरणों की प्रणालियों का निर्माण करते हैं। जब समीकरणों की एक प्रणाली असंभव हो जाती है, तो सभी गणनाओं को रोक दें।

इसका एक गैर समांतर एनालॉग शॉर्ट-सर्किट मूल्यांकन होगा।