ढूँढना एक द्विआधारी ढेर

Question

Wikipedia के हवाले से पिछले तत्व:

यह पूरी तरह से एक द्विआधारी ढेर लागू करने के लिए एक पारंपरिक द्विआधारी पेड़ डेटा संरचना उपयोग करने के लिए स्वीकार्य है। वहाँ जब एक तत्व जो संकल्प लिया एल्गोरिदम रूप हो सकता है जोड़ने द्विआधारी ढेर पर पिछले स्तर पर आसन्न तत्व की खोज के साथ कोई समस्या ...

पर कैसे इस तरह के एक कोई भी विचार है एल्गोरिदम काम कर सकता है?

मुझे इस मुद्दे के बारे में कोई जानकारी नहीं मिली, क्योंकि ज्यादातर द्विआधारी ढेर एरे का उपयोग करके लागू किए जाते हैं।

किसी भी मदद की सराहना की।

---

हाल ही में, मैं एक OpenID खाता पंजीकृत है और मेरी प्रारंभिक पोस्ट को संपादित और न ही उत्तर टिप्पणी करने में सक्षम नहीं कर रहा हूँ है। यही कारण है कि मैं इस जवाब के माध्यम से जवाब दे रहा हूँ। इसके लिए क्षमा करें।

---

के हवाले से मिच गेहूं:

@Yse: यदि आपका प्रश्न "मैं एक द्विआधारी ढेर के अंतिम तत्व मिल रहा है"?

हाँ, यह है। या अधिक सटीक होने के लिए, मेरा प्रश्न है: "मैं गैर-सरणी-आधारित बाइनरी ढेर का अंतिम तत्व कैसे प्राप्त करूं?"।

Suppressingfire उद्धृत:

वहाँ कुछ संदर्भ में जो आप इस सवाल पूछ रहे है?

जैसा कि ऊपर कहा, (यानी, वहाँ कुछ ठोस समस्या आप की कोशिश कर रहे हल है?) मैं "एक गैर सरणी-आधारित द्विआधारी के अंतिम तत्व को खोजने के लिए एक अच्छा तरीका जानना चाहते हैं ढेर "जो नोड्स के सम्मिलन और हटाने के लिए आवश्यक है।

रॉय उद्धृत:

यह लिए मेरे लिए सबसे समझा जा रहा है सिर्फ एक सामान्य द्विआधारी पेड़ संरचना और (एक pRoot और नोड [डेटा, pLeftChild, pRightChild] के रूप में परिभाषित का प्रयोग करके) का उपयोग दो अतिरिक्त पॉइंटर्स जोड़ें (pInsertionNode और pLastNode)। PInsertionNode और पीएलएस्टएनोड दोनों को के दौरान सम्मिलन और विलोपन सबराउटिन के दौरान अपडेट किया जाएगा ताकि उन्हें डेटा चालू किया जा सके जब संरचना संरचना परिवर्तनों के भीतर हो।यह ओ (1) दोनों प्रविष्टि बिंदु और संरचना के अंतिम नोड तक पहुंच प्रदान करता है।

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

ज़ैक Scrivena उद्धृत:

कैसे गहराई-प्रथम खोज करने के बारे में ...

हाँ, यह एक अच्छा दृष्टिकोण होगा। मैं भी कोशिश करूँगा।

फिर भी मैं सोच रहा हूं, अगर अंतिम नोड और सम्मिलन बिंदु के स्थानों की "गणना" करने का कोई तरीका है। एन नोड्स के साथ एक बाइनरी ढेर की ऊंचाई को एन की तुलना में दो की छोटी शक्ति की लॉग (आधार 2) लेने के द्वारा गणना की जा सकती है। शायद गहरे स्तर पर नोड्स की संख्या की गणना करना संभव है। तो संभवतः यह निर्धारित करना संभव था कि कैसे ढेर को प्रविष्टि बिंदु या हटाने के लिए नोड तक पहुंचने के लिए पार किया जाना चाहिए।

Answer 1

एक depth-first search प्रदर्शन, सही बच्चे से पहले छोड़ दिया बच्चे का दौरा, पेड़ की ऊंचाई निर्धारित करने के लिए के बारे में कैसे। इसके बाद, आप जिस छोटे पत्ते को कम गहराई से सामना करते हैं, या एक लापता बच्चे के साथ माता-पिता का संकेत मिलता है कि आपको "बुलबुले अप" से पहले नया नोड कहाँ रखना चाहिए।

