مواد

• موازنہ چارٹ
• بی ٹری کی تعریف
• آر ایم کے بی ٹری کی پراپرٹیز
• ثنائی درخت کی تعریف
• ٹراورسال تراکیب
• نتیجہ اخذ کرنا

بی ٹری اور بائنری ٹری غیر لکیری ڈیٹا ڈھانچے کی اقسام ہیں۔ اگرچہ شرائط یکساں نظر آتی ہیں لیکن تمام پہلوؤں میں مختلف ہیں۔ ثنائی کے درخت کا استعمال اس وقت کیا جاتا ہے جب ریکارڈ یا ڈیٹا کو ڈسک کے بجائے رام میں اسٹور کیا جاتا ہے کیونکہ ریم تک رسائی کی رفتار ڈسک سے کہیں زیادہ ہوتی ہے۔ دوسری طرف ، بی ٹری استعمال کیا جاتا ہے جب ڈیٹا کو ڈسک میں محفوظ کیا جاتا ہے تو اس سے درخت کی اونچائی کو کم کرکے اور نوڈ میں شاخوں میں اضافہ کرکے رسائی کا وقت کم ہوجاتا ہے۔

بی ٹری اور بائنری ٹری کے درمیان ایک اور فرق یہ ہے کہ بی ٹری کے پاس اپنے سارے بچے کے نوڈس ایک ہی سطح پر ہونے چاہئیں جبکہ بائنری ٹری میں ایسی رکاوٹ نہیں ہے۔ ایک بائنری درخت میں زیادہ سے زیادہ 2 ذیلی نری یا نوڈس ہوسکتے ہیں جبکہ بی ٹری میں ایم سب ٹری یا نوڈس کا M نمبر ہوسکتا ہے جہاں ایم بی ٹری کی ترتیب ہوتی ہے۔

1. موازنہ چارٹ
2. تعریف
3. کلیدی اختلافات
4. نتیجہ اخذ کرنا

موازنہ چارٹ

موازنہ کی بنیاد	بی ٹری	ثنائی درخت
لازمی رکاوٹ	نوڈ میں زیادہ سے زیادہ M تعداد میں بچے کے نوڈس ہوسکتے ہیں (جہاں M درخت کی ترتیب ہے)۔	نوڈ میں زیادہ سے زیادہ 2 سب ٹری کی تعداد ہوسکتی ہے۔
استعمال کیا جاتا ہے	جب ڈسک پر ڈیٹا ذخیرہ ہوتا ہے تو اس کا استعمال کیا جاتا ہے۔	جب استعمال کیا جاتا ہے جب ریکارڈ اور ڈیٹا رام میں رکھے جاتے ہیں۔
درخت کی اونچائی	لاگایم N (جہاں M M-Way درخت کی ترتیب ہے)	لاگ2 این
درخواست	بہت سے DBMS میں کوڈ انڈیکسنگ ڈیٹا ڈھانچہ۔	کوڈ کی اصلاح ، ہف مین کوڈنگ ، وغیرہ۔

بی ٹری کی تعریف

بی ٹری متوازن ایم وے درخت ہے اور متوازن ترتیب والے درخت کے طور پر بھی جانا جاتا ہے۔ یہ بائنری سرچ ٹری کی طرح ہے جہاں نوڈس کو انڈر ٹروراسل کی بنیاد پر منظم کیا جاتا ہے۔ بی ٹری کی خلائی پیچیدگی O (n) ہے۔ اضافے اور حذف کرنے میں وقت کی پیچیدگی O (log n) ہے۔

کچھ شرائط ہیں جو بی ٹری کے ل true درست ہونی چاہ:۔

• ہر ممکن حد تک درخت کی اونچائی کم سے کم رہنی چاہئے۔
• درخت کے پتے کے اوپر ، خالی ذیلی ندیوں کو نہیں ہونا چاہئے۔
• درخت کے پتے ایک ہی سطح پر آئیں گے۔
• تمام نوڈس میں چھٹی والے نوڈس کے سوا کم از کم تعداد میں بچوں کی تعداد ہونی چاہئے۔

آر ایم کے بی ٹری کی پراپرٹیز

• ہر نوڈ میں بچوں کی زیادہ سے زیادہ M تعداد اور بچوں کی کم از کم M / 2 تعداد یا 2 سے زیادہ سے زیادہ تعداد ہوسکتی ہے۔
• ہر نوڈ میں زیادہ سے زیادہ M-1 کیز والے بچوں سے ایک کلید کم ہوتی ہے۔
• چابیاں کا انتظام نوڈس کے اندر کچھ مخصوص ترتیب میں ہے۔ چابی کے بائیں طرف موجود سب ٹری میں موجود تمام چابیاں چابی کے پیش رو ہیں اور کلید کے دائیں طرف موجود اسے جانشین کہا جاتا ہے۔
• مکمل نوڈ ڈالنے کے وقت ، درخت دو حصوں میں تقسیم ہوجاتا ہے ، اور میڈین ویلیو والی کلید والدین کے نوڈ پر ڈالی جاتی ہے۔
• جب نوڈس کو حذف کر دیا جاتا ہے تو ضم کرنے کا عمل ہوتا ہے۔

