درخت دکارتی

درخت دکارتی روی یک دنبالهٔ متمایز از اعداد توسط اطلاعات زیر به صورت یکتا تعریف می‌شود:

1. یک درخت دکارتی برای هر عدد در دنباله یک گره دارد. هر گره فقط به یکی از اعداد دنباله نسبت داده می‌شود.
2. یک پیمایش متقارن (میان ترتیب) روی این درخت دنبالهٔ اصلی را تولید می‌کند. در این درخت، زیر درخت سمت چپ زودتر در دنباله ظاهر می‌شود و این ترتیب در همهٔ گره‌های این درخت برقرار است.
3. این درخت خواص یک هرم را دارد، به این ترتیب که پدر هر گره (به غیر از ریشه) از فرزندانش کوچک‌تر است.

بر اساس خواص هرم، ریشهٔ درخت باید عضو کمینهٔ دنباله باشد؛ بنابراین درخت همچنین می‌تواند به صورت بازگشتی این چنین تعریف شود که ریشه کمینهٔ دنباله است و زیر درخت‌های سمت چپ و راست هر کدام درخت‌های دکارتی مجزایی روی دنباله‌های سمت چپ و راست ریشه تعریف می‌شوند؛ بنابراین سه خاصیت بالا درخت دکارتی را به صورت یکتا به دست می‌دهد. اگر در یک دنباله تکرار داشته باشیم، برای به دست آوردن درخت دکارتی متناظر نیاز به گذاشتن یک قید اضافی (به‌طور مثال از بین دو عدد برابر، عددی که زودتر دیده شود به عنوان عدد کوچکتر در نظر گرفته شود) نیاز داریم.

درخت دکارتی می‌تواند به عنوان بخشی از داده ساختارهای کارآمد برای پرسمان‌های کمینهٔ کران و مسئله‌های جستجوی کران که در بر گیرندهٔ پرسمان‌هایی برای یافتن مقدار کمینه در یک زیر دنبالهٔ پیوسته از دنبالهٔ اصلی است، می‌باشد. در یک درخت دکارتی، این مقدار کمینه می‌تواند جد مشترک راست‌ترین و چپ‌ترین مقادیر در زیر دنبالهٔ مورد نظر باشد. به عنوان مثال، در زیردنبالهٔ (۱۵، ۲۰، ۱۰، ۱۲) در دنبالهٔ مثال زده شده در شکل (۱)، مقدار کمینه (۱۰)، پایین‌ترین جد مشترک راست‌ترین و چپ‌ترین مقادیر زیردنباله (۱۲ و ۱۵) می‌باشد. به دلیل این که پایین‌ترین جد مشترک به ازای هر پرسمان در زمان ثابتی به دست می‌آید، استفاده از داده ساختاری که حجم خطی اشغال می‌کند و در زمان خطی ساخته می‌شود، باعث می‌شود مسئلهٔ کمینه کردن کران نیز محدود به همین مرزها شود.

Bender و Farach-Colton در سال ۲۰۰۰، این رابطه بین مسئلهٔ دو داده ساختار را، با نشان دادن این که پایین‌ترین اجداد مشترک در یک درخت ورودی می‌تواند به صورت کارآمد و غیر درختی برای کمینه کردن کران حل شود، معکوس کردند. داده ساختار آن‌ها از تکنیک دور اویلری برای تبدیل درخت ورودی به یک دنباله استفاده می‌کند. پس از آن کمینهٔ کران را در دنبالهٔ به دست آمده پیدا می‌کند. دنبالهٔ حاصل از این انتقال، شکل خاصی دارد (اعداد مجاور، ارتفاع گره‌های همسایه در درخت را با اختلاف ۱± نمایش می‌دهند) که باعث برتری آن می‌شود. به منظور حل مسئلهٔ کمینه کردن برای دنباله‌هایی که این شکل خاص را ندارند، درخت دکارتی را، به منظور تبدیل مسئلهٔ کمینه کردن کران به مسئلهٔ پایین‌ترین اجداد مشترک، استفاده می‌کنند. سپس با اعمال تکنیک دور اویلری، مسئله را به مسئلهٔ کمینه کردن کران در یک دنباله که این شکل خاص را دارد، تبدیل می‌کنند.

