सामग्री

• तुलना चार्ट
• बी-वृक्ष व्याख्या
• ऑर्डरच्या बी-ट्रीचे गुणधर्म एम
• बायनरी ट्री ची व्याख्या
• ट्रॅव्हर्सल तंत्रे
• निष्कर्ष

बी-ट्री आणि बायनरी ट्री हे रेखीय डेटा स्ट्रक्चरचे प्रकार आहेत. जरी अटी समान दिसत आहेत परंतु सर्वच बाबतीत ते भिन्न आहेत. जेव्हा रेकॉर्ड किंवा डेटा डिस्कऐवजी रॅममध्ये डेटा साठवला जातो तेव्हा बायनरी ट्री वापरली जाते कारण रॅमची प्रवेश गती डिस्कपेक्षा जास्त असते. दुसरीकडे, बी-ट्री वापरली जाते जेव्हा डेटा डिस्कमध्ये ठेवला जातो तेव्हा झाडाची उंची कमी करून आणि नोडमध्ये शाखा वाढवून प्रवेशाचा वेळ कमी होतो.

बी-वृक्ष आणि बायनरी झाडाचा आणखी एक फरक असा आहे की बी-वृक्षाला त्याच्या सर्व मुलांच्या नोड एकाच स्तरावर असणे आवश्यक आहे तर बायनरी झाडाला अशी मर्यादा नसते. बायनरीच्या झाडामध्ये जास्तीत जास्त 2 उपट्री किंवा नोड असू शकतात तर बी-ट्रीमध्ये एम उपगृहे किंवा नोड नसतात जेथे एम बी-वृक्षाची क्रमवारी असते.

1. तुलना चार्ट
2. व्याख्या
3. मुख्य फरक
4. निष्कर्ष

तुलना चार्ट

तुलना करण्यासाठी आधार	बी-वृक्ष	बायनरी ट्री
अत्यावश्यक अडचणी	एका नोडमध्ये जास्तीत जास्त एम संख्या असलेल्या चाइल्ड नोड्स असू शकतात (जेथे एम झाडाची क्रमवारी असते).	नोडमध्ये जास्तीत जास्त 2 उपशीर्षके असू शकतात.
वापरलेले	जेव्हा डिस्कवर डेटा संग्रहित केला जातो तेव्हा तो वापरला जातो.	रॅममध्ये रेकॉर्ड आणि डेटा संग्रहित केला जातो तेव्हा त्याचा वापर केला जातो.
झाडाची उंची	लॉगएम एन (जेथे मीटर हा एम-वे ट्रीचा क्रम आहे)	लॉग2 एन
अर्ज	बर्‍याच डीबीएमएस मधील कोडची अनुक्रमणिका डेटा रचना.	कोड ऑप्टिमायझेशन, हफमॅन कोडिंग इ.

बी-वृक्ष व्याख्या

ब-ट्री हा संतुलित एम-वे वृक्ष आहे आणि त्याला संतुलित सॉर्ट ट्री म्हणून देखील ओळखले जाते. हे बायनरी सर्च ट्रीसारखे आहे जिथे नोड्स इनऑर्डर ट्रॅव्हर्सलच्या आधारावर आयोजित केले जातात. बी-झाडाची स्पेस कॉम्प्लेक्सिटी ओ (एन) आहे. समाविष्ट करणे आणि हटविण्याची वेळ गुंतागुंत ओ (लॉग एन) आहे.

अशा काही अटी आहेत ज्या बी-ट्रीसाठी सत्य असणे आवश्यक आहे:

• झाडाची उंची शक्य तितक्या किमान असणे आवश्यक आहे.
• झाडाच्या पानांच्या वर, रिक्त उपशीर्षके नसावीत.
• झाडाची पाने एकाच पातळीवर येणे आवश्यक आहे.
• सर्व नोड्समध्ये लीव्ह नोड्स वगळता किमान मुलांची संख्या असावी.

ऑर्डरच्या बी-ट्रीचे गुणधर्म एम

• प्रत्येक नोडमध्ये जास्तीत जास्त मुले आणि कमीतकमी एम / 2 मुलांची संख्या किंवा 2 ते जास्तीत जास्त कोणतीही संख्या असू शकते.
• प्रत्येक नोडमध्ये जास्तीत जास्त एम -1 की असलेल्या मुलांपेक्षा एक की कमी असते.
• कीजची व्यवस्था नोड्समध्ये काही विशिष्ट क्रमाने असते. की च्या डाव्या बाजूला असलेल्या सबट्री मधील सर्व कीज किल्लीचे पूर्ववर्ती असतात आणि की च्या उजव्या बाजूला असलेल्या उत्तराधिकारी म्हणतात.
• पूर्ण नोड घालण्याच्या वेळी, झाडाचे दोन भाग होतात आणि पॅरेंट नोडवर मध्यम मूल्य असलेली की घातली जाते.
• नोड्स हटविले जातात तेव्हा विलीन ऑपरेशन होते.

