प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

द्विचक्रीयवृक्षः एकः महत्त्वपूर्णः दत्तांशसंरचना अस्ति यस्मिन् नोड्स् भवन्ति, प्रत्येकं नोड् अधिकतमं द्वौ बालनोडौ भवतः । केषुचित् सन्दर्भेषु तस्य सर्वाणि नोड्स् द्रष्टुं द्विचक्रीयवृक्षस्य भ्रमणं कर्तव्यम् । परन्तु असन्तुलितद्विचक्रीयवृक्षेषु साधारणपरिभ्रमणविधिभिः अदक्षताः उत्पद्यन्ते । एतस्याः समस्यायाः समाधानार्थं वयं "threading" इति तन्त्रस्य उपयोगं कृत्वा traversal process इत्यस्य अनुकूलनं कर्तुं शक्नुमः ।

1. द्विचक्रीयवृक्षसूत्रीकरणं किम् ?

द्विचक्रीयवृक्षसूत्रीकरणं द्विचक्रीयवृक्षस्य सूत्रितद्विचक्रीयवृक्षे परिवर्तनस्य प्रक्रियां निर्दिशति । सुराग द्विचक्रीयवृक्षः मूलद्विचक्रीयवृक्षे द्वौ सूचकौ योजयति: ltag तथा rtag, ये क्रमशः वामबालस्य दक्षिणबालस्य च पूर्ववर्तीं उत्तराधिकारीं च सूचयन्ति एतेन क्रमेण, पूर्वक्रमेण, क्रमोत्तरं च सुलभं भ्रमणं भवति ।

2. द्विचक्रीयवृक्षाणां थ्रेडिंग् कथं कार्यान्वितम् ?

1. मध्य-अनुक्रमसूत्रीकरणम्

क्रमान्तर-अनुक्रमण-अल्गोरिदम् परिवर्त्य क्रमेण सूत्रीकरणं भवति । यदा नोड् अभिगम्यते तदा वयं नोड् इत्यस्य पूर्ववर्ती नोड् इत्यस्य च मध्ये clue information संयोजयामः । विशिष्टानि पदानि निम्नलिखितरूपेण सन्ति ।

• वर्तमानं आगतस्य नोड् इत्यस्य पूर्ववर्ती नोड् अभिलेखनार्थं उपयुज्यमानं सूचकं pre आरभत ।
• द्विचक्रीयवृक्षे प्रत्येकं नोडं भ्रमन्तु, प्रत्येकस्य नोडस्य कृते:
  • यदि प्रथमः नोड् गतः अस्ति तर्हि तस्य lchild pre इति सेट् भवति तथा ltag 1 इति सेट् भवति ।
  • यदि तस्य पूर्ववर्ती नोड् निर्धारितः अस्ति (अर्थात् pre रिक्तं नास्ति), तर्हि तस्य rchild pre इति सेट् भवति तथा rtag 1 इति सेट् भवति ।
  • वर्तमान नोड् मध्ये pre अद्यतनं कुर्वन्तु ।

1. पूर्वादेश cueing

पूर्व-आदेश-सूचना-मध्य-क्रम-सूचना-विचाराः समानाः सन्ति, परन्तु प्रेम-बिन्दु-जादू-वृत्तस्य समस्यायां भवद्भिः ध्यानं दातव्यम् । यदा ltag=0 भवति तदा वाम उपवृक्षः पूर्वक्रमेण सूचयितुं शक्यते । विशिष्टानि पदानि निम्नलिखितरूपेण सन्ति ।

• वर्तमानं आगतस्य नोड् इत्यस्य पूर्ववर्ती नोड् अभिलेखनार्थं उपयुज्यमानं सूचकं pre आरभत ।
• द्विचक्रीयवृक्षे प्रत्येकं नोडं भ्रमन्तु, प्रत्येकस्य नोडस्य कृते:
  • यदि प्रथमः नोड् गतः अस्ति तर्हि तस्य lchild pre इति सेट् भवति तथा ltag 1 इति सेट् भवति ।
  • यदि तस्य पूर्ववर्ती नोड् निर्धारितः अस्ति (अर्थात् pre रिक्तं नास्ति), तर्हि तस्य rchild pre इति सेट् भवति तथा rtag 1 इति सेट् भवति ।
  • वर्तमान नोड् मध्ये pre अद्यतनं कुर्वन्तु ।
  • यदि ltag=0 अस्ति तर्हि वाम उपवृक्षे पूर्वक्रमसूत्रीकरणं पुनरावर्तनीयरूपेण क्रियते ।

1. आदेशोत्तर सुराग

Postorder threading अपि तथैव विचारस्य अनुसरणं करोति, परन्तु अन्तिमस्य नोड् इत्यस्य rchild तथा rtag इत्येतयोः संसाधने विशेषं ध्यानं दातव्यम् । विशिष्टानि पदानि निम्नलिखितरूपेण सन्ति ।

• वर्तमानं आगतस्य नोड् इत्यस्य पूर्ववर्ती नोड् अभिलेखनार्थं उपयुज्यमानं सूचकं pre आरभत ।
• द्विचक्रीयवृक्षे प्रत्येकं नोडं भ्रमन्तु, प्रत्येकस्य नोडस्य कृते:
  • यदि प्रथमः नोड् गतः अस्ति तर्हि तस्य lchild pre इति सेट् भवति तथा ltag 1 इति सेट् भवति ।
  • यदि तस्य पूर्ववर्ती नोड् निर्धारितः अस्ति (अर्थात् pre रिक्तं नास्ति), तर्हि तस्य rchild pre इति सेट् भवति तथा rtag 1 इति सेट् भवति ।
  • वर्तमान नोड् मध्ये pre अद्यतनं कुर्वन्तु ।
  • यदा अन्तिमः नोड् सम्मुखीभवति तदा तस्य rchild pre इति सेट् भवति तथा rtag 1 इति सेट् भवति ।

3. त्रुटिप्रवणबिन्दवः

द्विचक्रीयवृक्षसूत्रीकरणं कार्यान्वितुं प्रक्रियायां निम्नलिखिताः केचन सामान्याः त्रुटिप्रवणाः बिन्दवः सन्ति ।

1. अन्तिमस्य नोडस्य rchild तथा rtag इत्येतयोः विशेषः उपचारः उपेक्षितः भवति ।
2. पूर्व-आदेश-सूत्रीकरण-प्रक्रियायां प्रेम-बिन्दु-जादू-वृत्तस्य समस्या सम्यक् न निबद्धा ।
3. सूचकः pre सम्यक् आरम्भः अथवा अद्यतनः न भवति ।

4. सारांशः

द्विचक्रीयवृक्षसूत्रीकरणं भ्रमणरणनीतयः अनुकूलनार्थं प्रभावी पद्धतिः अस्ति । अतिरिक्तसूचकाः योजयित्वा, traversal algorithm परिवर्त्य च वयं द्विचक्रीयवृक्षे सर्वाणि नोड्-आणि अधिकतया अभिगन्तुं शक्नुमः । व्यावहारिकप्रयोगेषु अस्माभिः उपरि उल्लिखितानां केषाञ्चन सामान्यदोषाणां परिहाराय ध्यानं दातव्यं यत् संहितायां सम्यक्त्वं स्थिरतां च सुनिश्चितं भवति ।