---

गहराई-पहले खोज (डीएफएस) दृष्टिकोण से ऊपर मान नहीं है कि आप पेड़ में नोड्स की कुल संख्या पता है। यदि यह जानकारी उपलब्ध है, तो हम "जूम-इन" जल्दी से वांछित जगह पर, पूरा द्विआधारी पेड़ के गुणों का उपयोग करके कर सकते हैं:

एन पेड़ में नोड्स की कुल संख्या होने दो , और एच पेड़ की ऊंचाई।

से कुछ मूल्यों (एन, एच) कर रहे हैं (1,0), (2,1), (3,1), (4,2), ..., (7.2) , (8, 3)। संबंधित दो है एच = प्लस्तर लगाना [log2 (एन +1)] सामान्य सूत्र - 1. अब, केवल एन को देखते हुए, हम नए नोड के लिए स्थिति को जड़ से पार करने के लिए चाहते हैं, कदम की कम संख्या, यानी किसी भी "बैक ट्रैकिंग" के बिना। हम पहले एक आदर्श द्विआधारी पेड़ में नोड्स की कुल संख्या एम गणना ऊंचाई की एच = प्लस्तर लगाना [log2 (एन +1)] - 1, जो एम = 2^(एच है +1) - 1.

तो एन == एम, तो हमारे पेड़ सही है, और नए नोड एक नए स्तर में जोड़ा जाना चाहिए।इसका मतलब यह है कि जब तक हम पहले पत्ते को हिट नहीं करते हैं, तब तक हम केवल एक डीएफएस (दाएं से पहले बाएं) कर सकते हैं; नया नोड इस पत्ते का बायां बच्चा बन जाता है। कहानी का अंत।

हालांकि, अगर एन < एम, तो अभी भी हमारे पेड़ के अंतिम स्तर में रिक्तियों रहे हैं, और नए नोड वाम-पंथी खाली जगह में जोड़ा जाना चाहिए। हमारे पेड़ के अंतिम स्तर पर पहले से मौजूद नोड्स की संख्या केवल (एन - 2^एच + 1) है। इसका मतलब है कि नया नोड स्पॉट एक्स = (एन - 2^एच + 2) बाईं ओर से अंतिम स्तर पर लेता है।

अब, रूट से वहां पहुंचने के लिए, आपको प्रत्येक स्तर पर सही मोड़ (एल बनाम आर) बनाना होगा ताकि आप अंतिम स्तर पर स्पॉट एक्स पर समाप्त हो जाएं। अभ्यास में, आप प्रत्येक स्तर पर थोड़ी गणना के साथ मोड़ निर्धारित करेंगे।

0 0 0 0 0 X 0 0 <--- represents the last level in our tree, X marks the spot! 
     ^
L L L L R R R R <--- at level 0, proceed to the R child 
L L R R L L R R <--- at level 1, proceed to the L child 
L R L R L R L R <--- at level 2, proceed to the R child 
     ^     (which is the position of the new node) 
      this column tells us 
      if we should proceed to the L or R child at each level 

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

Answer 2

असल में, उद्धृत बयान उद्धृत करने और ढेर से डेटा तत्वों को हटाने और हटाने के लिए स्थान को हल करने की समस्या को संदर्भित करता है। बाइनरी ढेर के "आकार की संपत्ति" को बनाए रखने के लिए, ढेर का निम्नतम स्तर हमेशा खाली नोड्स को छोड़कर बाएं से दाएं भरना चाहिए। द्विआधारी ढेर के लिए औसत ओ (1) सम्मिलन और हटाने के समय को बनाए रखने के लिए, आपको अगले प्रविष्टि के लिए स्थान और रूट नोड को हटाने के लिए निम्नतम स्तर पर अंतिम नोड का स्थान निर्धारित करने में सक्षम होना चाहिए, दोनों निरंतर समय में।

एक सरणी में संग्रहीत एक बाइनरी ढेर के लिए (विकिपीडिया प्रविष्टि में समझाया गया इसके अंतर्निहित, कॉम्पैक्ट डेटा संरचना के साथ), यह आसान है। सरणी के अंत में बस नवीनतम डेटा सदस्य डालें और फिर स्थिति में "बबल" करें (ढेर नियमों के बाद)। या हटाए जाने के लिए "बुलबुले डाउन" सरणी में अंतिम तत्व के साथ रूट को प्रतिस्थापित करें। सरणी भंडारण में ढेर के लिए, ढेर में तत्वों की संख्या एक अंतर्निहित सूचक है जहां अगला डेटा तत्व डाला जाना है और हटाने के लिए उपयोग करने के लिए अंतिम तत्व कहां मिलना है।