ثنائی درخت کی تعریف

بائنری ٹری ایک درخت کی ساخت ہے جس میں اس کے بچے کے نوڈس کے لئے زیادہ سے زیادہ دو پوائنٹر ہوسکتے ہیں۔ اس کا مطلب یہ ہے کہ نوڈ کے پاس سب سے زیادہ ڈگری 2 ہے اور وہاں صفر یا ایک ڈگری نوڈ بھی ہوسکتا ہے۔

بائنری درخت کی کچھ مختلف قسمیں ہیں جیسے سختی سے بائنری ٹری ، مکمل بائنری ٹری ، توسیعی بائنری ٹری وغیرہ۔

• سختی سے بائنری ٹری ایک درخت ہے جہاں ہر نان ٹرمینل نوڈ کا ضمنی اور دائیں سب ٹری ہونا ضروری ہے۔
• جب درخت 2 ہونے کی حالت کو پورا کرتا ہے تو اسے ایک مکمل بائنری ٹری کہا جاتا ہے ^میں ہر سطح پر نوڈس جہاں میں سطح ہوں۔
• تھریڈڈ بائنری ایک بائنری درخت ہے جس میں نوڈس کے 0 نمبر یا نوڈس کی 2 تعداد ہوتی ہے۔

ٹراورسال تراکیب

درختوں کے اعداد و شمار کے ڈھانچے پر درختوں کی عبور ایک سب سے متواتر کاروائی ہے جس میں ہر نوڈ نے ایک مرتبہ باقاعدہ طور پر ایک مرتبہ دورہ کیا۔

• انڈرڈر- اس درخت کے پھٹنے میں بائیں ذیلی درخت کا بار بار دورہ کیا جاتا ہے پھر جڑ نوڈ ملاحظہ کیا جاتا ہے اور آخری دائیں حصے میں جاتا ہے۔
• پریورر - اس درخت کے محور میں جڑ کے نوڈ کو پہلے پھر بائیں سب ٹری اور آخری دائیں سب ٹری پر ملاحظہ کیا جاتا ہے۔
• پوسٹ آرڈر- یہ تکنیک بائیں سب ٹری پھر دائیں سب ٹری اور آخری روٹ نوڈ پر جاتی ہے۔

1. بی ٹری میں ، زیادہ سے زیادہ چائلڈ نوڈس جو نان ٹرمینل نوڈ ہوسکتے ہیں وہ ایم ہے جہاں ایم بی ٹری کی ترتیب ہے۔ دوسری طرف ، ایک ثنائی کے درخت میں زیادہ سے زیادہ دو ذیلی یا بچوں کے نوڈس ہوسکتے ہیں۔
2. بی ٹری کا استعمال اس وقت کیا جاتا ہے جب ڈیٹا کو ڈسک میں اسٹور کیا جاتا ہے جبکہ بائنری ٹری استعمال ہوتا ہے جب ڈیٹا کو رام جیسے تیز میموری میں اسٹور کیا جاتا ہے۔
3. بی ٹری کے لئے درخواست کا دوسرا شعبہ DBMS میں کوڈ انڈیکسنگ ڈیٹا ڈھانچہ ہے ، اس کے برعکس ، بائنری ٹری کوڈ آپٹیمائزیشن ، ہف مین کوڈنگ وغیرہ میں ملازمت کرتا ہے۔
4. بی-ٹری کی زیادہ سے زیادہ اونچائی لاگ ہے_ایمN (M درخت کی ترتیب ہے)۔ اس کے برعکس ، بائنری ٹری کی زیادہ سے زیادہ اونچائی لاگ ان ہے₂N (N نوڈس کی تعداد ہے اور بیس 2 ہے کیونکہ یہ بائنری کے لئے ہے)۔

نتیجہ اخذ کرنا

بی ٹری بائنری اور بائنری سرچ ٹریٹ کے اوپر استعمال ہوتا ہے اس کی سب سے بڑی وجہ میموری کی درجہ بندی ہے جہاں سی پی یو اعلی بینڈوتھ چینلز کے ساتھ کیشے سے جڑا ہوا ہے جبکہ سی پی یو کم بینڈوتھ چینل کے ذریعہ ڈسک سے جڑا ہوا ہے۔ ثنائی کے درخت کا استعمال اس وقت کیا جاتا ہے جب ریکارڈ (چھوٹے اور تیز) رام میں رکھے جاتے ہیں اور B-درخت استعمال ہوتے ہیں جب ریکارڈز ڈسک (بڑے اور آہستہ) میں محفوظ ہوجاتے ہیں۔ لہذا ، بائنری ٹری کے بجائے بی ٹری کے استعمال سے برانچنگ عنصر اور درخت کی اونچائی کم ہونے کی وجہ سے رسائی کا وقت نمایاں طور پر کم ہوجاتا ہے۔