[Powered by Google Translate] آپ کو ایک کمپیوٹر میں کس طرح آپ کے تمام خاندان کے اراکین کو کی نمائندگی کریں گے؟ ہم نے ایک فہرست صرف اسے استعمال کر سکتے ہیں، لیکن وہاں ایک واضح تنظیمی ڈھانچے یہاں ہے. 

چلو کا کہنا ہے کہ ہم آپ کی عظیم دادی، یلس کے ساتھ شروع کر رہے ہیں. انہوں نے 2 بیٹوں، باب ہے اور آپ کے دادا، چارلی. چارلی 3 بچے ہیں، تمہارے چاچا، ڈیو، تمہاری چاچی، ئو، اور آپ کے والد، فریڈ. آپ فریڈ کی اکلوتی اولاد ہیں. 

آپ کے خاندان کے اراکین کو اس طرح سے کیوں کی تنظیم کریں گے سادہ فہرست کی نمائندگی سے بہتر ہو؟ ایک وجہ یہ ہے کہ یہ پدانکردوست ساخت، کے نام سے 'درخت' ایک سادہ فہرست سے مزید معلومات پر مشتمل ہے. ہم سب کے درمیان خاندانی تعلقات کو جانتا ہوں درخت کا معائنہ کرتے ہوئے. اس کے علاوہ، یہ رفتار تیز کر سکتے ہیں بہت وقت نظر اپ، اگر درخت اعداد و شمار کے مطابق ہے. 

ہم یہاں فائدہ اٹھانے نہیں، لیکن کر سکتے ہیں ہم اس کی ایک مثال دیکھ جلد ہی کریں گے. ہر شخص درخت پر ایک نوڈ کی طرف سے ظاہر کیا جاتا ہے. نوڈس بچے نوڈس کر سکتے ہیں کے ساتھ ساتھ والدین نوڈ کے طور پر. یہ تکنیکی اصطلاحات ہیں، خاندانوں کے علاوہ چیزوں کے لئے اس وقت بھی جب درخت کا استعمال کرتے ہوئے. یلس نوڈ 2 بچوں اور کوئی والدین نہیں ہیں، جبکہ چارلی نوڈ 3 بچوں اور والدین 1 ہے. 

پتی کی نوڈ ایک ہے کہ کسی بھی بچے نہیں ہے درخت سے باہر کنارے پر. درخت کے اوپر نوڈ، جڑ نوڈ، کوئی والدین ہے. 

ایک بائنری درخت درخت کی ایک مخصوص قسم ہے، جس میں ہر نوڈ زیادہ سے زیادہ ہے،، 2 بچے. سی میں ایک بائنری درخت کی نوڈ کے struct ہے ہر نوڈ کو کچھ اس کے ساتھ وابستہ ڈیٹا ہے اور دوسرے نوڈس 2 اشارہ. 

ہمارے خاندان ورکش میں، مربوط ڈیٹا ہر ایک شخص کا نام تھا. یہاں یہ ایک int ہے، اگرچہ اس میں کچھ بھی ہو سکتا ہے. کے طور پر یہ پتہ چلتا ہے، ایک بائنری درخت کے خاندان کے لئے ایک اچھا نمائندگی نہیں کریں گے، کے بعد سے لوگوں کو اکثر 2 سے زائد بچے ہیں. 

ایک بائنری تلاش درخت بائنری کے درخت کی ایک خصوصی، منظم قسم ہے ہے کہ ہمیں اقدار میں فوری طور پر تلاش کرنے کی اجازت دیتا ہے ہے. آپ نے محسوس کیا ہو سکتا ہے کہ ایک درخت کی جڑ سے نیچے ہر نوڈ ہے کسی اور درخت کی جڑ، قرار دیا 'subtree. یہاں درخت کی جڑ 6 ہے، اور اس کے بچے، 2، ایک subtree کی جڑ ہے. 

ایک بائنری تلاش درخت میں ایک نوڈ کے تمام اقدار کو درست subtree ہے نوڈ قیمت سے زیادہ ہے. یہاں: 6. ٹھیک ہے، ایک نوڈ کے بائیں subtree میں اقدار نوڈ قیمت سے بھی کم وقت ہے. اگر ہم نقل اقدار کو ہینڈل کرنے کی ضرورت ہے، ہم ڑیلی عدم مساوات یا تو ان میں سے تبدیل کر سکتے ہیں، مطلب جیسی اقدار کو بائیں یا دائیں یا تو گر کر سکتے ہیں، جب تک ہم بھر میں اس کے بارے میں مسلسل ہیں. یہ درخت بائنری تلاش درخت ہے کیونکہ یہ ان قوانین مندرجہ ذیل ہیں. 