एक वृक्ष संरचना में संग्रहीत एक बाइनरी ढेर के लिए, यह जानकारी स्पष्ट नहीं है, लेकिन क्योंकि यह एक पूर्ण बाइनरी पेड़ है, इसकी गणना की जा सकती है। उदाहरण के लिए, 4 तत्वों के साथ एक पूर्ण द्विआधारी पेड़ में, सम्मिलन का बिंदु हमेशा रूट नोड के बाएं बच्चे का सही बच्चा होगा। हटाने के लिए उपयोग करने वाला नोड हमेशा रूट नोड के बाएं बच्चे का बायां बच्चा होगा। और किसी दिए गए मनमानी पेड़ के आकार के लिए, पेड़ हमेशा अच्छी तरह से परिभाषित सम्मिलन और हटाने के बिंदु के साथ एक विशिष्ट आकार होगा। चूंकि पेड़ किसी भी दिए गए आकार के लिए एक विशिष्ट संरचना के साथ "पूर्ण बाइनरी पेड़" है, इसलिए ओ (1) समय में सम्मिलन/हटाने के स्थान की गणना करना बहुत संभव है। हालांकि, पकड़ यह है कि यहां तक ​​कि जब आप जानते हैं कि यह संरचनात्मक रूप से कहां है, आपको पता नहीं है कि नोड स्मृति में कहाँ होगा। इसलिए, आपको दिए गए नोड को प्राप्त करने के लिए पेड़ को पार करना होगा जो एक ओ (लॉग एन) प्रक्रिया है जो सभी आवेषण और कम से कम ओ (लॉग एन) को हटा देता है, आमतौर पर वांछित ओ (1) व्यवहार को तोड़ देता है। किसी भी खोज ("गहराई-प्रथम", या कुछ अन्य) अर्ध-क्रमबद्ध ढेर की यादृच्छिक प्रकृति की वजह से ट्रैवर्सल मुद्दे के कारण कम से कम ओ (लॉग एन) होगा और आमतौर पर ओ (एन) होगा।

चाल करने के लिए दोनों गणना और संदर्भ उन प्रविष्टि/निरंतर समय में हटाए जाने के अंक या तो डेटा संरचना बढ़ाने (पेड़ "सूत्रण", विकिपीडिया लेख में उल्लेख के रूप में) या अतिरिक्त का उपयोग करके सक्षम होने के लिए है संकेत दिए गए।

कम स्मृति और अतिरिक्त कोडिंग ओवरहेड के साथ मुझे समझने के लिए सबसे आसान प्रतीत होता है, केवल सामान्य साधारण बाइनरी पेड़ संरचना का उपयोग करना है (एक पीआरयूटी और नोड का उपयोग करके [डेटा, पीपीरेंट, पीएलईएफटी चाइल्ड, pRightChild]) और दो अतिरिक्त पॉइंटर्स (पिंसर्ट और पीलास्ट नोड) जोड़ें। PInsert और pLastNode दोनों को सम्मिलन और हटाने के दौरान अद्यतन किया जाएगा, जब उन्हें संरचना में डेटा बदलता है तो उन्हें चालू रखने के लिए। यह कार्यान्वयन ओ (1) दोनों प्रविष्टि बिंदु और संरचना के अंतिम नोड तक पहुंच प्रदान करता है और दोनों प्रविष्टि और हटाने में समग्र ओ (1) व्यवहार के संरक्षण की अनुमति देनी चाहिए। कार्यान्वयन की लागत दो अतिरिक्त पॉइंटर्स और सम्मिलन/हटाना subroutines (उर्फ, न्यूनतम) में कुछ मामूली अतिरिक्त कोड है।

संपादित: एक ओ के लिए जोड़ा स्यूडोकोड (1) डालने()

यहाँ, एक डालने सबरूटीन जो हे (1) है के लिए छद्म कोड है औसतन:

define Node = [T data, *pParent, *pLeft, *pRight] 

