درخت کی‌دی

درخت کی‌دی یک نوع درخت دودویی از نوع BSP ( کوتاه شده Binary space partitioning ) است .

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

نقاط سمت چپ ابرصفحه، در زیر درخت سمت چپ آن گره و نقاط سمت راست ابرصفحه، در زیر درخت راست نمایش داده می‌شوند .

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

در این داده ساختار علاوه بر نقاط چند بعدی می‌توان انواع دیگری از متغیرها را نیز ذخیره نمود . به عنوان مثال یک درخت کی دی می‌تواند دربر دارنده مستطیلهای دو یا چند بعدی باشد . یک مستطیل دوبعدی نمایانگر یک شیء ۴ مؤلفه‌ای است ( ۴ نقطه مشخص‌کننده مستطیل ).

در چنین نمونه‌ایی مسئله جستجو تبدیل به یافتن مستطیل‌هایی متقاطع با مستطیل مرجع خواهد شد .

ساخت درخت کی دی

درخت کی دی بر اساس یک مجموعه نمونه داده شده E با الگوریتم زیر ایجاد می‌شود :

Algorithm:         Constructing a KD-tree

Input:             exset,of type exemplar-set

Output:            kd , of type kd tree

Pre:               None

Post:              exset=exset-rep(kd) ^ ls-legal-kdtree(kd)

if exset is empty then return the empty kdtree

call pivot-choosing procedure.which returns two values:

ex := a member of exset                              
split := the splitting dimention

d := domain vector of ex

exset' := exset with ex removed

r := range vector of ex

exsetleft := { ( d' , r') member of exset'|d'split ≤ d split }

exsetright := { ( d' , r') member of exset'|d'split> d split}

kdleft := recursively construct kd-tree from exsetleft

kdright := recursively construct kd-tree from exsetright

kd := <d.r.split.kdleft.kdright>                                  

افزودن یک عنصر

افزودن یک نقطه به درخت کی دی، همانند افزودن یک عنصر به هر درخت جستجوی دیگر است .

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

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

حذف یک عنصر

برای حذف یک عنصر از درخت کی دی بهترین و ساده‌ترین روش آن است که مجموعه فرزندان گره هدف را مشخص کرده و پس از حذف آن گره، با توجه به مجموعه ذخیره شده مجدداً این بخش از درخت را ساخت.

البته روش های دیگری نیز وجود دارند، مثلا اینکه بهترین جایگزین را برای گره ی مورد نظری که میخواهیم از درخت حذف کنیم، پیدا کنیم. اما به‌طور کلی به صرفه از نظر پیچیدگی زمانی نخواهد بود.

ایجاد تعادل (balance) پس از درج یا حذف

تعادل در یک درخت کی دی نیاز به مراقبت دارد زیرا این درختان در ابعاد مختلف طبقه بندی شده اند، بنابراین از روش چرخش درخت نمی توان برای تعادل آن ها استفاده کرد به این دلیل که ممکن است تغییر نا پذیر باشد.

چندین نوع مختلف کی دی وجود دارد که تعادل در آن ها برقرار است، شمال درخت تقسیم شده ی کی دی، درخت شبه کی دی، درخت های hB و درخت Bkd است.

ساختن یک درخت کی دی

ساختن یک درخت کی دی ایستا (static) اگر n گره (عناصر مورد نظر) داشته باشیم در دو حالت بررسی می شود:

حالت اول

اگر از مرتب سازی هایی با پیچیدگی زمانی ${\displaystyle o(nlogn)}$

حالت دوم

اگر از اگوریتم میانه ی میانه ها استفاده شود ${\displaystyle o(nlogn)}$

برای درج و حذف و جست و جو

بررسی پیچیدگی زمانی در بدترین حالت و حالت میانگین