سرخ سیاہ درخت کا تعارف


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے ایمیزون کوڈ نیشن فیس بک گوگل Uber
اعلی درجے کی ڈیٹا سٹرکچر ثنائی تلاش درخت ثنائی درخت ڈیٹا سٹرکچر درخت

ریڈ بلیک ٹری ایک خود توازن بائنری درخت ہے۔ اس درخت میں ، ہر نوڈ یا تو ایک سرخ نوڈ یا کالا نوڈ ہوتا ہے۔ اس سرخ - درخت کے تعارف میں ، ہم کوشش کریں گے کہ اس کی سبھی بنیادی خصوصیات کا احاطہ کیا جائے۔

سرخ رنگ کے درخت کی خصوصیات

  1. ہر نوڈ کو سرخ یا سیاہ رنگ کی نمائندگی کی جاتی ہے۔
  2. جڑ نوڈ ہمیشہ سیاہ ہوتا ہے۔
  3. سرخ نوڈ میں سرخ والدین یا سرخ بچہ نہیں ہوسکتا (یعنی کوئی دو سرخ نوڈس ملحق نہیں ہیں)۔
  4. کسی بھی نوڈ سے اس کے NIL اولاد تک ہر راستے میں مساوی تعداد میں کالا نوڈس ہونا چاہئے۔

سرخ - سیاہ درخت کی درست اور غلط مثالیں

سرخ سیاہ درخت کا تعارف

سرخ سیاہ درخت کا تعارف

وقت کی پیچیدگی کا تجزیہ

بی ایس ٹی کے تمام کام جیسے تلاش ، اندراج ، حذف کرنا ، او (ح) وقت میں انجام دیئے جاسکتے ہیں ، جہاں سرخ رنگ کے درخت کی اونچائی ہوتی ہے ، اور متوازن بی ایس ٹی کے لئے اونچائی ہمیشہ ترتیب کی ہوتی ہے لاگ (این) [n-> نوڈس کی تعداد]۔

تلاش = O (لاگ (ن))
اندراج = O (لاگ (ن))
منسوخی = O (لاگ (ن))

سرخ بلیک ٹری میں بلیک اونچائی

کسی سرخ نوکدار درخت میں بلیک اونچائی کی وضاحت اس سیدھے راستے پر کالے نوڈس کی تعداد کے طور پر کی گئی ہے۔ اس کی نمائندگی bh (x) کرتی ہے۔

سرخ سیاہ درخت کی اونچائی

کے برعکس AVL درخت ، اونچائی توازن اتنا سخت نہیں ہے ، لیکن سرخ سیاہ درختوں میں ، گردش کی تعداد AVL درختوں کے مقابلے میں کم ہے۔
سرخ رنگ کے درخت کی اونچائی <<2 (لاگ (n + 1)) log لاگ کی بنیاد 2} تفصیلی ہے ثبوت RB درختوں کی اونچائی کیوں <= 2 لاگ (n + 1) ہے۔

اونچائی میں توازن برقرار رکھنے کے لئے سرخ رنگ کا ایک درخت رنگینی اور تنظیم نو کا استعمال کرتا ہے۔

آپ دیکھ سکتے ہیں کہ آر بی کے درخت کیسے خود کو دوبارہ رنگ لیتے ہیں اور تنظیم نو کرتے ہیں یہاں.

بازیافت

اس سے مراد کچھ سرخ نوڈس کا رنگ سیاہ اور اس کے برعکس ہوجاتا ہے ، یہ جب بھی سرخ نوڈ کے سرخ والدین کا بھائی لال ہوتا ہے تو کیا جاتا ہے۔

سرخ سیاہ درخت کا تعارف

 

بحالی

اس سے مراد درخت کی گردش ہوتی ہے ، یہ تب بھی ہوتا ہے جب کسی سرخ بچے کے سرخ والدین اور سیاہ یا کالے یا چچا چچا ہوتے ہیں۔ تنظیم نو میں چار معاملات ہیں ،

  • اس وقت
  • چھوڑ دیا
  • دائیں بائیں
  • بائیں دائیں

درخواستیں

  • خود توازن BSTs کو نافذ کرنے کے لئے حقیقی دنیا کی لائبریریوں میں استعمال کیا جاتا ہے۔
  • کے طور پر استعمال کیا جاتا ہے ٹری سیٹ اور جاوا میں ٹری میپ اور سی ++ میں سیٹ اور میپس۔

تلاش

سرخ رنگ کا ایک درخت ایک بی ایس ٹی ہے ، لہذا آر بی ٹی میں تلاش کرنا بالکل ویسا ہی ہے جیسے بی ایس ٹی میں تلاش کرنا ، نوڈ کے رنگ سے کوئی فرق نہیں پڑتا ہے۔