बायनरी ट्री ची व्याख्या

बायनरी ट्री एक वृक्ष रचना आहे ज्यामध्ये मुलाच्या नोड्ससाठी जास्तीत जास्त दोन पॉईंटर्स असू शकतात. याचा अर्थ असा आहे की नोडची उच्चतम डिग्री 2 आहे आणि शून्य किंवा एक-डिग्री नोड देखील असू शकते.

बायनरी झाडाचे काही प्रकार आहेत जसे की काटेकोरपणे बायनरी ट्री, संपूर्ण बायनरी ट्री, विस्तारित बायनरी ट्री इ.

• काटेकोरपणे बायनरी ट्री एक असे झाड आहे जेथे प्रत्येक नॉन-टर्मिनल नोडमध्ये डावे सबट्री आणि उजवीकडे उपखंड असणे आवश्यक आहे.
• जेव्हा झाडाला 2 ठेवण्याची अट पूर्ण होते तेव्हा त्याला संपूर्ण बाइनरी ट्री म्हणतात ^मी मी स्तर आहे अशा प्रत्येक स्तरावरील नोड्स.
• थ्रेडेड बायनरी एक बायनरी ट्री आहे ज्यात एकतर 0 नोड किंवा 2 नोड असतात.

ट्रॅव्हर्सल तंत्रे

ट्री ट्रॅव्हर्सल हे वृक्ष डेटा रचनांवर केले जाणारे एक सर्वात वारंवार ऑपरेशन आहे ज्यात प्रत्येक नोड व्यवस्थित पद्धतीने एकदा भेट दिले.

• इनऑर्डर - या झाडाच्या आडवा भागात डावीकडील subtree वारंवार भेट दिली जाते त्यानंतर रूट नोडला भेट दिली जाते आणि शेवटच्या उजव्या subtree ला भेट दिली जाते.
• प्रीओरर - या झाडाच्या आडवा भागामध्ये रूट नोड प्रथम डावीकडील उपश्री आणि शेवटी उजवीकडील उपखंडात भेट दिली जाते.
• पोस्टऑर्डर- हे तंत्र डावीकडील subtree नंतर उजवीकडे सबट्री आणि अंतिम रूट नोडला भेट देते.

1. बी-ट्रीमध्ये, नॉन-टर्मिनल नोड असू शकतात अशा मुलाच्या नोड्सची जास्तीत जास्त संख्या एम असते जेथे एम बी-ट्रीची क्रमवारी असते. दुसरीकडे, बायनरीच्या झाडामध्ये जास्तीत जास्त दोन उप-ट्री किंवा चाइल्ड नोड असू शकतात.
2. जेव्हा डिस्क डिस्कमध्ये डेटा साठविला जातो तेव्हा बी-ट्री वापरली जाते, तर डेटा रॅम सारख्या वेगवान मेमरीमध्ये ठेवल्यास बायनरी ट्री वापरली जाते.
3. बी-ट्रीसाठी अर्जाचे आणखी एक क्षेत्र म्हणजे डीबीएमएस मधील कोड अनुक्रमणिका डेटा स्ट्रक्चर, त्याउलट, बायनरी ट्री कोड ऑप्टिमायझेशन, हफमॅन कोडिंग इ. मध्ये कार्यरत आहे.
4. बी-झाडाची जास्तीत जास्त उंची लॉग आहे_एमएन (एम झाडाचा क्रम आहे). त्याउलट, बायनरी ट्रीची कमाल उंची लॉग आहे₂एन (एन ही नोडची संख्या आहे आणि बेस 2 आहे कारण तो बायनरीसाठी आहे).

निष्कर्ष

बी-ट्री बायनरी आणि बायनरी सर्च ट्रीवर वापरली जाते यामागील मुख्य कारण म्हणजे मेमरी श्रेणीबद्धता जेथे सीपीयू उच्च बँडविड्थ चॅनेलसह कॅशेशी जोडलेले आहे तर सीपीयू लो बँडविड्थ चॅनेलद्वारे डिस्कवर कनेक्ट केलेले आहे. रेकॉर्ड (लहान आणि वेगवान) मध्ये रेकॉर्ड ठेवल्यास बायनरी ट्री वापरली जाते आणि जेव्हा रेकॉर्ड डिस्कमध्ये (मोठ्या आणि स्लो) संचयित केल्या जातात तेव्हा बी-ट्री वापरली जाते. म्हणून, बायनरी ट्रीऐवजी बी-वृक्षाचा वापर केल्यामुळे उच्च शाखांचा घटक आणि झाडाची उंची कमी झाल्यामुळे प्रवेशाचा वेळ लक्षणीय प्रमाणात कमी होतो.