اس کا یہ ہے کہ یہ کس طرح دیکھو، اگر ہم C structs میں تمام مراکز دیا گی. کہ اگر کوئی بچہ غائب ہے، نوٹس پوائنٹر شہوت انگیز null ہے. ہم اگر 7 درخت میں ہے دیکھنے کے لئے کیسے چیک کر سکتا ہوں؟ ہم جڑ میں شروع ہو جاتے ہیں. سات 6 سے بڑھ کر ہے، اس لئے اگر یہ درخت میں ہے، اسے درست ہونا ضروری ہے. اس کے بعد، یہ 8 سے بھی کم ہے، تو اسے چھوڑ رکھا جائے ضروری ہے. یہاں، ہم 7 مل گیا ہے. اب، ہم نے 5 کے لئے چیک کرنے کے لیے کریں گے. پانچ 6 سے کم ہے، تو اس کے بائیں طرف ہونا چاہیے. پانچ 2 سے بڑا ہے، تو اس کا حق ہونا چاہیے، اور یہ بھی 4 سے بڑھ کر ہے، تو یہ درست ہے پھر ہونا چاہیے. تاہم، کوئی بھی بچہ یہاں ہے. پوائنٹر شہوت انگیز null ہے. اس کا مطلب یہ ہے کہ ہمارے درخت میں 5 نہیں ہے. 

ہم نے مندرجہ ذیل کوڈ کے ساتھ بائنری درخت کو تلاش کر سکتے ہیں: ہر نوڈ میں، ہم اگر ہم نے محسوس کیا ہے دیکھنا چیک کرنے کے لیے قدر ہم تلاش کر رہے ہیں. اگر ہم اسے تلاش نہیں کرتے، ہم یہ تعین تو ہونا چاہئے بائیں یا دائیں اور subtree چیک کرنے کے لیے. یہ لوپ نیچے درخت جاری رہے گا تک کوئی بچہ یا تو بائیں یا دائیں نوڈ ہے. 

یاد رکھیں کہ 5 درخت میں نہیں تھا. ہم اس سے کس طرح داخل ہے؟ عمل کی تلاش اسی طرح لگتا ہے. ہم نے 6 سے شروع ہونے والے درخت iterate، 2 چھوڑ 4 کا حق اور پھر، لیکن 4 اس طرف کوئی بچے نہیں ہے. اس 5 کے لئے نئے پوزیشن ہو جائے گا، اور یہ کسی بھی بچوں کے ساتھ شروع کر دیں گے. 

روزہ کس طرح ایک بائنری تلاش کے پیڑ پر آپریشن کیا ہیں؟ یاد رکھیں کہ ایک بالائی جانے Bigohnotation فراہم کرنے کی کوشش کی ہے. بدترین صورت میں، ہمارے درخت سے منسلک فہرست صرف ہو سکتا ہے اس اندراج، تنسیخ، اور تلاش کا مطلب درخت میں مراکز کی تعداد کے متناسب وقت لگ سکتا ہے. یہ O (ن) کے ہے. 

مثال کے طور پر، مندرجہ ذیل ایک درست بائنری تلاش درخت ہے. تاہم، اگر ہم 9 تلاش کرنے کی کوشش کرتے ہیں، ہم ہر نوڈ گزرنا ہے. یہ ایک لنک کی فہرست سے بہتر ہے. مثالی طور پر، ہم نے ہر نوڈ چاہتا ہمارے بائنری تلاش کے درخت کی 2 بچے ہیں. اس طرح، اندراج کی منسوخی، اور تلاش لے، میں سب سے زیادہ، O (لاگ ان ن) وقت گی. درخت پہلے سے زیادہ متوازن ہو سکتا ہے، اس طرح. اب، زیادہ سے زیادہ کوئی قیمت لگ لیتا ہے،، 3 اقدامات. یہ درخت متوازن ہے، کا مطلب یہ ہے کہ کم سے کم گہرائی ہے مراکز کی تعداد میں. 

کی تلاش میں ایک متوازن بائنری تلاش درخت میں ایک کی قیمت کے لئے کے مطابق صف پر بائنری تلاش کے لئے اسی طرح کی ہے. اصل میں، اگر ہم اشیاء کو داخل یا خارج کرنے کی ضرورت نہیں ہے، انہوں نے بالکل اسی طرح برتاؤ کرتے ہیں. تاہم، ایک درخت کا ڈھانچہ بہتر ہے ہینڈلنگ کے اضافے اور حذف کے لئے 

میرا نام Bannus وین ڈیر Kloot ہے. یہ CS50 ہے.