موضوع مقاله: درخت دکارتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت دکارتی | مقدمه: در علوم کامپیوتر، درخت دکارتی یک درخت دودویی است که از یک دنباله از اعداد به دست می‌آید. | ## بخش 1: درخت دکارتی | این درخت به صورت یک هرم می‌باشد و پیمایش میان‌ترتیب آن دنبالهٔ اصلی را به دست می‌د هد. درخت دکارتی همچنین در تعریف داده ساختارهای تیریپ و درخت دودویی جستجوی تصادفی به منظور جستجوی دودویی نیز استفاده شده‌است. درخت دکارتی با یک الگوریتم پشته محور، به منظور پیدا کردن نزدیک‌ترین ارقام کوچک‌تر، در زمان خطی برای یک دنباله از اعداد ساخته می‌شود. تعریف درخت دکارتی روی یک دنبالهٔ متمایز از اعداد توسط اطلاعات زیر به صورت یکتا تعریف می‌شود: یک درخت دکارتی برای هر عدد در دنباله یک گره دارد. در این درخت، زیر درخت سمت چپ زودتر در دنباله ظاهر می‌شود و این ترتیب در همهٔ گره‌های این درخت برقرار است. این درخت خواص یک هرم را دارد، به این ترتیب که پدر هر گره (به غیر از ریشه) از فرزندانش کوچک‌تر است. بر اساس خواص هرم، ریشهٔ درخت باید عضو کمینهٔ دنباله باشد؛ بنابراین درخت همچنین می‌تواند به صورت بازگشتی این چنین تعریف شود که ریشه کمینهٔ دنباله است و زیر درخت‌های سمت چپ و راست هر کدام درخت‌های دکارتی مجزایی روی دنباله‌های سمت چپ و راست ریشه تعریف می‌شوند؛ بنابراین سه خاصیت بالا درخت دکارتی را به صورت یکتا به دست می‌دهد. درخت دکارتی می‌تواند به عنوان بخشی از داده ساختارهای کارآمد برای پرسمان‌های کمینهٔ کران و مسئله‌های جستجوی کران که در بر گیرندهٔ پرسمان‌هایی برای یافتن مقدار کمینه در یک زیر دنبالهٔ پیوسته از دنبالهٔ اصلی است، می‌باشد.; . در یک درخت دکارتی، این مقدار کمینه می‌تواند جد مشترک راست‌ترین و چپ‌ترین مقادیر در زیر دنبالهٔ مورد نظر باشد. به عنوان مثال، در زیردنبالهٔ (۱۵، ۲۰، ۱۰، ۱۲) در دنبالهٔ مثال زده شده در شکل (۱)، مقدار کمینه (۱۰)، پایین‌ترین جد مشترک راست‌ترین و چپ‌ترین مقادیر زیردنباله (۱۲ و ۱۵) می‌باشد. به دلیل این که پایین‌ترین جد مشترک به ازای هر پرسمان در زمان ثابتی به دست می‌آید، استفاده از داده ساختاری که حجم خطی اشغال می‌کند و در زمان خطی ساخته می‌شود،; . داده ساختار آن‌ها از تکنیک دور اویلری برای تبدیل درخت ورودی به یک دنباله استفاده می‌کند. دنبالهٔ حاصل از این انتقال، شکل خاصی دارد (اعداد مجاور، ارتفاع گره‌های همسایه در درخت را با اختلاف ۱± نمایش می‌دهند) که باعث برتری آن می‌شود. به منظور حل مسئلهٔ کمینه کردن برای دنباله‌هایی که این شکل خاص را ندارند، درخت دکارتی را، به منظور تبدیل مسئلهٔ کمینه کردن کران به مسئلهٔ پایین‌ترین اجداد مشترک، استفاده می‌کنند. سپس با اعمال تکنیک دور اویلری، مسئله را به مسئلهٔ کمینه کردن کران در یک دنباله که این شکل خاص را دارد، تبدیل می‌کنند. مسئلهٔ کمینه کردن کران به این شکل می‌تواند این امکان را به ما بدهد که جستجوی کران دوبعدی را بیان کنیم. یک مجموعه از تعداد متناهی اما زیاد نقاط در صفحهٔ دکارتی می‌تواند برای شکل دادن درخت دکارتی استفاده شود. به وسیلهٔ مرتب‌سازی نقاط بر اساس مختصهٔ x آن‌ها و در نظر گرفتن مختصهٔ y آن‌ها به عنوان به عنوان ترتیب این مقادیر در دنباله، می‌توان این درخت را شکل داد. | ## بخش 2: درخت دکارتی | اگر S را به عنوان زیرمجموعهٔ نقاط ورودی بین چند محدودهٔ عمودی با نامعادلهٔ L ≤ x ≤ R فرض کنیم و p چپ‌ترین نقطهٔ S (نقطه‌ای که مختصهٔ x آن کمینه است) است، و q راست‌ترین نقطهٔ S (نقطه‌ای که مختصهٔ x آن بیشینه است) است، آنگاه پایین‌ترین جد مشترک p و q در درخت دکارتی پایین‌ترین نقطه در محدوده است. یک پرسمان کران سه طرفه که در آن هدف لیست کردن نقاط در یک محدودهٔ سه طرفه است که با نامعادله‌های L ≤ x ≤ R و y ≤ T مشخص می‌شود، می‌تواند با پیدا کردن پایین‌ترین نقطه (b) و مقایسهٔ مختصهٔ y آن با T، و (در صورت حضور b در محدودهٔ مورد نظر) ادامه دادن این روش بین b و p، و بین b و q، به صورت بازگشتی، پیدا شود. در این روش پس از این که راست‌ترین و چپ‌ترین نقاط بازه مشخص شدند، تمام نقاط بین این سه محدوده را می‌توان در زمان ثابت به ازای هر نقطه، لیست کرد.. در ساختمان به این شکل برای پایین‌ترین اجداد مشترک در یک درخت دکارتی، این امکان را ایجاد می‌کند که داده ساختاری با اشغال حجم خطی بسازیم که به ما اجازهٔ پرسش ذر مورد فاصلهٔ بین هر جفت از نقاط در فضای فرامتریک را در زمان ثابت به ازای هر پرسمان، می‌دهد. فاصلهٔ بین دو نقطه در فضای فرامتریک، وزن مسیر مینیماکس در درخت فراگیر کمینه در فضای متریک است.; از یک درخت فراگیر کمینه می‌توان یک درخت دکارتی ساخت که ریشهٔ آن نمایانگر سنگین‌ترین لبهٔ درخت فراگیر کمینه می‌باشد. با تقسیم درخت فراگیر کمینه به دو زیردرخت، می‌توان به صورت بازگشتی درخت دکارتی را به وسیلهٔ بچه‌های ریشهٔ ذکر شده ساخت. همچنین پایین‌ترین جد مشترک دو برگ، سنگین‌ترین لبه بین آن دو نقطه در درخت فراگیر کمینه است که وزن آن با فاصلهٔ بین دو نقطه برابر است. درخت دکارتی زمانی می‌تواند در زمان خطی ساخته شود که درخت فراگیر کمینه را بیابیم و وزن لبه‌های آن را مرتب کنیم.. تیریپ‌ها به دلیل این‌که یک درخت دکارتی یک درخت دودویی است، طبیعی است که آن را به عنوان یک درخت دودویی جستجو برای یک دنبالهٔ مرتب از مقادیر استفاده کنیم. با این حال، تعریف کردن درخت دکارتی بر اساس مقادیر مشابهی که کلیدهای درخت جستجو را می‌سازند به خوبی کارآمد نیست. درخت دکارتی مربوط به یک دنباله مرتب، یک مسیر است که ریشهٔ آن چپ‌ترین نقطهٔ آن است و جستجوی دودویی در این درخت را به جستجوی خطی در یک مسیر تبدیل می‌کند. با این حال، ایجاد درخت‌های جستجوی متعادل‌تر با ایجاد مقادیر اولویت‌دار برای هر کلید جستجو که با خود کلید متفاوتند، با مرتب کردن ورودی‌ها بر اساس مقادیر کلیدشان و استفاده از دنبالهٔ اولویت‌دار مربوطه برای ایجاد درخت دکارتی ممکن است. به این صورت که مختصات x نقاط، کلیدهای جستجو و مختصات y آن‌ها اولویت‌دارها هستند. داده ساختار ناشی از این ایده به دلیل ترکیب ویژگی‌های درخت دودویی و هیپ دودویی، تریپ خوانده شد. اضافه کردن به تریپ، با اضافه کردن کلید جدید به عنوان برگ یک درخت موجود، انتخاب اولویت برای آن و اجرای عملیات چرخش درخت در طول مسیر از گره تا ریشهٔ درخت برای برطرف کردن هر گونه نقض هیپ به دلیل اضافه شدن انجام می‌شود. حذف هم می‌تواند به‌طور مشابه با نرخ ثابت تغییر در طول مسیر با دنباله‌ای از چرخش‌ها در درخت انجام گیرد. اگر اولویت‌های هر کلید به‌طور تصادفی و مستقل انتخاب شوند، با اضافه شدن یک عضو به درخت، درخت دکارتی پایانی همان ویژگی‌های درخت دودویی تصادفی جستجو را خواهد داشت، درختی که که با اضافه شدن کلیدها با جایگشت تصادفی با شروع از یک درخت تهی ایجاد می‌شود. اضافه کردن هر گره با قرار گرفتن آن گره به عنوان برگ انجام می‌شود و تغییری در ساختار درخت انجام نمی‌گیرد. | ## بخش 3: درخت دکارتی | درخت‌های دودویی تصادفی جستجو مدت زیادی مورد مطالعه قرار گرفته‌اند و به عنوان درخت جستجوی کارآمد شناخته می‌شوند (با احتمال زیاد ارتفاع لگاریتمی پیدا خواهند کرد). طبق پیشنهاد Seidel و Aragon، امکان اولویت‌بندی دوبارهٔ گره‌های پراستفاده، که منجر به انتقال آن‌ها به ریشهٔ تریپ و بالا بردن سرعت دسترسی به آن‌ها می‌شود، وجود دارد. یک روش پردازش کردن دنبالهٔ مقادیر از چپ به راست است، در عین این‌که درخت دکارتی پردازش شده، در یک ساختار که امکان طی کردن درخت از بالا به پایین و برعکس را داشته باشد، باقی بماند. برای ایجاد هر مقدار جدید x، از گره‌ای که یک اولویت از x بالاتر است، شروع می‌کنیم ومسیر این گره تا ریشه را دنبال می‌کنیم تا مقدار y را که از x کوچک‌تر است را پیدا کنیم. مجموع زمان این فرایند خطی است، به این دلیل که، زمانی که برای جستجوی پدر هر گره x استفاده شد، می‌تواند برای حذف گره‌های موجود در راست‌ترین مسیر ذخیره شود. در دنبالهٔ ورودی، همسایه چپ x، مقداری است که اولویتش از x بیشتر است، مقدارش کمتر و از هر مقدار دیگری به x نزدیک‌تر است. دنبالهٔ مقادیر با یک پشته که حاوی زیردنباله‌ای از مقادیر است، قابل نگه‌داری است. برای هر دنبالهٔ جدید x، از پشته واکشی شده تا پشته خالی شده یا بالاترین مقدار آن از x کوچک‌تر شود و در این صورت در پشته، اضافه می‌شود. همسایه‌های راست هم با اجرای همین الگوریتم با پشته و با دنبالهٔ معکوس به‌دست می‌آیند. پدر x در درخت دکارتی، می‌تواند بسته به مقدار در صورت وجود همسایهٔ سمت چپ یا سمت راست x باشد. همسایه‌ها با الگوریتم بهینهٔ موازی قابل پیاده‌سازی هستند، پس این فرمول برای توسعهٔ الگوریتم بهینهٔ موازی برای ساخت درخت دکارتی قابل استفاده است.. آن‌ها الگوریتم را بر پایهٔ قرار داشتن مقدار بیشینه در ریشه تعریف کردند ولی این الگوریتم برای درخت‌های حاوی مقدار کمینه در ریشه هم قابل تصحیح است. الگوریتم Levcopolous-Petersson می‌تواند به عنوان نسخه‌ای از مرتب‌سازی انتخابی و مرتب‌سازی هرمی که حاوی یک صف اولویت‌دار از مینیمم اعضای موجود است، عمل کند، به این صورت که در هر مرحله، کم‌ترین مقدار را در صف پیدا کرده و آن را حذف می‌کند و به پایان دنبالهٔ خروجی منتقل می‌کند. در الگوریتم آن‌ها، صف اولویت‌دار تنها از مقادیری که پدرشان در درخت دکارتی پیدا و حذف شده تشکیل شده‌است. همین‌طور بیان می‌شود که برای هر n و (k = ω(۱ هر الگوریتم مقایسه‌ای باید برای هر سری ورودی (Ω(n log k مقایسه انجام دهد. در نسخه‌ای که Vuillemin ارائه داد، همان‌طور که در ساختار بالا که قابلیت یافتن مختصات دوبعدی را داشت، توضیح داده شد، یک درخت دکارتی برای گروهی از نقطه‌ها طی حرکت در درخت دارای ترتیب براساس مختصات xاش است و همچنین دارای ویژگی هیپ بر اساس مختصات yاش است. | ## جمع‌بندی | این تغییر امکان این که دنباله لزوماً دنباله‍ای مرتب از مختصات x نباشد را به نسخهٔ Vuillemin داد و همچنین این امکان را داد که درخت دکارتی برای مسائل غیر هندسی نیز مورد استفاده قرار گیرد.