संतुलित वृक्ष में नोड्स की संख्या

Question

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

  1 
     4  2 
    3 

कार्यक्रम निम्नलिखित उत्पादन दे देंगे:

Query: 1 
Response: 4 2 
Query: 4 
Response 3 
Query: 3 
Response: 0 0 
Query: 2 
Response: 0 0 
Answer: 4 

Answer 1

int countnodes(ele,count) 
{ 
if(ele.right != null) 
    { 
     count += countnodes(ele.right,0); 
    } 
    if(ele.left != null) 
    { 
    count += countnodes(ele.left,0); 
    } 
    return count++; //got to count this node 
} 

Answer 2

मैं अंत में इसे बाहर हैरान।

हालत

यह गारंटी है कि बाईं सबट्री के रूप में कई या उस नोड ई

यह इस प्रकार पर सही सबट्री एक से अधिक नोड होगा प्रत्येक नोड ई के लिए कि से कि

1. गैर-पत्ती नोड्स की संख्या पेड़ की गहराई से गणना की जा सकती है; यह 2 ^{गहराई है - 1}। इसलिए गिनने के लिए दिलचस्प बात पत्ती नोड्स हैं।
2. संतुलित स्थिति को देखते हुए, हमेशा एक ही स्थान होता है जहां एक नया नोड डाला जा सकता है या एक मौजूदा हटा दिया जा सकता है। (इसका मतलब है कि पत्ती नोड्स की एक दी गई संख्या का मतलब है, और केवल एक, पत्ती नोड्स का पैटर्न।)
3. यदि हम नोड के बाएं उपट्री के पत्ते नोड्स की संख्या जानते हैं, तो हम जानते हैं कि पत्ती नोड्स की संख्या (और नोड्स की संख्या) दाएं उपट्री में या तो एक या एक से कम है।
4. यह 2 और 3 से चलता है। दाहिनी उप-धारा में केवल एक पत्ता-नोड स्लॉट होता है जिसमें हम पेड़ का निरीक्षण किए बिना नहीं जानते हैं कि यह भर गया है या नहीं। यह ढूँढना इस एल्गोरिदम में चाल है।

तो, 3 का इस्तेमाल कर रही: मान लें कि हम एक (उप) पेड़ टी हम अपनी बाईं सबट्री में पत्र-गांठ की संख्या पता n है छोड़ दिया है। हम इसलिए जानते हैं कि इसके दाएं उपट्री में पत्ती नोड्स की संख्या या तो _बाएं या एन - 1 छोड़ दिया गया है, और विशेष रूप से यह अधिकतर पर छोड़ दिया गया है।

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

• इस सबट्री में पत्र-गांठ की अधिकतम संख्या विषम है, तो संदिग्ध स्लॉट बाईं तरफ है, क्योंकि दाएं तरफ बाएं से भारी नहीं हो सकता है। यदि यह भी है, तो स्लॉट दाएं
• प्रत्येक सबबूट्री में पत्ती नोड्स की अधिकतम संख्या उप-रेखा में पत्ती नोड्स का आधा हिस्सा है, जो बाईं ओर गोलाकार है, दाईं ओर गोलाकार है।

जो इस मामले के दिल को हल करता है; बाकी सरल रिकर्सन है। सी ++ में:

#include <cstddef> 

// I'm using a simple node structure, you'd use query functions. The 
// algorithm is not meaningfully altered by this. 
struct node { 
    node *left = nullptr, *right = nullptr; 
}; 

struct node_counter { 
    std::size_t leaf;  // number of leaf nodes, 
    std::size_t trunk;  // number of trunk nodes, 
    std::size_t depth;  // and depth of the inspected subtree. 
}; 

// Interesting function #1: Given a right subtree and the leaf-count and 
// depth of its left sibling, find the node that might or might not be there 
node const *find_leaf(node const *branch, std::size_t leaf_count, std::size_t depth) { 
    // We've gone down, found the slot. Return it. 
    if(depth == 0) { return branch; } 

    // The heart of the matter: Step into the subtree that contains the 
    // questionable slot, with its maximum leaf node count and depth. 
    return find_leaf(leaf_count % 2 ? branch->left : branch->right, 
        (leaf_count + 1)/2, // int division 
        depth - 1); 
} 

// Recursive counter. This steps down on the left side, then infers the 
// number of leaf and trunk nodes on the right side for each level. 
node_counter count_nodes_aux(node const *root) { 
    // leftmost leaf node is reached. Return info for it. 
    if(!root->left) { 
    return { 1, 0, 0 }; 
    } 

    // We're in the middle of the tree. Get the counts for the left side, 
    auto ctr_left = count_nodes_aux(root->left); 

    // then find the questionable slot on the right 
    auto leaf_right = find_leaf(root->right, ctr_left.leaf, ctr_left.depth); 

    return { 
    // the number of leaf nodes in this tree is double that of the left 
    // subtree if the node is there, one less otherwise. 
    ctr_left.leaf * 2 - (leaf_right ? 0 : 1), 

    // And this is just an easy way to keep count of the number of non-leaf 
    // nodes and the depth of the inspected subtree. 
    ctr_left.trunk * 2 + 1, 
    ctr_left.depth + 1 
    }; 
} 

// Frontend function to make the whole thing easily usable. 
std::size_t count_nodes(node const *root) { 
    auto ctr = count_nodes_aux(root); 
    return ctr.leaf + ctr.trunk; 
} 

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

void fill_node(node *n) { 
    n->left = new node; 
    n->right = new node; 
} 

int main() { 
    node *root = new node; 

    fill_node(root); 

    fill_node(root->left); 
    fill_node(root->right); 

    fill_node(root->left->left); 
    fill_node(root->left->right); 
    fill_node(root->right->left); 
    fill_node(root->right->right); 

    fill_node(root->left->left->left); 
    fill_node(root->left->left->right); 
    fill_node(root->left->right->left); 
    fill_node(root->left->right->right); 
    fill_node(root->right->left->left); 
    fill_node(root->right->left->right); 
    fill_node(root->right->right->left); 
    fill_node(root->right->right->right); 

    std::cout << count_nodes(root) << std::endl; 

    root->left ->left ->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->right->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->right->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->right->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->right->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->left ->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->left ->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->left ->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->left ->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->right->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->right->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->right->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->right->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->right->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->right->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->right->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->right->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->left ->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->left ->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->left ->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->left ->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->right->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->right->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->right->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->right->right->right = new node; std::cout << count_nodes(root) << std::endl; 
}