बाइनरी खोज पेड़ में डुप्लिकेट प्रविष्टियों को खोजने की रणनीति

Question

मेरे पास एक बीएसटी है जिसमें डुप्लिकेट प्रविष्टियां हैं। मैं डुप्लिकेट प्रविष्टियों को खोजने की कोशिश कर रहा हूं। अब जाहिर है कि मैं एक गूंगा एल्गोरिदम लिख सकता हूं जो पूरे पेड़ को पार करता है, जो आसान है।

हालांकि, मैं एक और अधिक कुशल लिखना चाहता हूं। यहां मैंने जो किया है/मैंने अभी तक सोचा है:

निम्न पेड़ मानें।

 10 
    / \ 
    5 15 
    /\ /\ 
    2 8 10 16 
     \ \ 
     8 12 

अगर मैं अगर यह कोई अधिकार नहीं बच्चा है डुप्लिकेट खोजने के लिए, सभी 8 की, मैं पहले से 10 के बाईं सबट्री पर 8 मिलेगा खोजना चाहते हैं, यह होने जा रहा है सबसे बाईं ओर उस नोड (8) से बड़े पहले माता-पिता के दाएं-उप-भाग पर नोड? और अगर उसके पास सही बच्चा होता है, तो यह या तो अपने दाएं उपट्री के बाएं सबसे नोड में या बाएं उपट्री पर सबसे अधिक नोड सही हो सकता है?

क्या वे सभी मामले हैं, जिन्हें लूप और if-statement के समूह के साथ हासिल किया जा सकता है?

यदि नहीं, तो बेहतर दृष्टिकोण क्या है? क्या कोई मदद कर सकता है?

धन्यवाद

संपादित करें: असल में मैं सिर्फ महसूस किया कि यह "सबसे नोड छोड़ दिया" या "सही सबसे नोड" नहीं हो सकता। वह नोड पाएगा जो अगले उच्चतम मूल्य या पिछले सबसे कम मूल्य है। क्या यह पहले एक नोड होगा?

संपादित करें 2:

फिक्स्ड मेरी BST उदाहरण। यह निम्न प्रविष्टि विधि इस प्रकार है:

if (node == null) 
    return new NodeBST<Value>(name, value); 

if (node.key().compareTo(name) > 0) 
    node.setLeft(insert(node.left(), name, value));  
else 
    node.setRight(insert(node.right(), name, value)); 

इसका मतलब यह है डुप्लिकेट उनके डुप्लिकेट के अधिकार के लिए जोड़ दिया जाएगा .. है ना?

Answer 1

1. एक तत्व है कि हमेशा की तरह द्विआधारी पेड़ खोज कलन विधि का उपयोग अपने प्रमुख से मेल खाता है का पता लगाएं। यदि नहीं मिला, तो रुको।
2. एलएच उप-शाखा की जांच करें। यदि इसके प्रमुख मैच हैं, तो वर्तमान नोड बनाएं और इस चरण को दोहराएं।
3. अब आप उस कुंजी के साथ पेड़ में पहले तत्व पर हैं। अब चाबियाँ बराबर होती हैं, जबकि चाबियाँ बराबर होती हैं, यानी पाठक के लिए अभ्यास के रूप में छोड़े गए इस नोड, सही उप-पेड़, माता-पिता, माता-पिता का दायां उप-पेड़ आदि।

Answer 2

जो पेड़ आप दिखाते हैं वह पेड़ (अच्छी तरह से, कम से कम मुझे लगता है ... ;-)) जो बाईं ओर से कम है, और दाएं से अधिक हैं, क्या मैं सही हूँ?

तो दो चीजें आप विचार करना चाहिए:

1. आपका पेड़ गलत है! "10" सिर के दाईं ओर दूसरा "8" वहां नहीं हो सकता है, क्योंकि यह 10 से कम है। एक सही सम्मिलन, और एक सही संतुलन, दोनों "बहुत" पुनरावृत्ति पर सही नहीं होने पर बहुत करीबी हो जाएंगे "बाएं 8" से।

2. पेड़ को बाईं ओर "कम से कम या बराबर" के रूप में परिभाषित करके, और दाईं ओर "अधिक से अधिक", आपको वांछित परिणाम मिल जाएगा: सभी "8" को जंजीर कर दिया जाएगा एक साधारण प्रविष्टि पेड़ पर एक दूसरे के बाएं।

Answer 3

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

जो आपने खींचा है वह सख्ती से बीएसटी नहीं है, मैं गलत हो सकता हूं, लेकिन मेरा मानना ​​है कि यह बहुत टूटा हुआ है - बाएं पेड़ की सभी संख्या 10 से कम होनी चाहिए, और इसके विपरीत।

Answer 4

इस कार्यान्वयन पुनरावर्ती विधि का उपयोग करता है और डुप्लिकेट प्रविष्टियों

public class TreeNode<E> { 
    public int data; 
    public TreeNode left; 
    public TreeNode right; 
} 

public Integer[] findDuplicate(TreeNode tree) { 
    Map<Integer, Integer> entries = new HashMap<>(); 
    List<Integer> duplicates = new LinkedList<>(); 

    return (Integer[]) findDuplicate(tree, entries, duplicates); 
} 

private Integer[] findDuplicate(TreeNode tree, Map entries, List duplicates) { 
    if (tree == null) 
     return (Integer[]) duplicates.toArray(new Integer[] {}); 

    if (entries.containsKey(tree.data)) 
     duplicates.add(tree.data); 
    else 
     entries.put((int) tree.data, 1); 

    findDuplicate(tree.left, entries, duplicates); 
    findDuplicate(tree.right, entries, duplicates); 

    return (Integer[]) duplicates.toArray(new Integer[] {}); 
}