void insert(T data) 
{ 
    do_insertion(data); // do insertion, update count of data items in tree 

    # assume: pInsert points node location of the tree that where insertion just took place 
    # (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process) 

    int N = this->CountOfDataItems + 1;  # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion 

    p = new Node(<null>, null, null, null);  // new empty node for the next insertion 

    # update pInsert (three cases to handle) 
    if (int(log2(N)) == log2(N)) 
     {# #1 - N is an exact power of two 
     # O(log2(N)) 
     # tree is currently a full complete binary tree ("perfect") 
     # ... must start a new lower level 
     # traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion 
     pInsert = pRoot; 
     while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; } # log2(N) iterations 
     p->pParent = pInsert; 
     pInsert->pLeft = p; 
     } 
    else if (isEven(N)) 
     {# #2 - N is even (and NOT a power of 2) 
     # O(1) 
     p->pParent = pInsert->pParent; 
     pInsert->pParent->pRight = p; 
     } 
    else 
     {# #3 - N is odd 
     # O(1) 
     p->pParent = pInsert->pParent->pParent->pRight; 
     pInsert->pParent->pParent->pRight->pLeft = p; 
     } 
    pInsert = p; 

    // update pLastNode 
    // ... [similar process] 
} 

तो, सम्मिलित करें (टी) औसत पर ओ (1) है: बिल्कुल ओ (1) सभी मामलों में जब पेड़ को एक स्तर से बढ़ाया जाना चाहिए जब यह ओ (लॉग एन) होता है, जो प्रत्येक लॉग एन प्रविष्टि होता है (कोई हटाना नहीं मानता) । एक और पॉइंटर (पीएलईएफटीओटीएलएफ़) के अलावा सभी मामलों के लिए डालने() ओ (1) डालने और पूर्ण सम्मिलन & पूर्ण पूर्ण बाइनरी पेड़ में हटाने के संभावित रोगजनक मामले से बचा जा सकता है। (PLeftmost जोड़ना एक अभ्यास के रूप में छोड़ा गया है [यह काफी आसान है]।)

Answer 3

अगर आपके माता-पिता का संदर्भ नहीं है तो समाधान !!! अगले नोड के लिए सही जगह खोजने के लिए आप को संभालने के लिए 3 मामलों है

• मामले (1) पेड़ स्तर पूरा log2 (एन)
• मामले (2) ट्री नोड गिनती भी है
• मामला है (3) ट्री नोड गिनती अजीब है

सम्मिलित:

void Insert(Node root,Node n) 
{ 
Node parent = findRequiredParentToInsertNewNode (root); 
if(parent.left == null) 
parent.left = n; 
else 
parent.right = n; 
} 

डालने के लिए आदेश में नोड के माता-पिता का पता लगाएं

void findRequiredParentToInsertNewNode(Node root){ 

Node last = findLastNode(root); 

//Case 1 
if(2*Math.Pow(levelNumber) == NodeCount){ 
    while(root.left != null) 
     root=root.left; 
    return root; 
} 
//Case 2 
else if(Even(N)){ 
    Node n =findParentOfLastNode(root ,findParentOfLastNode(root ,last)); 
return n.right; 
} 
//Case 3 
else if(Odd(N)){ 
    Node n =findParentOfLastNode(root ,last); 
return n; 
} 

} 

पिछले नोड आप एक BFS (चौड़ाई पहले खोज) करने की आवश्यकता को खोजने के लिए और कतार

Node findLastNode(Node root) 
{ 
    if (root.left == nil) 
     return root 

    Queue q = new Queue(); 

    q.enqueue(root); 
    Node n = null; 

    while(!q.isEmpty()){ 
     n = q.dequeue(); 
    if (n.left != null) 
     q.enqueue(n.left); 
    if (n.right != null) 
     q.enqueue(n.right); 
     } 
    return n; 
} 

में अंतिम तत्व मिल सेट करने के लिए पिछले नोड के माता-पिता का पता लगाएं नोड को हटाने के मामले में जड़ के साथ की जगह

Node findParentOfLastNode(Node root ,Node lastNode) 
{ 
    if(root == null) 
     return root; 

    if(root.left == lastNode || root.right == lastNode) 
     return root; 

    Node n1= findParentOfLastNode(root.left,lastNode); 
    Node n2= findParentOfLastNode(root.left,lastNode); 

    return n1 != null ? n1 : n2; 
} 

Answer 4

