payamvha/North_RAG huggingface dataset:
شکل یک رابطه‌ی بازگشتی نیز نوشته شود: formula_2 formula_3 این الگوریتم هم مانند الگوریتم‌های دیگر به صورت غیر بازگشتی هم نوشته می‌شود. فیبوناچی. یکی دیگر از الگوریتم‌های بازگشتی متداول الگوریتم فیبوناچی است. " تابع بازگشتی فیبوناچی: " formula_4 و می‌توان این تابع را با رابطهٔ بازگشتی زیر نشان داد: formula_5 formula_6 ب.م.م. الگوریتم اقلیدس که بزرگترین مقسوم‌علیه مشترک (ب.م.م) دو عدد را محاسبه می‌کند، می‌تواند به صورت بازگشتی نوشته شود. تابع به شکل زیر تعریف می‌شود: رابطهٔ بازگشتی ب.م.م به شکل زیر تعریف
می‌شود: رابطهٔ بازگشتی ب.م.م به شکل زیر تعریف می‌شود، در این رابطه منظور از formula_8، مقدار باقیمانده‌ی حاصل از formula_9 است: برج‌های هانوی(برج برهما). در محوطه معبدی در آسیای دور سه میله الماسی قرار داشت که یکی از آن‌ها حاوی تعدادی قرص طلایی بود. کاهنان معبد در تلاش بودند تا قرص‌های طلائی را از آن میله به یکی دیگر از میله‌ها تحت شرایطی انتقال دهند، و باور داشتند که با تمام شدن انتقال قرص‌ها عمر جهان نیز به پایان خواهد رسید! میله اولیه ۶۴ قرص داشت، که بر روی هم به‌طور نزولی بر اساس اندازه‌شان چیده
که بر روی هم به‌طور نزولی بر اساس اندازه‌شان چیده شده‌بودند. همانند شکل سه میله داریم. یکی از میله‌ها میله مبدأ (A)، دیگری میله کمکی (B) و دیگری میله مقصد (C) است. هدف انتقال تمام دیسک‌ها از میله مبدأ به میله مقصد با رعایت شرایط زیر است: در هر زمان فقط یک دیسک را می‌توان جابجا نمود. نباید در هیچ زمانی دیسکی بر روی دیسک با اندازه کوچکتر قرار بگیرد. هدف ما ارائه الگوریتمی است که کمترین توالی حرکت‌ها را برای انتقال دیسک‌ها به ما بدهد. مثلاً اگر n=۲ باشد، توالی حرکت به صورت زیر است: توجه داشته باشید که بر اساس
حرکت به صورت زیر است: توجه داشته باشید که بر اساس قانون اول نمی‌توان به غیر از بالاترین دیسک هر میله، به دیسک دیگری از آن دسترسی پیدا کرد. حال سؤال این است که آیا این مسئله به کمک تکنیک بازگشت قابل حل است؟ اصولاً چه مسائلی را می‌توان بازگشتی حل نمود؟ برای اینکه مسئله‌ای بتواند با روش بازگشتی حل شود باید یک ویژگی اساسی داشته باشد. مسئله اصلی (مسئله‌ای که به ما داده می‌شود) قابل خرد شدن به زیر مسئله‌هایی از همان نوع مسئله اصلی باشد، به شرطی که اندازه زیر مسئله‌های ایجاد شده کمتر باشد. آنگاه می‌توان امیدوار
ایجاد شده کمتر باشد. آنگاه می‌توان امیدوار بود که آن را به‌طور بازگشتی حل کرد! این ویژگی در مورد مسئله برج هانوی صدق می‌کند. ایده اصلی این است که توجهمان را به جای حرکت بالاترین دیسک، روی پایین‌ترین دیسک میله متمرکز کرده، و مراحل زیر را طی می‌کنیم: n - ۱ دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌کنیم. بزرگترین دیسک را از میله مبدأ به میله مقصد حرکت می‌دهیم. n - ۱ دیسک را که هم‌اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا
انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. واضح است که جابجا کردن n - ۱ قرص راحتتر از جابجا نمودن n قرص است. "تابع بازگشتی برج‌های هانوی": "رابطهٔ بازگشتی برای هانوی": هر چند برای تمام توابع بازگشتی راه حل روشنی نمی‌توان یافت اما برج‌های هانوی از این قاعده مستثنی است: ساختمان داده‌های بازگشتی(ساخت یافته). در اصطلاح کامپیوتری، ساختمان داده به روشهایی از ذخیره اطلاعات گفته می‌شود که برای استفاده بهینه از اطلاعات ذخیره
می‌شود که برای استفاده بهینه از اطلاعات ذخیره شده اتخاذ می‌شود. غالباً انتخاب یک ساختمان داده موجب ایجاد الگوریتم‌های متناسب با آن خواهد شد که این دو در کنار هم موجب افزایش سرعت انجام یک وظیفه یا کاهش مصرف حافظه برای پردازش داده می‌شود؛ سنگ بنای ساختمان‌های داده انواع داده و اشاره گرهای گوناگون است. که با توجه به چگونگی تعریف کاربرد آن‌ها در هر زبان برنامه نویسی پیاده‌سازی آن‌ها متفاوت خواهد بود. لیست پیوندی. در زیر می‌توانید تعریف ساده‌ای از گرهٔ فهرستهای پیوندی را مشاهده کنید. عنصر بعدی در ساختار گره
پیوندی را مشاهده کنید. عنصر بعدی در ساختار گره اشاره گری است به یک ساختار گره. struct node int n; // some data struct node *next; // pointer to another struct node // LIST is simply a synonym for struct node * (aka syntactic sugar). typedef struct node *LIST; رویه‌هایی که لیست ساختمان داده را به وجود می‌آورند می‌توانند به صورت بازگشتی هم تعریف شوند. void printList(LIST lst) if (!isEmpty(lst)) // base case printf("%d ", lst-&gt;n); // print integer followed by a space printList(lst-&gt;next); // recursive
by a space printList(lst-&gt;next); // recursive call درخت‌های دودویی. در زیر می‌توانید تعریف ساده‌ای از درخت‌های دودویی را مشاهده کنید. همانند گره‌ها برای لیست‌های الحاقی در اینجا نیز تعریف به صورت بازگشتی است. در اینجا دو اشاره‌گر داریم، یکی به زیر درخت سمت چپ و دیگری به زیر درخت سمت راست. struct node int n; // some data struct node *left; // pointer to the left subtree struct node *right; // point to the right subtree // TREE is simply a synonym for struct node * (aka syntactic sugar). typedef struct
node * (aka syntactic sugar). typedef struct node *TREE; void printTree(TREE t) { if (!isEmpty(t)) { // base case printTree(t-&gt;left); // go left printf("%d ", t-&gt;n); // print the integer followed by a space printTree(t-&gt;right); // go right بازگشتی در مقابل غیر بازگشتی. دربارهٔ اینکه کدامیک سریعتر و بهینه تر است نمی‌توان نظر قطعی داد و بستگی به خود الگوریتم و دفعات اجرای آن دارد. اما در هر حال هر کدام برتری‌ها و کاستی‌های نسبت به دیگری دارد و در موارد خاصی الگوریتم‌ها فقط با یکی از این روش قابل
موارد خاصی الگوریتم‌ها فقط با یکی از این روش قابل پیاده سازی‌اند. ترتیب فراخوانی توابع. تابع ۱. ترتیب فراخوانی توابع تأثیر به سزایی در اجرای برنامه دارد. به مثال زیر که با زبان C نوشته است، توجه کنید. void recursiveFunction(int num) { if (num &lt;5) { printf("%d\n", num); recursiveFunction(num + 1); تابع ۲ با خطوط جابجا شده. void recursiveFunction(int num) { if (num &lt;5) { recursiveFunction(num + 1); printf("%d\n", num); بازگشت مستقیم و غیرمستقیم. بازگشت مستقیم زمانی است که تابع خود را فراخوانی کند.
مستقیم زمانی است که تابع خود را فراخوانی کند. بازگشت غیرمستقیم زمانی است که به‌طور مثال تابع «الف» تابع «ب» و تابع «ب« تابع «ث« و تابع «ث» نیز دوباره تابع «الف» را فراخوانی کند.
در علم رایانه، ساختمان داده درخت قرمز-سیاه بلوک، یک نوع درخت جستجوی دودویی خود-متوازن است. این ساختمان داده را ابتدا رودولف بایر در سال ۱۹۷۲ با نام «درخت دودویی B متقارن» ابداع کرد ولی نام جدید آن از پایان‌نامهٔ لیو.جی.گیباس و رابرت سجویک گرفته شده‌است. این ساختمان داده بسیار پیچیده است با این حال اعمال مربوط به آن حتی در بدترین حالت نیز زمان اجرای خوبی دارند، در واقع زمان جستجو، حذف، و درج برای این درخت مانند درخت AVL لگاریتمی است (formula_1 که formula_2 تعداد گره‌های موجود در درخت است). مزیت عمده این
تعداد گره‌های موجود در درخت است). مزیت عمده این ساختمان داده نسبت به درخت AVL این است که اعمال درج و حذف با تنها یک بار پیمایش درخت از بالا به پایین و تغییر رنگ گره‌ها انجام می‌شوند و در نتیجه پیاده‌سازی این درخت از درخت AVL ساده‌تر است. ویژگی‌ها. درخت قرمز-سیاه یک درخت جستجوی دودویی است که ویژگی‌های زیر را دارد: ویژگی‌های بالا موجب این خصوصیت مهم درخت‌های قرمز-سیاه می‌شوند: ویژگی فوق باعث می‌شود تا درخت‌های قرمز-سیاه کارایی مناسبی در اعمال جستجو، درج، و حذف داشته باشند.همچنین به خاطر این که در تمام
و حذف داشته باشند.همچنین به خاطر این که در تمام مسیرهای از ریشه به برگ، تعداد گره‌های سیاه برابر است (ویژگی ۴) و ممکن نیست دو گره قرمز پشت سر هم قرار بگیرند (ویژگی ۳)، در این نوع درخت‌ها طول بلندترین مسیر از ریشه تا برگ هیچ وقت بزرگتر از دو برابر طول کوتاه‌ترین مسیر ریشه تا برگ نمی‌شود. با توجه به ویژگی‌های بالا درخت‌های قرمز-سیاه (بر خلاف درخت‌های جستجوی دودویی معمولی) هیچ وقت دچار عدم توازن شدید نمی‌شوند و زمان اجرای لگاریتمی اعمال در این درخت‌ها تضمین شده‌است. شباهت به درخت‌های بی مرتبه ۴. یک درخت
شده‌است. شباهت به درخت‌های بی مرتبه ۴. یک درخت قرمز-سیاه ار نظر ساختار شبیه یک درخت بی مرتبه ۴ است که در آن هر گره می‌تواند ۱ تا ۳ مقدار و همچنین ۲ تا ۴ اشاره گر به فرزندانش داشته باشد. در هر درخت بی، هر گره تنها یک مقدار دارد که برابر مقدار گره سیاه در درخت قرمز-سیاه است، و یک مقدار دلخواه دارد که و/یا بعد از آن در همان گره آمده‌است، که هر دوی آن‌ها مساوی گره قرمز در درخت قرمز-سیاه هستند. یک راه دیدن این برابری این است که در گره‌های قرمز درخت قرمز-سیاه در یک نمایش گرافیکی به سمت بالا حرکت کنیم، به‌طوری‌که
نمایش گرافیکی به سمت بالا حرکت کنیم، به‌طوری‌که با پدر سیاهشان در یک ردیف قرار بگیرند و یک دسته افقی را تشکیل دهند. در درخت بی، یا در نمایش گرافیکی تغییر یافته درخت قرمز-سیاه که گفته شد، همه برگ‌ها عمق یکسانی دارند. در این حالت درخت قرمز-سیاه، از نظر ساختار با درخت بی مرتبه ۴ برابر است که حداقل میزان پرشدن در یک دسته برابر ۳۳٪ است. این نوع درخت بی، عمومی تر از درخت قرمز-سیاه است اما هنگام تبدیل به درخت قرمز-سیاه، ابهاماتی دارد چون از یک درخت بی مرتبه ۴، چندین درخت قرمز-سیاه ساخته می‌شود. اگر یک دسته در
چندین درخت قرمز-سیاه ساخته می‌شود. اگر یک دسته در درخت بی تنها ۱ مقدار را شامل شود، این مقدار کمینه است، گره مربوطه سیاه است و دو اشاره گر به فرزندانش دارد. اگر یک دسته شامل ۳ مقدار شود، مقدار وسطی در یک گره سیاه قرار می‌گیرد و گره‌های کناری آن باید قرمز باشند. اگر دسته شامل ۲ مقدار باشد، هر کدام از آن‌ها می‌تواند در درخت قرمز-سیاه، سیاه باشد و دیگری باید قرمز باشد؛ بنابراین درخت بی مرتبه ۴، مشخص نمی‌کند که کدامیک از مقادیر در هر دسته ریشه سیاه کل آن دسته و پدر بقیه مقادیر دسته است. با وجود این، عملیات در
پدر بقیه مقادیر دسته است. با وجود این، عملیات در درخت‌های قرمز-سیاه از نظر زمان بهینه تر هستند چون نیازی به نگهداشتن برداری از مقادیر نیست. این نگهداری زمانی که مقادیر مستقیماً در هر گره ذخیره شده‌اند، نسبت به وقتی که تنها مرجع آن‌ها نگهداری شده‌است، پر هزینه است. البته گره‌های درخت بی از نظر حافظه به صرفه تر هستند چون لازم نیست برای آن‌ها صفت رنگ نگهداری شود. در عوض باید مشخص شود کدام بخش از دسته استفاده شده‌است. می‌توان شباهت‌هایی با درخت‌های بی مرتبه‌های بالاتری که از نظر ساختار شبیه درخت دودویی رنگ شده
بالاتری که از نظر ساختار شبیه درخت دودویی رنگ شده باشند هم ایجاد کرد چون تنها به رنگ‌های بیشتری نیاز است. مثلاً فرض کنید آبی را هم استفاده کنیم. در نتیجه درخت آبی-قرمز-سیاه مثل درخت قرمز-سیاه تعریف می‌شود اما با این محدودیت اضافه که دو گره متوالی از نظر مقدار نباید آبی باشند و همه گره‌های آبی باید فرزندان گره قرمز باشند. چنین درختی معادل یک درخت بی می‌شود که دسته‌های آن حداکثر ۷ مقدار و با این رنگ‌ها دارند :آبی، قرمز، آبی، سیاه، آبی، قرمز، آبی (هر گروه حداکثر ۱ گره سیاه، ۲ گره قرمز و ۴ گره آبی دارد). برای
۱ گره سیاه، ۲ گره قرمز و ۴ گره آبی دارد). برای تعدیل کردن حجم مقادیر، درج و حذف در یک درخت دودویی سریعتر از درخت‌های بی است چون درخت‌های رنگ شده تلاشی برای بیشینه کردن مقدار پر شدن در یک دسته افقی از گره‌ها نمی‌کنند. (تنها کمینه مقدار پرشدن در درخت‌های دودویی رنگ شده تضمین شده‌است). چرخش در درخت‌های بی سریع تر است (چون چرخش‌ها اغلب در دسته یکسان رخ می‌دهند به جای اینکه در چند گره مجزا در یک درخت دودویی رنگ شده انجام شوند). با این وجود برای مرتب‌سازی حجم زیادی از داده‌ها، درخت‌های بی بسیار سریعتر هستند چون
از داده‌ها، درخت‌های بی بسیار سریعتر هستند چون با گروهی کردن چند فرزند در یک دسته و امکان دسترسی محلی، فشرده تر شده‌اند. همه بهینه‌سازی‌های ممکن در درخت‌های بی برای افزایش متوسط میزان پرشدن گروه‌ها در درخت‌های دودویی رنگ شده هم ممکن است. بیشینه کردن میزان پرشدن در یک درخت بی، مانند کم کردن ارتفاع درخت چند رنگ است که با افزایش تعداد گره‌های غیر سیاه انجام می‌شود. بدترین حالت زمانی رخ می‌دهد که همه گره‌ها در یک درخت دودویی رنگ شده، سیاه باشند. بهترین حالت زمانی است که تنها یک سوم آن‌ها سیاه باشند (و دو سوم
است که تنها یک سوم آن‌ها سیاه باشند (و دو سوم بقیه، قرمز باشند). کاربردها و ساختمان داده‌های مرتبط. درخت‌های قرمز-سیاه، ضمانتی برای بدترین حالت زمان درج، حذف و جستجو می‌دهند. این نکته نه تنها باعث ارزشمندی آن‌ها در کاربردهایی که زمان برای آن‌ها حیاتی است مانند real-time application شده‌است بلکه آن‌ها را سازنده باارزش بلوک‌ها در سایر ساختمان داده‌های استفاده شده در هندسه محاسباتی که ضمانت بدترین زمان اجرا دارند، کرده‌است. درخت متوازن ساختار دیگری است که جستجو، درج و حذف را در زمان اجرای O(log "n")پشتیبانی
درج و حذف را در زمان اجرای O(log "n")پشتیبانی می‌کند. این درخت بیشتر از درخت قرمز-سیاه مرتب شده‌است که منجر به درج و حذف آهسته‌تر اما بازیابی سریعتر می‌شود. درخت‌های قرمز-سیاه به ویژه در برنامه‌نویسی تابعی ارزشمند هستند که یکی از رایج‌ترین انواعساختار پایدار داده‌های استفاده شده برای ساختن آرایه‌های اشتراکی و مجموعه‌ها است. نسخه پایدار درخت‌های قرمز-سیاه علاوه بر زمان، نیازمند فضایی به اندازه O(log "n") برای هر درج یا حذف است. درخت‌های قرمز-سیاه یک ایزومتری از درخت‌های ۲–۴ هستند. به عبارت دیگر، برای هر
از درخت‌های ۲–۴ هستند. به عبارت دیگر، برای هر درخت ۲–۴، یک درخت قرمز-سیاه همتا که عناصر داده‌ای آن از همان مرتبه است، وجود دارد. عملیات درج و حذف در درخت‌های ۲–۴ هم معادل تغییر رنگ و چرخش در درخت‌های قرمز-سیاه هستند. این باعث می‌شود درخت‌های ۲–۴ ابزار مهمی برای درک منطق درخت‌های قرمز-سیاه باشند؛ و این همان دلیلی است که بسیاری از متن‌های معرفی الگوریتم‌ها، درخت‌های ۲–۴ را قبل از درخت‌های قرمز-سیاه معرفی می‌کنند باوجود اینکه درخت‌های ۲–۴ معمولاً در عمل استفاده نمی‌شوند. در سال ۲۰۰۸، رابرت سجویک یک نسخه
نمی‌شوند. در سال ۲۰۰۸، رابرت سجویک یک نسخه ساده‌تر از درخت‌های قرمز-سیاه را معرفی کرد که Left-Leaning Red-Black Trees نامیده شد که با حذف کردن درجه آزادی نا مشخص در پیاده‌سازی به وجود آمده بود. LLRB یک ویژگی اضافه دارد که همه رئوس قرمز باید هنگام درج‌ها و حذف‌ها در سمت چپ درخت قرار بگیرند. درخت‌های قرمز-سیاه می‌توانند برای هر مجموعه‌ای از عملیات، به درخت‌های ۲–۳ یا درخت‌های ۲–۴ ایزومتریک باشند. درخت ۲–۴ ایزومتری در سال ۱۹۸۷ توسط سجویک معرفی شد. با درخت‌های ۲–۴، ایزومتری با یک «تغییر رنگ» حل شده است که در
۲–۴، ایزومتری با یک «تغییر رنگ» حل شده است که در آن رنگ قرمز هر دو گره فرزند، به پدر منتقل می‌شود. عملگرها. عملگرهای فقط خواندنی نسبت به درخت‌های دودویی ساده نیاز به تغییر ندارند چراکه یک حالت خاص از آن‌ها می‌باشند ولی حذف و اضافهٔ معمولی می‌تواند تأثیراتی از قبیل خارج شدن از شروط اولیهٔ درخت‌های قرمز- سیاه داشته باشد که برای بازگردانی آن ویژگی‌ها نیاز به تغییر رنگ و چرخش درخت دارد. اگرچه این نوع حذف واضافه پیچیدگی بسیاری دارد ولی بازهم نرخ جستجوی آن همچنان (O(logn می‌باشد. اضافه کردن. اضافه کردن به وسیلهٔ
(O(logn می‌باشد. اضافه کردن. اضافه کردن به وسیلهٔ پیاده‌سازی انجام شده در درخت‌های دودویی و رنگ آمیزی آن‌ها با رنگ قرمز انجام می‌شود. اتفاقی که بعداً می‌افتد بستگی به شیوهٔ رنگ آمیزی گره‌های مجاور بستگی دارد عبارت گره عمو به برادر گره والد اشاره دارد، همانند آنچه که در روابط خانوادگی مطرح است. توجه به موارد زیر لازم است: توجه کنید: برچسب‌های N برای گره اضافه شده، P برای والد گره اضافه شده،G برای پدربزرگ گره اضافه شده و U برای عموی گره اضافه شده مورد استفاده می‌شود. هر مثال شامل شرحی در زیان سی++ می‌باشد:
می‌شود. هر مثال شامل شرحی در زیان سی++ می‌باشد: class RBT{ BinaryNode * grandParent(BinaryNode *n){ if((n!=null) &amp;&amp;( n-&gt;parent!=null)) return n-&gt;parent-&gt;parent; else return NULL; BinaryNode * uncle(BinaryNode *n){ BinaryNode *g=grandparent(n); if(n-&gt;pareant==g-&gt;left) return g-&gt;right; else return g-&gt;left; حالت ۱ :گره جدید N ریشهٔ درخت باشد. در این حالت با تغییر رنگ به سیاه (بخاطر ویژگی ریشه باید سیاه باشد) و در هر مسیر باید یگ گره سیاه وجود داشته باشد اعتبار درخت را حفظ می‌کند.
سیاه وجود داشته باشد اعتبار درخت را حفظ می‌کند. void insert_case1(BinaryNode *n){ if(n-&gt;parent==null) n-&gt;col=Black; else insert_case2(n); حالت ۲: اگر گره والد سیاه باشد هیج کدام از دو ویژگی (هردو فرزند قرمز، سیاه هستند و تعداد راه‌های از هر مسیر به برگ دارای تعداد یکسان گره سیاه دارند) مورد تهدید واقع نمی‌شوند ولی فقط وجود دوگره قرمز اعتبار درخت را زیر سؤال می‌برد (حالت ۳). void insert_case2(BinaryNode *n){ if(n-&gt;parent-&gt;col==Black) return;//درخت همچنان هر پنج ویژگی را دارد. else
return;//درخت همچنان هر پنج ویژگی را دارد. else insert_case3(n); حالت ۳:اگر هردو گره والد و عمو قرمز باشد، هردو به رنگ سیاه در می‌آیند و پدر آن‌ها قرمز در می‌آید. (برابر ویژگی ۴). گره قرمز جدید دارای والد سیاه است. تا آن زمان که هر راه از والد /عمو که به‌طور قطع از پدر بزرگ نیز عبور می‌کند همچنان معتبر می‌باشد. با این وجود G(پدر والد و عمو و پدربزرگ N) باید بررسی شود که آیا ریشه‌است یا خیر (تا به رنگ سیاه درآید (ویژگی ۲) این کار را می‌توان با یک متد بازگشتی انجام داد. حتی می‌توان آن را به صورت یک حلقه نوشت
انجام داد. حتی می‌توان آن را به صورت یک حلقه نوشت که البته ثابت می‌شود این حلقه دارای تعداد مشخصی انجام عملیات چرخش است. void insert_case3(BinaryNode *n){ BinaryNode u=uncle(n); if((u!=null)&amp;&amp; )u-&gt;col==Red){ n-&gt;parent-&gt;col=Black; u-&gt;col=Black; g=grandparent(n); g-&gt;col=Red; insert_case1(g); }else insert_case4(n); حالت ۴:اگر والد (p) قرمز باشد ولی عمو سیاه باشد همچنان گره جدید سمت راست p است و p فرزند سمت چپ G است. در این حالت، یک دوران به چپ که نقش گره جدید N را با والدش؛ P تغییر
به چپ که نقش گره جدید N را با والدش؛ P تغییر می‌دهد، قابلیت اجرا پیدا می‌کند که در آن والد قبلی با فرزندش جابجا می‌شود سپس والد قبلی که اکنون دوباره برچسب‌گذاری شده با ویژگی همه مسیرها دارای تعدا مساوی گره سیاه هستند؛ سر و کار دارد. چون بر طبق ویژگی ۴ (هر دو فرزند گره قرمز سیاه هستند) همچنان مورد تهدید بی اعتبارشدن درخت همراه است. دوران باعث می‌گردد تا در بعضی از مسیرها (از جمله مسیری که از زیر درخت برچسب‌گذاری شدهٔ ۱)عبور می‌نماید از گره جدیدی که قبلاً مطرح نبوده‌است، عبور می‌کند ولی چون این گره مانند گره
نبوده‌است، عبور می‌کند ولی چون این گره مانند گره قبلی قرمز است، ویژگی ۴ با دوران اعتبار درخت را از بین نمی‌برد. void insert_case4(BinaryNode *n){ BinaryNode g=grandparent(n); if((n== n-&gt;parent-&gt;right) &amp;&amp; (n-&gt;parent ==g-&gt;left)){ rotate_left(n-&gt;parent); }else if((n== n-&gt;parent-&gt;left) &amp;&amp; (n-&gt;parent ==g-&gt;right)){ rotate_right(n-&gt;parent); n=n-&gt;right; insert_case5(n); حالت ۵:والد قرمز است ولی عمو سیاه می‌باشد و گره جدید N فرزند چپ والد P است و P فرزند چپ
و گره جدید N فرزند چپ والد P است و P فرزند چپ پدربزرگ(G)است. در این حالت رو ی پدر بزرگ(g) دوران به راست اجرا می‌گردد. درختی که نتیجه می‌شود دارای والد ی به نام P برای هردو گره G و N است .G، به عنوان ریشه، سیاه است و این تا آن زمان که فرزندش قرمز باشد پابرجاست. با تغییر رینگ P و G درخت نهایی حاصل می‌گردد که همهٔ ویژگی‌های فوق از جمله تعداد مساوی گره سیاه در هر مسیر (به این شکل که تمامی مسیرهایی که از این سه گره عبور می‌کند که قبلاً از G عبور می‌کرده و اکنون از P عبور می‌کند) پابرجاست. void
می‌کرده و اکنون از P عبور می‌کند) پابرجاست. void insert_case5(BinaryNode *n) BinaryNode *g = grandparent(n); n-&gt;parent-&gt;color = BLACK; g-&gt;color = RED; if ((n == n-&gt;parent-&gt;left) &amp;&amp; (n-&gt;parent == g-&gt;left)) { rotate_right(g); } else { /*یعنی : * (n == n-&gt;parent-&gt;right) &amp;&amp; (n-&gt;parent == g-&gt;right). rotate_left(g);
ابها شهری است کوهستانی در کشور پادشاهی عربستان سعودی واقع در شبه جزیره عربستان. این شهر مرکز فرمانداری استان عسیر است. شهر ابها در قلهٔ کوه جبال سروات قرار دارد و در أقصی جنوب غربی مملکت عربستان سعودی واقع شده‌است و بنام "عروس الجنوب" (عروس جنوب) مشهور است. محدودهٔ ابها. این شهر از سمت‌های شمال و مشرق به استان خمیس مشیط و از سمت شمال غربی به استان النماص و از جهت غرب و جنوب غربی به استان محایل و رجال المع محدود می‌گردد. پیشینهٔ تاریخی. در سنگ نبشته‌ها و در بعضی کتب تاریخی و همچنین از گفتار پژوهشگران
و در بعضی کتب تاریخی و همچنین از گفتار پژوهشگران آمده‌است که این شهر را در دوران قدیم «ابقا» می‌نامیده‌اند و یکی از نقاط تحت نفوذ مکملت سبا بوده‌است و از همین‌جا قافلهٔ شتر هدایایه ملکهٔ بلقیس ملکهٔ مملکت سبا به سوی سلیمان پیامبر برده شده‌است. در این شهر صدها ابنیه و قلعه‌های تاریخی وجود دارد که خود شاهد بر قدمت دیرینهٔ این شهر است. همچنین شهر ابها یکی از قدیمی‌ترین مکان تجمع مردم و ساکنان منطقهٔ جبال السراة و سهول تهامه بوده‌است و یکی از مشهورترین بازارهای آن دوران در این شهر قرار داشته که هنوز آثار آن
آن دوران در این شهر قرار داشته که هنوز آثار آن باقی مانده‌است. مساحت و ارتفاع. مساحت ابها در حدود ۵۰۰۰ هکتار و ارتفاعش از سطح دریا در حدود ۲۲۰۰ متر است. منطقهٔ ابها مانند حوضچه‌ای می‌ماند؛ چنان‌که از بیشتر جهات کوه آن را احاطه نموده‌است. منتها از سمت شمال و شمال شرقی انخفاض کوه مشاهده می‌شود که استان خمیس مشیط واقع شده‌است. آب و هوای ابها. ابها از لحاظ آب دمای هوا در زمستان سرد و تابستان معتدل است. حراره در تابستان معتدل و از ۳۰ درجه سانتیگراد تجاوز نمی‌کند اما در زمستان حراره به ۵ درجه سانتیگراد و حتی در
اما در زمستان حراره به ۵ درجه سانتیگراد و حتی در بعضی نقاط مانند السوده تا صفر و زیر صفر نیز می‌رسد. در ابها بادهای موسمی که منشأ آن اقیانوس هند است و باد دیگر که به نام «غربی» نزد مردم مشهور است و منشأ آن دریای سرخ است، ظاهر شده و باران می‌آورد. در فصل زمستان در ابها میزان بارندگی افزایش می‌یابد. جمعیت. جمعیت ابها و مراکز توابع آن در حدود ۶۰۰۰۰ نفر می‌باشد؛ بیشتر آنان در شهر ابها زندگی می‌کنند اما بقیه در مراکز تابعه که شامل پنج مرکز به شرح زیر است، می‌باشند: این مراکز پنجگانه شامل ۴۲۷ روستا می‌باشند که
مرتب‌سازی لانه‌کبوتری: (Pigeonhole sort) و به آن مرتب‌سازی شمارش (count sort) هم گفته می‌شود (و با مرتب‌سازی شمارشیcounting sort متفاوت است) یک الگوریتم از درجه (O(n+N است که n تعداد اعدادی است که باید مرتب شوند و N ارزشهای ممکن برای اعداد است. الگوریتم. الگوریتم این مرتب‌سازی به صورت زیر است: ۱. یک آرایه از لانه‌های کبوتر ایجاد کنید، هر لانه کبوتر نشانه یک ارزش در بازه کلیدهای موجود است ۲.آرایه اصلی (آرایه‌ای که می‌خواهد مرتب شود) را مرور کنید و هر شیء را در لانه کبوتر مربوط به آن جای دهید ۳. تکرار به
را در لانه کبوتر مربوط به آن جای دهید ۳. تکرار به ترتیب بر روی آرایه لانه‌های کبوتر، و عقب بردن عنصرها ی لانه‌های کبوتر غیر خالی در آرایه اصلی یک شبه کد ساده از الگوریتم: function pigeonhole_sort(array a[n]) array b[N] var i,j zero_var (b) (* zero out array b *) for i in [0...length(a)-1] b[a]:= b[a[i]]+1 [I](* copy the results back to a *) j:= 0 for i in [0...length(b)-1] repeat b[i] times a[j]:= i j:= j+1 [I](* copy the results back to a *) j:= 0 for i in [0...length(b)-1] repeat b[i] times a[j]:= i j:=
[0...length(b)-1] repeat b[i] times a[j]:= i j:= j+1 تحلیل. این الگوریتم به این صورت کار می‌کند که ابتدا مینیمم و ماکزیمم اعدادی که در آرایه به ما داده شده‌اند را پیدا می‌کند. سپس یک آرایهٔ کمکی ایجاد می‌کند با این هدف که سایز این آرایهٔ جدید به تعداد تمام اعداد ممکن بین مینیمم و ماکزیمم اعداد باشد. در این آرایه می‌خواهیم در واقع فراوانی هر عدد را نگه داریم و سپس از ابتدای این آرایه شروع کنیم و به تعداد فراوانی هر خانه عدد مربوط به آن خانه را چاپ کنیم. مثال زیر این مطلب را روشن تر می‌کند: T ۲ ۳ ۱ ۲ ۱ ۳ ۲ ۱
زیر این مطلب را روشن تر می‌کند: T ۲ ۳ ۱ ۲ ۱ ۳ ۲ ۱ ۴ U: ۰ ۰ ۰ ۰ ۱ ۲ ۳ ۴ ۱ ۱ ۱ ۲ ۲ ۲ ۳ ۳ ۴ پیاده‌سازی الگوریتم. کد جاوای مرتب‌سازی لانه کبوتری به صورت زیر است که نحوهٔ کار آن مطابق با توضیحات ذکر شده در بالا است: public static void pigeonhole_sort(int[] a) // size of range of values in the list (ie, number of pigeonholes we need) int min = a[0], max = a[0]; for (int x: a) { min = Math.min(x, min); max = Math.max(x, max); final int size = max - min + 1; // our array of pigeonholes int[] holes = new int[size];
array of pigeonholes int[] holes = new int[size]; // Populate the pigeonholes. for (int x: a) holes[x - min]++; // Put the elements back into the array in order. int i = 0; for (int count = 0; count &lt;size; count++) while (holes[count]--&gt; 0) a[i++] = count + min;
الکساندر ریچارد "الکس" لودویگ (زادهٔ ۷ مه ۱۹۹۲ در ونکوور) یک بازیگر کانادایی است. او با بازی در نقش "ویل استنتن" در فیلم "" که نخستین فیلم از سه‌گانه‌ای بر پایه رمان‌های سوزان کوپر بود، بیشتر شناخته شد. او در سریال "وایکینگ‌ها" نیز نقش بیورن یارنسیدا را ایفا کرده‌است. لودویگ در سال ۲۰۰۹ در فیلم "مسابقه تا کوه جادوگران" به بازی پرداخت. از دیگر فیلم‌های او می‌توان به "بازی‌های گرسنگی"، و "پسران بد تا ابد" اشاره کرد. زندگی‌نامه. لودویگ در ۱۹۹۲ونکوور، بریتیش کلمبیا زاده شد. او دو خواهر و یک برادر دارد که از همه
زاده شد. او دو خواهر و یک برادر دارد که از همه آن‌ها بزرگتر است. پدر او "هرالد" یک تاجر و مادرش "شارلین" یک بازیگر پیشین است. فیلم‌شناسی. فیلم‌های سینمایی که لودویگ در آن‌ها بازی کرده‌است: لودویگ افزون بر این، در چند فیلم ویدئویی و تلویزیونی دیگر نیز بازی کرده‌است.
در نظریهُ گراف یک فهرست مجاورت نمایش همهٔ یال‌های یک گراف به صورت مجموعه‌ای از فهرست‌هاست، اگر گراف بدون جهت باشد، هر واحد از این فهرست‌ها یک مجموعه از دو گره شامل دو سر یال مربوطه است. کاربرد در علوم رایانه. نمایش فهرست مجاورت یک گراف (G=(V,E شامل یک آرایه‌ی Adj از |V| فهرست است، یعنی به ازای هر رأس در V یک فهرست. برای هر رأس u در مجموعه رأس‌های V، فهرستِ مجاورت [Adj[u شامل همهٔ رأس‌های v است به طوری که یال (u,v) در E وجود داشته باشد. به عبارتی دیگر، [Adj[u دربردارندهٔ همهٔ رأس‌هایی است که یک یال از u به
دربردارندهٔ همهٔ رأس‌هایی است که یک یال از u به آن‌ها در گراف G وجود دارد. این رأس‌ها در فهرست مجاورت با ترتیبی دلخواه چیده شده‌اند. شکل 1.b نمایش فهرست مجاورتِ گراف بدون جهتِ نشان داده شده در شکل 1.a است. مشابهاً شکل 2.b نمایش فهرست مجاورت گرافِ جهت‌دار نشان داده شده در شکل 2.a است. خصوصیات فهرست مجاورت. اگر G یک گراف جهت‌دار باشد، مجموع طول‌های همه‌ی فهرست‌های مجاورت برابر با |E| است، چرا که یالی به شکل (u,v) با ظاهر شدنِ v در[Adj[u نمایش داده می‌شود. اما اگر G بدون جهت باشد، مجموع طول‌های همه‌ی
اما اگر G بدون جهت باشد، مجموع طول‌های همه‌ی فهرست‌های مجاورت برابر با «دوبرابرِ» |E|است، چرا که یالی بدون جهت به شکل (u,v) با ظاهر شدنِ v در [Adj[u و u در [Adj[v نمایش داده می‌شود. برای هر دو حالت (جهت دار و بدون جهت)، فهرست مجاورت ویژگی مطلوبی دارد و آن اینکه حافظهٔ مورد نیاز آن(Ѳ(V+E است. نارسایی‌های فهرست مجاورت. یک اشکال عمدهٔ فهرست‌های مجاورت این است که راه سریع تری برای اینکه بدانیم یال داده شدهٔ (u,v) در گراف هست یا نه، وجود ندارد جزاینکه در فهرست [Adj[u به دنبال v بگردیم. این اشکال می‌تواند با