مسئلهٔ کمینه کردن کران به این شکل می‌تواند این امکان را به ما بدهد که جستجوی کران دوبعدی را بیان کنیم. یک مجموعه از تعداد متناهی اما زیاد نقاط در صفحهٔ دکارتی می‌تواند برای شکل دادن درخت دکارتی استفاده شود. به وسیلهٔ مرتب‌سازی نقاط بر اساس مختصهٔ x آن‌ها و در نظر گرفتن مختصهٔ y آن‌ها به عنوان به عنوان ترتیب این مقادیر در دنباله، می‌توان این درخت را شکل داد. اگر 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 آن‌ها اولویت‌دارها هستند.

ایدهٔ استفاده از اعداد تصادفی به عنوان اولویت، توسط Seidel و Aragon در سال ۱۹۹۶ عملی شد. داده ساختار ناشی از این ایده به دلیل ترکیب ویژگی‌های درخت دودویی و هیپ دودویی، تریپ خوانده شد. اضافه کردن به تریپ، با اضافه کردن کلید جدید به عنوان برگ یک درخت موجود، انتخاب اولویت برای آن و اجرای عملیات چرخش درخت در طول مسیر از گره تا ریشهٔ درخت برای برطرف کردن هر گونه نقض هیپ به دلیل اضافه شدن انجام می‌شود. حذف هم می‌تواند به‌طور مشابه با نرخ ثابت تغییر در طول مسیر با دنباله‌ای از چرخش‌ها در درخت انجام گیرد.

اگر اولویت‌های هر کلید به‌طور تصادفی و مستقل انتخاب شوند، با اضافه شدن یک عضو به درخت، درخت دکارتی پایانی همان ویژگی‌های درخت دودویی تصادفی جستجو را خواهد داشت، درختی که که با اضافه شدن کلیدها با جایگشت تصادفی با شروع از یک درخت تهی ایجاد می‌شود. اضافه کردن هر گره با قرار گرفتن آن گره به عنوان برگ انجام می‌شود و تغییری در ساختار درخت انجام نمی‌گیرد. درخت‌های دودویی تصادفی جستجو مدت زیادی مورد مطالعه قرار گرفته‌اند و به عنوان درخت جستجوی کارآمد شناخته می‌شوند (با احتمال زیاد ارتفاع لگاریتمی پیدا خواهند کرد). این ویژگی مهم شامل تریپ‌ها هم می‌شود. طبق پیشنهاد Seidel و Aragon، امکان اولویت‌بندی دوبارهٔ گره‌های پراستفاده، که منجر به انتقال آن‌ها به ریشهٔ تریپ و بالا بردن سرعت دسترسی به آن‌ها می‌شود، وجود دارد.

درخت دکارتی در زمان خطی توسط دنبالهٔ ورودی‌هایش قابل ساخت است. یک روش پردازش کردن دنبالهٔ مقادیر از چپ به راست است، در عین این‌که درخت دکارتی پردازش شده، در یک ساختار که امکان طی کردن درخت از بالا به پایین و برعکس را داشته باشد، باقی بماند. برای ایجاد هر مقدار جدید x، از گره‌ای که یک اولویت از x بالاتر است، شروع می‌کنیم ومسیر این گره تا ریشه را دنبال می‌کنیم تا مقدار y را که از x کوچک‌تر است را پیدا کنیم. گره y پدر x است و فرزند راست سابق y, فرزند چپ جدید x قرار می‌گیرد. مجموع زمان این فرایند خطی است، به این دلیل که، زمانی که برای جستجوی پدر هر گره x استفاده شد، می‌تواند برای حذف گره‌های موجود در راست‌ترین مسیر ذخیره شود.

