बाइनरी पेड़ से डुप्लिकेट हटाएं - एल्गोरिदम, भाषा-अज्ञेयवादी, पेड़, बाइनरी-पेड़

Im एक बाइनरी ट्री / बाइनरी सर्च ट्री से डुप्लिकेट को हटाने के लिए एक एल्गोरिथम के साथ आने की कोशिश कर रहा है। अब तक सबसे अच्छा मैं साथ आ सकता था

एक सरणी में ट्री के इनवर्टर ट्रैवर्सल को स्टोर करें।
यदि पेड़ के पास कोई ऑर्डर नहीं है, तो सरणी को क्रमबद्ध करें।
सरणी से डुप्लिकेट निकालें और बाइनरी ट्री को फिर से बनाएँ।

क्या हमें पेड़ के पुनर्निर्माण के साथ-साथ पेड़ के पूर्व क्रम को संग्रहीत करने की आवश्यकता है?

यह जटिलता डालता है O(n log n ) समय और O(n) अंतरिक्ष। क्या हम बेहतर कर सकते हैं? छद्म कोड / कोड के नमूने की सराहना की जाएगी

EDIT 1: मान लें कि बाइनरी ट्री की संरचना निम्नलिखित ऑब्जेक्ट द्वारा दी गई है

public class Node
{
int data;
Node right;
Node left;
// getters and setters for the left and right nodes
}

उत्तर:

जवाब के लिए 2 № 1

द्विआधारी खोज ट्री के लिए डुप्लिकेट एल्गोरिथ्म निकालें:

1. ट्री वॉक प्रारंभ करें (/ पूर्व / पोस्ट ऑर्डर में)

2. प्रत्येक नोड पर, नोड में संग्रहीत कुंजी मूल्य के लिए उस नोड पर निहित सबट्री पर एक द्विआधारी खोज करें।

   यदि कुंजी मान पेड़ के नीचे पाया जाता है, तो कॉल हटाएं (कुंजी) और चरण 2 को पुनरारंभ करें (हो सकता है कि कई डुप्लिकेट हों)।

   चरण 2 को तब तक दोहराएं जब तक कि उप पेड़ में कुंजी न मिल जाए। फिर चरण 1 पर वापस जाएं

समय जटिलता - O(nlogn) (प्रत्येक के लिए n तत्व एक द्विआधारी खोज करते हैं जो लेता है logn पहर)

अंतरिक्ष जटिलता - O(logn) (पुनरावृत्ति में प्रयुक्त स्टैक स्पेस के लिए)

---

जवाब के लिए 0 № 2

मेरे पास एक अजीब विचार है:

यदि आपके पास पहले से डुप्लिकेट वाला एक पेड़ है और डुप्लिकेट के बिना नया बनाने की आवश्यकता है तो आप बस कर सकते हैं:

1. नोड मानों का खाली हैशमैप बनाएं
2. नया पेड़ बनाएँ
3. किसी भी क्रम में मौजूदा पेड़ को पार करें और एक-एक करके तत्व प्राप्त करें
4. यदि तत्व पहले से ही हैश मैप में मौजूद है, तो इसे नए में न जोड़ें पेड़

ठीक है न?)

---

जवाब के लिए 0 № 3

अपनी समस्या के लिए प्रस्तावित पुनरावर्ती समाधान: -

deleteDup(Node p) {

if(p == NULL) return

else {

deleteDup(p.left)
deleteDup(p.right)
delete(p.value,p.left)
delete(p.value,p.right)

}

}

deleteDup(root)

समय जटिलता:

बीएसटी में विलोपन = O(logN)

T(N) = 2T(N/2) + O(logN)
T(N) = O(N)

अंतरिक्ष जटिलता: O(logN)

ध्यान दें:- संतुलित BST मानकर

---

जवाब के लिए 0 № 4

मेरा एक और विचार था जो O (n) समय और O (n) स्पेस में चलता है। उदाहरण के लिए, हमारे पास जड़ A और दो बच्चों A और B के साथ एक पेड़ है। ए अ ब

1. एक मैप काउंट बनाएं जो ट्री में प्रत्येक मान को एक काउंट में मैप करता है।
2. गिनती करने के लिए पेड़ में सभी तत्वों को पार करें। हमें काउंट्स [A] = 2 और काउंट्स [B] = 1 मिलेंगे। इसमें O (n) स्थान और O (n) समय लगता है।
3. फिर से, पेड़ में सभी तत्वों को पार करें। प्रत्येक तत्व के लिए, जांचें कि क्या मायने रखता है [तत्व]> 1 और यदि हां, तो हम गणना करते हैं [तत्व] - और उस तत्व को हटा दें (बाइनरी ट्री विलोपन / रोटेशन का उपयोग करके) यह O (n) समय है।
4. एक बार हो जाने के बाद, पेड़ के पास और कोई डुप्लिकेट नहीं है!

---

उत्तर के लिए -1 № 5

इस स्थिति में ट्रिक यह है कि डुप्लिकेट को स्टोर करने के लिए शुरू न करें ...।

जब आप पेड़ में नोड्स जोड़ते हैं तो "आप पहले से ही पेड़ में डुप्लिकेट होने पर नोड को नहीं जोड़ने का निर्णय क्यों कर सकते हैं?"

---