موضوع مقاله: درخت مستطیلی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت مستطیلی | مقدمه: ISBN 0897911288 پیشنهاد شد و کاربردهای مختلفی در زمینه‌های نظری و کاربردی بدست آورد.Y. | ## بخش 1: درخت مستطیلی | Retrieved 8 October 2011.یکی از کاربردهای معمول درخت مستطیلی می‌تواند ذخیره شیء‌های مکانی مانند مکان رستوران‌ها یا چند ضلعی‌هایی که نقشه‌های معمولی از آن‌ها ساخته می‌شوند: خیابان‌ها، ساختمان‌ها، مرز دریاچه‌ها، خطوط ساحلی و غیره، و سپس یافتن سریع پاسخ سوال‌هایی مانند "تمام موزه‌هایی که در ۲ کیلومتری مکان من هستند را پیدا کن"،"بازیابی تمام جاده‌ها تا ۲ کیلومتری اطراف من (برای نشان دادن در سامانه راه یابی)" یا "نزدیک‌ترین پمپ بنزین را پیدا کن"، باشد. ایده درخت مستطیلی ایده اصلی این داده ساختار این است که اشیاء نزدیک هم را در یک گروه قرار دهیم و آن‌ها را با کوچکترین مستطیلی که آن‌ها را احاطه می‌کند در سطح بالایی درخت نشان دهیم؛ R در "درخت R" از اول کلمه rectangle گرفته شده‌است. از آن جایی که همه اشیاء در مستطیل احاطه‌کننده قرار می‌گیرند، یک جستجو که تداخلی با مستطیل احاطه‌کننده ندارد پس نمی‌تواند تداخلی با هیچ یک از اشیاء داخل آن داشته باشد. در سطح برگ هر مستطیل نشان دهده یک شیء هست؛ در سطوح بالاتر این تعداد افزایش پیدا می‌کند. مشابه با درخت B، درخت مستطیلی هم یک درخت جستجو متوازن است (پس همهٔ برگ‌ها در یک ارتفاع هستند)، داده‌ها را در صفحه سازمان دهی می‌کند، و برای ذخیره بر روی دیسک طراحی شده‌است. هر صفحه می‌تواند حاوی یک مقدار حداکثری از ورودی‌ها باشد که معمولاً با M نشان داده می‌شود. همچنین یک مقدار حداقلی هم تضمین می‌شود (بجز گره ریشه)، اگر چه بهترین عملکرد با حداقل پر شدن ۳۰٪ تا ۴۰٪ حداکثر مقدار داده‌ها، تجربه شده‌است (درخت B پر شدن ۵۰٪ و درخت *B پر شدن ۶۶٪ صفحه را ضمانت می‌کند). دلیل این مورد، پیچیده تر بودن متوازن سازی برای داده‌های مکانی در برابر داده‌های خطی ذخیره شده در درخت B است. مانند اکثر درخت‌ها الگوریتم‌های جستجو (برای مثال تلاقی، حاوی بودن، جستجو نزدیکترین همسایه) نسبتاً ساده هستند. ایده اصلی استفاده کردن از مستطیل احاطه‌کننده برای تصمیم گیری در مورد اینکه داخل یک زیر درخت جستجو شود یا نه، است. این مورد باعث می‌شود درخت مستطیلی برای مجموعه داده‌های بزرگ و پایگاه‌های داده مناسب باشد؛ جایی که کل درخت در حافظه جا نمی‌شود و گره‌ها در هنگام نیاز به حافظه منتقل می‌شوند. سختی اصلی طراحی درخت مستطیلی این است که از یک طرف درخت باید متوازن باشد (برگ‌ها در یک ارتفاع باشند) و از طرف دیگر مستطیل‌ها فضای خالی زیادی را پوشش ندهند و زیاد هم پوشانی نداشته باشند (تا در هنگام جستجو نیاز به بررسی تعداد کمتری زیردرخت باشد). برای مثال، ایده اصلی برای اضافه کردن داده‌ها برای بدست آمدن یک درخت بهینه این است که همیشه به زیردرختی که نیاز به کمترین بزرگ شدن مستطیل احاطه‌کننده‌اش دارد، اضافه کنیم. وقتی آن صفحه پر شد، داده‌ها به دو مجموعه که هر کدام مقدار کمینه‌ای مساحت را پوشش می‌دهند، تقسیم می‌شوند. هدف اکثر تحقیقات و بهبودها برای درخت R، بهبود نحوه ساخت درخت است و می‌توان آن‌ها را به دو بخش تقسیم کرد: ساخت یک درخت بهینه از ابتدا (بارگذاری توده‌ای) و ایجاد تغییرات بر روی یک درخت موجود (حذف و اضافه). | ## بخش 2: درخت مستطیلی | درخت‌های مستطیلی کارایی خوب برای بدترین حالت را تضمین نمی‌کنند ولی عموماً برای داده‌های واقعی خوب کار می‌کنند.Hwang, S. .از جنبه نظری درخت مستطیلی اولویت (بارگذاری توده‌ای شده) از انواع درخت مستطیلی در بدترین حالت بهینه استArge, L. ISBN 1581138598، ولی به دلیل زیاد شدن پیچیدگی توجه زیادی در کاربردهای عملی به آن نشده‌است. "تراکم-اتصال-دسته بندی کردن" یک الگوریتم آنالیز خوشه‌ای است که از ساختار درخت مستطیلی برای انواع مشابه اتصال مکانی استفاده می‌کند تا به صورت بهینه یک دسته‌بندی OPTICS را محاسبه کند. انواع درخت مستطیلی* درخت مستطیلی+ درخت مستطیلی هیلبرت درخت X الگوریتم‌ها ساختار داده داده‌ها در درخت مستطیلی در چند صفحه سازمان دهی می‌شوند، که می‌توانند شامل تعداد متغیری مدخل باشند (حداکثر تا تعداد یک مقدار از قبل تعیین شده و معمولاً بیشتر از یک مقدار حداقلی). هر مدخل درون یک گره غیر برگ دو قطعه اطلاعات نگهداری می‌کند: یک راه برای شناسایی گره فرزند. گره‌های برگ اطلاعات مورد نیاز برای هر فرزند را نگه می‌دارند، معمولاً یک نقطه یا مستطیل احاطه‌کننده معرّف فرزند و یک شناسه خارجی برای فرزند. هر گرهٔ داخلی شامل مجموعه‌ای از مستطیل‌ها و اشاره گر به گره‌های فرزند است و هر برگ شامل مستطیلی از اشیای مکانی است (می‌تواند شامل اشیای مکانی هم باشد). به ازای هر گره مستطیل متناظر آن با ورودی مقایسه می‌شود، در صورتی همپوشانی، گرهٔ فرزند هم جستجو می‌شود. جستجو به صورت بازگشتی تا زمانی ادامه پیدا می‌کند که تمام گره‌های دارای هم پوشانی با ورودی پیمایش شوند. اگر گره مورد بررسی برگ باشد، مستطیل دربرگیرنده آن با ورودی مقایسه می‌شود و اشیای موجود در آن (در صورت وجود) که در مستطیل ورودی قرار دارند به جواب اضافه می‌شوند. افزودن عنصر برای افزودن عنصر جدید درخت با شروع از ریشه به صورت بازگشتی پیمایش می‌شود. در هر سطح تمام مستطیل‌های این سطح بررسی می‌شوند و نماینده با استفاده از الگوریتم اکتشافی (مثلاً انتخاب الگوریتمی که کمترین گسترش را نیاز دارد) انتخاب می‌شود. سپس جستجو به صفحهٔ انتخابی تقلیل پیدا می‌کند و این روند تا رسیدن به برگ ادامه می‌یابد. افزودن گره‌ای که تازه ایجاد شده‌است به سطح قبلی می‌تواند منجر به سرریزی در سطح فعلی شود. | ## بخش 3: درخت مستطیلی | انتخاب زیردرخت در هر مرحله الگوریتم افزودن عنصر جدید باید تصمیم گرفته شود که شئ جدید در کدام زیردرخت قرار داده شود. زمانی که شئ به‌طور کامل داخل یک مستطیل قرار می‌گیرد انتخاب واضح است؛ اما زمانی که چندین گزینه وجود دارد، انتخاب زیردرخت می‌تواند بر کارآیی الگوریتم تأثیر زیادی داشته باشد. در درخت مستطیلی کلاسیک اشیاء در زیردرختی قرار داده می‌شوند که کمترین گسترش را نیاز دارد؛ اما در مدل‌های پشرفته تر (مثل درخت مستطیلی ستاره‌ای ) روشی ابتکاری به کار گرفته می‌شود. در صورتی که میزان گسترش مورد نیاز برای دو زیردرخت مساوی باشد، زیردرخت با مساخت کمتر انتخاب می‌شود. کاهش یافتن همپوشانی‌ها در مدل پیشرفته یکی از مزیت‌های اساسی آن نسبت به مدل کلاسیک است. تقسیم گرهٔ پرشده از آن جایی که زمان بررسی تمامی حالات تقسیم عناصر یک گره به دو گرهٔ مجزا به منظور یافتن حالت بهینه نمایی است باید الگوریتمی ابتکاری برای یافتن بهترین تقسیم به کار گرفته شود. در درخت مستطیلی کلاسیک، گاتمَن الگوریتم‌های تقسیم خطی و درجه دو را پیشنهاد کرده‌است. در الگوریتم تقسیم درجهٔ دو به دنبال مستطیل‌هایی می‌گردیم که در بدترین حالت در یک گره قرار می‌گیرند. سپس از بین مستطیل‌های باقی‌مانده، مستطیلی که بیشترین اولویت برای اضافه شدن به یکی از گره‌ها را دارد (یعنی افزودن مستطیل به گره منجر به کمترین افزایش مساحت می‌شود) به گرهٔ مربوطه اضافه می‌کنیم. استراتژی‌های تقسیم دیگری مثل Greene's Split ، روش ابتکاری تقسیم درخت مستطیلی ستاره‌ای یا روش تقسیم خطی پیشنهاد شده توسط Ang و Tan (هرچند می‌تواند مستطیل‌های غیرطبیعی ایجاد کند که برای بسیاری از پرس و جوهای جهان واقعی کارآمد نیستند) برای تقسیم پیشنهاد شده‌است. علاوه برداشتن الگوریتم ابتکاری پیشرفته برای تقسیم گره‌ها، درخت مستطیلی ستاره سعی می‌کند با تکرار کردن عناصر موجود در یک گره از تقسیم شدن آن جلوگیری کند (شبیه روشی که برای گره‌های پر شده در درخت بی مورد استفاده قرار می‌گیرد). درخت ایکس درختی مستطیل ستاره‌ای است که وقتی نمی‌تواند تقسیم مناسبی پیدا کند با جای تقسیم، گره‌ای جدید (موسوم به ابرگره) ایجاد می‌کند و تمام عناصر اضافی را در آن قرار می‌دهد. حذف حذف کردن یک عنصر از صفحه ممکن است نیازمند به روزرسانی مستطیل در برگیرندهٔ صفحهٔ پدر آن باشد. از آن جایی که وقتی یک صفحه پر نشده‌است، نمی‌تواند با همسایه‌هایش در تعادل باشد، صفحه حذف می‌شود تمام فرزندانش (که می‌توانند زیر درخت یا برگ باشند) دوباره به درخت اضافه می‌شوند. | ## جمع‌بندی | در طی این فرایند اگر ریشهٔ درخت تنها یک فرزند داشته باشد، ارتفاع درخت یک واحد کم می‌شود.