आप द्विआधारी ढेर के आकार के द्विआधारी प्रतिनिधित्व इस्तेमाल कर सकते हैं हे (लॉग एन) में पिछले नोड के स्थान खोजने के लिए मामले में शून्य पर। आकार को संग्रहीत और बढ़ाया जा सकता है जो ओ (1) समय लेगा। इसके पीछे मूलभूत अवधारणा बाइनरी पेड़ की संरचना है।

मान लीजिए कि हमारे ढेर का आकार 7 है। 7 का द्विआधारी प्रतिनिधित्व, "111" है।अब, हमेशा पहली बिट को छोड़ना याद रखें। तो, अब हम "11" के साथ छोड़ दिया गया है। बाएं से दाएं पढ़ें। बिट '1' है, इसलिए, रूट नोड के दाहिने बच्चे पर जाएं। फिर बाईं ओर स्ट्रिंग "1" है, पहला बिट '1' है। तो, फिर आप जिस नोड पर हैं, उसके सही बच्चे के पास जाएं। चूंकि अब आपके पास प्रक्रिया करने के लिए बिट्स नहीं हैं, यह इंगित करता है कि आप अंतिम नोड तक पहुंच गए हैं। तो, प्रक्रिया का कच्चा काम यह है कि, ढेर के आकार को बिट्स में परिवर्तित करें। पहली बिट छोड़ो। बाएं बिट के अनुसार, वर्तमान नोड के दाहिने बच्चे पर जाएं, यदि यह '1' है, और वर्तमान नोड के बाएं बच्चे को '0' है।

जैसा कि आप हमेशा बाइनरी पेड़ के बहुत अंत तक करते हैं, यह ऑपरेशन हमेशा ओ (लॉग एन) समय लेता है। यह अंतिम नोड खोजने के लिए एक सरल और सटीक प्रक्रिया है।

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

आशा है कि मेरे उत्तर ने आपकी मदद की है, अगर ऐसा हुआ, तो मुझे बताएं ...! ☺

Answer 5

स्टैक ओवरफ़्लो में भाग लेने के लिए मेरा पहला समय।

हां, ज़च स्क्रिप्वेना द्वारा उपर्युक्त उत्तर (भगवान मुझे नहीं पता कि अन्य लोगों को उचित रूप से कैसे संदर्भित किया जाए), सही है। अगर मैं नोड्स की गिनती देता हूं तो मैं जो जोड़ना चाहता हूं वह एक सरल तरीका है।

मूल विचार है:

को देखते हुए यह पूर्ण द्विआधारी पेड़ में नोड्स की गिनती एन, "एन% 2" गणना करते हैं और एक ढेर में परिणाम धक्का। एन == 1 तक गणना जारी रखें। फिर परिणामों को पॉप आउट करें। परिणाम 1 का मतलब सही है, 0 मतलब बाएं है। अनुक्रम रूट से लक्ष्य स्थिति का मार्ग है।

उदाहरण:

पेड़ अब 10 नोड्स है, मैं स्थिति 11. पर कैसे यह मार्ग के लिए एक और नोड सम्मिलित करना चाहते हैं?

11 % 2 = 1 --> right (the quotient is 5, and push right into stack) 
5 % 2 = 1 --> right (the quotient is 2, and push right into stack) 
2 % 2 = 0 --> left  (the quotient is 1, and push left into stack. End) 

फिर स्टैक पॉप करें: बाएं -> दाएं -> दाएं। यह रूट से पथ है।

Answer 6

मुझे पता है कि यह एक पुराना धागा है, लेकिन मैं एक ही प्रश्न का उत्तर ढूंढ रहा था। लेकिन मैं ओ (लॉग एन) समाधान करने का जोखिम नहीं उठा सका क्योंकि मुझे कुछ सेकंड में आखिरी नोड हजारों बार मिलना पड़ा। मेरे पास ओ (लॉग एन) एल्गोरिदम था लेकिन मेरा प्रोग्राम इस ऑपरेशन को करने की संख्या के कारण क्रॉल कर रहा था। तो बहुत सोचा के बाद मुझे अंततः इसके लिए एक फिक्स मिल गया। यकीन नहीं है कि अगर कोई चीज दिलचस्प है।

यह समाधान खोज के लिए ओ (1) है। सम्मिलन के लिए यह निश्चित रूप से ओ (लॉग एन) से कम है, हालांकि मैं यह नहीं कह सकता कि यह ओ (1) है।

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