الگوریتم دیگری با زمان خطی براساس تمام مقادیر کوچک‌تر نزدیک وجود دارد. در دنبالهٔ ورودی، همسایه چپ x، مقداری است که اولویتش از x بیشتر است، مقدارش کمتر و از هر مقدار دیگری به x نزدیک‌تر است. همسایهٔ راست هم به‌طور قرینه تعریف می‌شود. دنبالهٔ مقادیر با یک پشته که حاوی زیردنباله‌ای از مقادیر است، قابل نگه‌داری است. برای هر دنبالهٔ جدید x، از پشته واکشی شده تا پشته خالی شده یا بالاترین مقدار آن از x کوچک‌تر شود و در این صورت در پشته، اضافه می‌شود. همسایه چپ x بالاترین مقدار پشته در زمان اضافه شدن x است. همسایه‌های راست هم با اجرای همین الگوریتم با پشته و با دنبالهٔ معکوس به‌دست می‌آیند. پدر x در درخت دکارتی، می‌تواند بسته به مقدار در صورت وجود همسایهٔ سمت چپ یا سمت راست x باشد. همسایه‌ها با الگوریتم بهینهٔ موازی قابل پیاده‌سازی هستند، پس این فرمول برای توسعهٔ الگوریتم بهینهٔ موازی برای ساخت درخت دکارتی قابل استفاده است.

Levcolpoulos و Petersson در سال ۱۹۸۹ یک الگوریتم مرتب‌سازی بر پایهٔ درخت دکارتی ارائه دادند. آن‌ها الگوریتم را بر پایهٔ قرار داشتن مقدار بیشینه در ریشه تعریف کردند ولی این الگوریتم برای درخت‌های حاوی مقدار کمینه در ریشه هم قابل تصحیح است. الگوریتم تصحیح شده درقسمت پایین توضیح داده شده‌است. الگوریتم Levcopolous-Petersson می‌تواند به عنوان نسخه‌ای از مرتب‌سازی انتخابی و مرتب‌سازی هرمی که حاوی یک صف اولویت‌دار از مینیمم اعضای موجود است، عمل کند، به این صورت که در هر مرحله، کم‌ترین مقدار را در صف پیدا کرده و آن را حذف می‌کند و به پایان دنبالهٔ خروجی منتقل می‌کند. در الگوریتم آن‌ها، صف اولویت‌دار تنها از مقادیری که پدرشان در درخت دکارتی پیدا و حذف شده تشکیل شده‌است.

بنابراین الگوریتم شامل مراحل زیر است:

1. ساخت یک درخت دکارتی از دنبالهٔ ورودی‌ها.
2. ساخت یک صف اولویت‌دار که در ابتدا فقط حاوی ریشه درخت است.
3. تا زمانی که صف اولویت‌دار خالی نیست:
   • پیدا و حذف مقدار کمینهٔ x از صف اولوبت.
   • اضافه کردن x به دنبالهٔ خروجی.
   • اضافه کردن فرزند x در درخت دکارتی را در صف اولویت.

همان‌طور که Levcopoulos و Petersson نشان دادند، برای دنباله‌های ورودی که تقریباً مرتب شده‌اند، اندازهٔ صف اولویت‌دار کوچک می‌ماند و در این روش از این ویژگی بهره می‌گیرند تا اجرا سریع‌تر شود. اگر k میانگین تمام اعداد موجود در دنباله باشد، در بدترین حالت زمان اجرا (O(n log k است. همین‌طور بیان می‌شود که برای هر n و (k = ω(۱ هر الگوریتم مقایسه‌ای باید برای هر سری ورودی (Ω(n log k مقایسه انجام دهد.

درخت‌های دکارتی توسط Vuillemin در سال ۱۹۸۰ معرفی شدند. این اسم از سیستم دستگاه مختصات دکارتی در هواپیماها برگرفته شده‌است. در نسخه‌ای که Vuillemin ارائه داد، همان‌طور که در ساختار بالا که قابلیت یافتن مختصات دوبعدی را داشت، توضیح داده شد، یک درخت دکارتی برای گروهی از نقطه‌ها طی حرکت در درخت دارای ترتیب براساس مختصات xاش است و همچنین دارای ویژگی هیپ بر اساس مختصات yاش است. Gabbow، Bentley و Tarjan و برخی نویسندگان دیگر در سال ۱۹۸۴ تعریف درخت دکارتی را به درختی که از دنباله‌ای تشکیل شده‌است گسترش دادند. این تغییر امکان این که دنباله لزوماً دنباله‍ای مرتب از مختصات x نباشد را به نسخهٔ Vuillemin داد و همچنین این امکان را داد که درخت دکارتی برای مسائل غیر هندسی نیز مورد استفاده قرار گیرد.