Scapegoat tree
کمپیوٹر سائنس میں، قربانی کا بکرا ایک خود توازن بائنری سرچ ٹری ہے، جسے 1989 میں آرن اینڈرسن نے اور پھر 1993 میں ایگل گیلپرین اور رونالڈ ایل ریویسٹ نے ایجاد کیا تھا۔ یہ بدترین صورت حال کی تلاش کا وقت (اندراجات کی تعداد کے ساتھ) اور ادائیگی شدہ اندراج اور حذف کرنے کا وقت فراہم کرتا ہے۔ زیادہ تر دوسرے سیلف بیلنسنگ بائنری سرچ ٹریز کے برعکس جو بدترین صورت میں تلاش کا وقت بھی فراہم کرتے ہیں، قربانی کے بکروں کے درختوں میں باقاعدہ بائنری سرچ ٹری کے مقابلے میں کوئی اضافی فی نوڈ میموری اوور ہیڈ نہیں ہوتی ہے: کلیدی اور قدر کے علاوہ، ایک نوڈ چائلڈ نوڈس کے لیے صرف دو اشارے محفوظ کرتا ہے۔ اس سے قربانی کے بکروں کو لاگو کرنا آسان ہو جاتا ہے اور ڈیٹا ڈھانچے کی صف بندی کی وجہ سے نوڈ اوور ہیڈ کو ایک تہائی تک کم کیا جا سکتا ہے۔ زیادہ تر متوازن ٹری الگورتھم کے ذریعہ استعمال ہونے والی چھوٹی اضافی توازن کی کارروائیوں کے بجائے، قربانی کا بکرا شاذ و نادر ہی لیکن مہنگے انداز میں "قربانی کا بکرا" کا انتخاب کرتا ہے اور قربانی کے بکرا پر جڑے ہوئے ذیلی درخت کو مکمل طور پر بائنری ٹری میں دوبارہ تعمیر کرتا ہے۔ اس طرح، قربانی کے بکروں کی تازہ کاری کی کارکردگی بدترین ہوتی ہے۔ نظریہ بائنری سرچ ٹری کو وزن متوازن کہا جاتا ہے اگر نصف نوڈس جڑ کے بائیں طرف اور نصف دائیں طرف ہوں۔ ایک α-وزن-متوازن نوڈ کو آرام دہ وزن کے توازن کے معیار کو پورا کرنے کے طور پر بیان کیا گیا ہے: سائز (بائیں) ≤ α * سائز (نوڈ) سائز (دائیں) ≤ α * سائز (نوڈ) جہاں سائز کو بار بار اس طرح بیان کیا جاسکتا ہے: فنکشن سائز (نوڈ) اگر نوڈ = صفر ہے تو 0 اور ریٹرن سائز (نوڈ-> بائیں) + سائز (نوڈ-> دائیں) + 1 اختتام اگر اختتامی فنکشن یہاں تک کہ ایک انحطاط شدہ درخت (منسلک فہرست) بھی اس شرط کو پورا کرتا ہے اگر α = 1، جبکہ α = 0.5 صرف تقریبا مکمل بائنری درختوں سے میل کھاتا ہے۔ ایک بائنری سرچ ٹری جو α-وزن-متوازن ہے اسے بھی α-اونچائی-متوازن ہونا چاہیے، یعنی اونچائی (درخت) ≤ فرش (لاگ 1/α (سائز (درخت))) متضاد طور پر، ایک درخت جو α-اونچائی-متوازن نہیں ہے وہ α-وزن-متوازن نہیں ہے۔ قربانی کے بکروں کو ہر وقت α-وزن-توازن برقرار رکھنے کی ضمانت نہیں دی جاتی ہے، لیکن ہمیشہ اس اونچائی (قربانی کا بکرا درخت) ≤ فرش (لاگ 1/α (سائز (درخت))) + 1 میں ڈھیلے α-اونچائی-متوازن ہوتے ہیں۔ اونچائی کے توازن کی اس حالت کی خلاف ورزیوں کا اندراج کے وقت پتہ لگایا جا سکتا ہے، اور اس کا مطلب یہ ہے کہ وزن کے توازن کی حالت کی خلاف ورزی موجود ہونی چاہیے۔ اس سے قربانی کے بکروں کے درخت سرخ سیاہ درختوں سے ملتے جلتے ہیں کیونکہ ان دونوں کی اونچائی پر پابندیاں ہوتی ہیں۔ وہ اس بات کا تعین کرنے کے ان کے نفاذ میں بہت مختلف ہیں کہ گردش کہاں ہوتی ہے (یا قربانی کے بکرا کے درختوں کے معاملے میں، دوبارہ توازن)۔ جبکہ سرخ سیاہ درخت مقام کا تعین کرنے کے لیے ہر نوڈ میں اضافی 'رنگ' کی معلومات جمع کرتے ہیں، قربانی کا بکرا درختوں کو ایک قربانی کا بکرا ملتا ہے جو دوبارہ توازن عمل انجام دینے کے لیے α-وزن-متوازن نہیں ہوتا ہے۔ یہ کچھ حد تک اے وی ایل درختوں سے ملتا جلتا ہے، اس میں اصل گردش نوڈس کے 'توازن' پر منحصر ہوتی ہے، لیکن توازن کا تعین کرنے کے ذرائع بہت مختلف ہوتے ہیں۔ چونکہ اے وی ایل درخت ہر اندراج/حذف کرنے پر بیلنس ویلیو کی جانچ کرتے ہیں، یہ عام طور پر ہر نوڈ میں محفوظ ہوتا ہے۔ قربانی کا بکرا درخت صرف ضرورت کے مطابق اس کا حساب لگانے کے قابل ہوتے ہیں، جو صرف اس وقت ہوتا ہے جب قربانی کا بکرا تلاش کرنے کی ضرورت ہوتی ہے۔ زیادہ تر دوسرے خود توازن تلاش کے درختوں کے برعکس، قربانی کے بکرا کے درخت اپنے توازن کے لیے مکمل طور پر لچکدار ہوتے ہیں۔ وہ کسی بھی α کو اس طرح سپورٹ کرتے ہیں کہ 0.0 <α <1۔ اعلی α قدر کے نتیجے میں کم توازن پیدا ہوتا ہے، جس سے اندراج تیز ہوتا ہے لیکن تلاش اور حذف کرنا سست ہوتا ہے، اور اس کے برعکس کم α کے لیے۔ لہذا عملی ایپلی کیشنز میں، ایک α کا انتخاب اس بات پر منحصر ہے کہ ان اعمال کو کتنی بار انجام دیا جانا چاہیے۔ آپریشنز لک اپ لک اپ کو معیاری بائنری سرچ ٹری سے تبدیل نہیں کیا گیا ہے، اور اس کا بدترین وقت ہوتا ہے۔ یہ اسپلے کے درختوں کے برعکس ہے جن کا بدترین وقت ہوتا ہے۔ دیگر سیلف بیلنسنگ بائنری سرچ ٹری کے مقابلے میں نوڈ میموری اوور ہیڈ میں کمی حوالہ اور کیشنگ کے مقام کو مزید بہتر بنا سکتی ہے۔ اندراج ایک غیر متوازن بائنری سرچ ٹری کی طرح ہی بنیادی خیالات کے ساتھ نافذ کیا جاتا ہے، تاہم چند اہم تبدیلیوں کے ساتھ۔ اندراج نقطہ تلاش کرتے وقت، نئے نوڈ کی گہرائی بھی ریکارڈ کی جانی چاہیے۔ یہ ایک سادہ کاؤنٹر کے ذریعے لاگو کیا جاتا ہے جو تلاش کے ہر تکرار کے دوران بڑھ جاتا ہے، مؤثر طریقے سے جڑ اور داخل شدہ نوڈ کے درمیان کناروں کی تعداد کو شمار کرتا ہے۔ اگر یہ نوڈ α-اونچائی-توازن کی خاصیت (اوپر بیان کردہ) کی خلاف ورزی کرتا ہے، تو دوبارہ توازن کی ضرورت ہے۔ دوبارہ توازن قائم کرنے کے لیے، قربانی کے بکرے پر جڑے ہوئے ایک پورے ذیلی درخت کو توازن برقرار رکھنے کے عمل سے گزرنا پڑتا ہے۔ قربانی کا بکرا داخل شدہ نوڈ کا آباؤ اجداد ہونے کے طور پر بیان کیا گیا ہے جو α-وزن متوازن نہیں ہے۔ ہمیشہ کم از کم ایک ایسا آباؤ اجداد رہے گا۔ ان میں سے کسی کو بھی دوبارہ متوازن کرنے سے α-اونچائی-متوازن خاصیت بحال ہو جائے گی۔ قربانی کا بکرا تلاش کرنے کا ایک طریقہ یہ ہے کہ نئے نوڈ سے جڑ تک واپس چڑھنا اور پہلا نوڈ منتخب کرنا جو α-وزن میں متوازن نہ ہو۔ جڑ تک واپس چڑھنے کے لیے اسٹوریج کی جگہ درکار ہوتی ہے، جو عام طور پر اسٹیک پر مختص ہوتی ہے، یا پیرنٹ پوائنٹرز۔ جب آپ نیچے جاتے ہیں تو ہر بچے کو اس کے والدین کی طرف اشارہ کرکے، اور بیک اپ واک پر مرمت کرکے اس سے بچا جا سکتا ہے۔ اس بات کا تعین کرنے کے لیے کہ آیا ایک ممکنہ نوڈ ایک قابل عمل قربانی کا بکرا ہے، ہمیں اس کی α-وزن-متوازن خاصیت کی جانچ کرنے کی ضرورت ہے۔ ایسا کرنے کے لیے ہم تعریف پر واپس جا سکتے ہیں: سائز (بائیں) ≤ α * سائز (نوڈ) سائز (دائیں) ≤ α * سائز (نوڈ) تاہم یہ محسوس کر کے ایک بڑی اصلاح کی جا سکتی ہے کہ ہم پہلے ہی تین میں سے دو سائز جانتے ہیں، صرف تیسرے کا حساب کرنا باقی ہے۔ اس بات کو ثابت کرنے کے لیے درج ذیل مثال پر غور کریں۔ یہ فرض کرتے ہوئے کہ ہم جڑ تک واپس چڑھ رہے ہیں: سائز (والدین) = سائز (نوڈ) + سائز (بہن بھائی) + 1 لیکن جیسا کہ: سائز (داخل شدہ نوڈ) = 1۔ کیس کو اس طرح ٹریویلائز کیا گیا ہے: سائز [x + 1] = سائز [x] + سائز (بہن بھائی) + 1 جہاں x = یہ نوڈ، x + 1 = پیرنٹ اور سائز (بہن بھائی) واحد فنکشن کال ہے جس کی اصل میں ضرورت ہے۔ ایک بار جب قربانی کا بکرا مل جاتا ہے، تو قربانی کے بکرا پر جڑے ہوئے ذیلی درخت کو مکمل طور پر متوازن ہونے کے لیے مکمل طور پر دوبارہ تعمیر کیا جاتا ہے۔ یہ سبٹری کے نوڈس کو عبور کر کے وقت پر کیا جا سکتا ہے تاکہ ان کی اقدار کو ترتیب شدہ ترتیب میں تلاش کیا جا سکے اور بار بار میڈین کو سبٹری کی جڑ کے طور پر منتخب کیا جا سکے۔ چونکہ دوبارہ توازن کی کارروائیوں میں وقت لگتا ہے (سبٹری کے نوڈس کی تعداد پر منحصر ہے)، اندراج میں وقت کی بدترین کارکردگی ہوتی ہے۔ تاہم، چونکہ یہ بدترین صورت حال پھیلے ہوئے ہیں، اس لیے داخل کرنے میں کافی وقت لگتا ہے۔ اندراج کی لاگت کے لیے ثبوت کا خاکہ نوڈ v کے عدم توازن کو اس کے بائیں نوڈ اور دائیں نوڈ مائنس 1، یا 0، جو بھی زیادہ ہو، کے درمیان سائز میں فرق کی مطلق قیمت کے طور پر بیان کریں۔ دوسرے لفظوں میں: v پر جڑے ہوئے ذیلی درخت کی تعمیر نو کے فورا بعد، I (v) = 0۔ لیما: v پر جڑے ہوئے ذیلی درخت کی تعمیر نو سے فورا پہلے، (بگ اومیگا نوٹیشن ہے۔) لیما کا ثبوت: تعمیر نو کے فورا بعد ذیلی درخت کی جڑ بنیں۔ ۔ اگر انحطاطی اندراجات ہیں (یعنی، جہاں ہر داخل شدہ نوڈ اونچائی کو 1 سے بڑھاتا ہے)، تو، اور۔ چونکہ تعمیر نو سے پہلے، ذیلی درخت میں داخل ہونے کی جڑیں تھیں جس کے نتیجے میں تعمیر نو نہیں ہوئی۔ ان میں سے ہر ایک اندراج وقت پر کیا جا سکتا ہے۔ حتمی اندراج جو تعمیر نو کے اخراجات کا سبب بنتا ہے۔ مجموعی تجزیہ کا استعمال کرتے ہوئے یہ واضح ہو جاتا ہے کہ داخل کرنے کی تخفیف شدہ لاگت یہ ہے: قربانی کے بکروں کو ہٹانا غیر معمولی ہے اس میں حذف کرنا داخل کرنے سے زیادہ آسان ہے۔ حذف کرنے کو فعال کرنے کے لیے، قربانی کے بکروں کو درخت کے ڈیٹا ڈھانچے کے ساتھ ایک اضافی قیمت ذخیرہ کرنے کی ضرورت ہے۔ یہ خاصیت، جسے ہم میکس نوڈکاؤنٹ کہیں گے، صرف سب سے زیادہ حاصل کردہ نوڈکاؤنٹ کی نمائندگی کرتی ہے۔ جب بھی پورے ٹری کو دوبارہ متوازن کیا جاتا ہے تو اسے نوڈکاؤنٹ پر سیٹ کیا جاتا ہے، اور داخل کرنے کے بعد اسے زیادہ سے زیادہ (میکس نوڈکاؤنٹ، نوڈکاؤنٹ) پر سیٹ کیا جاتا ہے۔ حذف کرنے کے لیے، ہم صرف نوڈ کو ہٹا دیتے ہیں جیسا کہ آپ ایک سادہ بائنری سرچ ٹری میں کرتے ہیں، لیکن اگر نوڈکاؤنٹ ≤ α * میکس نوڈکاؤنٹ ہے تو ہم میکس نوڈکاؤنٹ کو نوڈکاؤنٹ پر سیٹ کرنا یاد رکھتے ہوئے جڑ کے بارے میں پورے ٹری کو دوبارہ متوازن کرتے ہیں۔ یہ حذف کرنے کو وقت کی بدترین کارکردگی دیتا ہے، جبکہ ادائیگی کا وقت ہے۔ حذف کرنے کی لاگت کے ثبوت کا خاکہ فرض کریں کہ قربانی کے بکرا کے درخت میں عناصر ہیں اور اسے ابھی دوبارہ تعمیر کیا گیا ہے (دوسرے الفاظ میں، یہ ایک مکمل بائنری درخت ہے)۔ زیادہ تر حذفیاں درخت کو دوبارہ تعمیر کرنے سے پہلے کی جا سکتی ہیں۔ ان حذفیوں میں سے ہر ایک میں وقت لگتا ہے (عنصر کو تلاش کرنے اور اسے حذف شدہ کے طور پر نشان زد کرنے میں وقت کی مقدار)۔ حذف کرنے سے درخت کو دوبارہ تعمیر کیا جاتا ہے اور اس میں (یا صرف) وقت لگتا ہے۔ مجموعی تجزیہ کا استعمال کرتے ہوئے یہ واضح ہو جاتا ہے کہ حذف کرنے کی تخفیف شدہ لاگت یہ ہے: صفت نام قربانی کا بکرا درخت "[.] اس عام حکمت پر مبنی ہے کہ جب کچھ غلط ہو جاتا ہے تو لوگ سب سے پہلے کسی کو (قربانی کا بکرا) کو مورد الزام ٹھہرانے کے لیے تلاش کرتے ہیں۔" بائبل میں، قربانی کا بکرا ایک ایسا جانور ہے جس پر رسمی طور پر دوسروں کے گناہوں کا بوجھ ڈالا جاتا ہے، اور پھر اسے نکال دیا جاتا ہے۔ یہ بھی دیکھیں پلے ٹری ٹری روٹیشن اے وی ایل ٹری بی-ٹری ٹی-ٹری حوالہ جات بیرونی روابط بائنری ٹری سرچ ٹری امورٹائزڈ ڈیٹا ڈھانچے