फ़ाइल में शब्दों को गिनने के लिए इसी कार्यक्रम के साथ, एक साधारण बाइनरी पेड़ (यानी, बिना संतुलन के) को लागू करके प्रारंभ करें। वह काम कर लो, तो आपके पास परीक्षण करने के लिए कुछ होगा। अभी तक संतुलन के बारे में चिंता मत करो; यह वास्तव में कठिन हिस्सा है।
/*
* Insert a new key into a binary tree, or find an existing one.
*
* Return the new or existing node whose key is equal to the one requested.
* Update *node with the new (sub)tree root.
*/
Node *insert(Node **node, String key)
{
if (*node == NULL) {
*node = new Node(key);
return *node;
}
if (key < (*node)->key)
return insert(&(*node)->left, key);
if (key > (*node)->key)
return insert(&(*node)->right, key);
return *node;
}
एक बार जब आप एक सरल द्विआधारी पेड़ काम करने और परीक्षण किया है, प्रविष्टि समारोह संतुलन प्रदर्शन करने के लिए फिर से लागू है, जो का दिल है:
यहाँ एक सरल द्विआधारी पेड़ के लिए एक प्रविष्टि समारोह (untested) है एवीएल एल्गोरिदम।
मैं विकिपीडिया पर AVL tree insertion diagram का जिक्र करने की अनुशंसा करता हूं। यह चार घूर्णनों को दिखाता है जिन्हें आपको लागू करने की आवश्यकता होगी और जहां उनकी आवश्यकता है।
एक रोटेशन के लिए आवश्यक है जब एक नोड के संतुलन कारक दूसरे शब्दों में सीमा —, जब बाईं सबट्री और सही सबट्री के बीच ऊंचाई में अंतर से अधिक 1.
आप कैसे तय करते हैं है से बाहर चला जाता है एक नोड का संतुलन कारक? खैर, निम्न में से कोई काम करेगा:
- बाईं बच्चे की ऊंचाई से सही बच्चे की ऊंचाई को घटाकर की किसी भी नोड के संतुलन कारक नोड संरचना करने के लिए एक
height सदस्य जोड़ें, और निर्धारित करते हैं।
- नोड संरचना में
balance सदस्य जोड़ें। यह पता लगाने में थोड़ा मुश्किल हो सकता है, लेकिन यह सरल कोड उत्पन्न करता है (मुझे लगता है)।
- ट्रैवर्सल द्वारा वृक्ष की ऊंचाई और संतुलन की गणना करें।यह अक्षम है, इतना है कि यह एवीएल के उद्देश्य को हरा देता है। हालांकि, यह समझना आसान है और कम बग-प्रवण है।
मैं तीसरे दृष्टिकोण से शुरू करने की सलाह देता हूं, ताकि आप जल्द ही अपने संतुलन कोड का परीक्षण कर सकें।
स्पष्ट करने के लिए क्या "ऊंचाई" और "संतुलन कारक" का क्या मतलब है तो यहां उन्हें गणना करने के लिए कार्य हैं:
int height(Node *node)
{
if (node == NULL)
return -1;
return std::max(height(node->left), height(node->right)) + 1;
}
int balanceFactor(Node *node)
{
assert(node != NULL);
return height(node->right) - height(node->left);
}
इसके बारे में पता ऊंचाइयों या संतुलन कारकों संवर्द्धित कागज शामिल हो रहा है अद्यतन करने के लिए कैसे, पेंसिल , सरल बीजगणित, और सामान्य ज्ञान।
मुझे आशा है कि इससे मदद मिलती है!
आपको शायद 'निकालें' को लागू करने की आवश्यकता नहीं है। शब्दावली शब्द आवृत्ति का कार्य करने की आवश्यकता नहीं है। हालांकि, अपना असाइनमेंट जांचें। –
हटाएं, यह दिखाने के लिए कि एवीएल पेड़ कुछ जोड़ या हटाए जाने पर खुद को संतुलित कैसे करता है, सम्मिलित करने की आवश्यकता होती है। –
एवीएल पेड़ प्रति "संतुलन" नहीं करता है; 'डालने' और 'निकालें' फ़ंक्शन आवश्यकतानुसार संतुलन प्रदर्शन करते हैं। मेरे अनुभव से, 'निकालें' को लागू करना फिर से 'डालने' को लागू करने जैसा है, लेकिन कठिन है। यदि आपको वैसे भी 'हटाने' को लागू करने की आवश्यकता है, तो सुनिश्चित करें कि आपके पास इसका परीक्षण करने का कोई तरीका है। –