درخت کیدی
در علوم رایانه، درخت کیدی (کوتاه شده درخت K بعدی) یک ساختمان داده برای سازماندهی نقاط در فضای k-بعدی است. در واقع این درخت، داده ساختاری است برای ذخیره سازی مجموعه متناهی از یک فضای K بعدی.
این درخت، یک داده ساختار مفید برای بسیاری از برنامههای کاربردی است، مانند جست و جوهایی که شامل کلید واژههای جست و جوی چند بعدی هستند.
محتویات |
مشخصات کلی [ویرایش]
درخت کیدی یک نوع درخت دودویی از نوع 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>
افزودن یک عنصر [ویرایش]
افزودن یک نقطه به درخت کی دی، همانند افزودن یک عنصر به هر درخت جست و جوی دیگر است .
ابتدا درخت را به این صورت پیمایش میکنیم که از ریشهٔ درخت شروع کرده و سپس با توجه به این که نقطه ای که میخواهیم درج کنیم در سمت راست صفحه جداکننده قرار دارد یا در سمت چپ به فرزند راست یا چپ می رویم ،
این کار را تا رسیدن به گره ای که این نقطه باید به عنوان فرزند آن درج شود ادامه داده و در آخر با توجه به این که نقطه مورد نظر در سمت راست صفحه جداکننده گره قرار دارد یا در سمت چپ، به عنوان فرزند راست یا چپ آن درج می شود. البته افزودن نقاط با این روش ممکن است موجب شود درخت نامتوازن شود و این امر کارآیی را کاهش می دهد.
حذف یک عنصر [ویرایش]
برای حذف یک عنصر از درخت کی دی بهترین و سادهترین روش آن است که مجموعه فرزندان گره هدف را مشخص کرده و پس از حذف آن گره، با توجه به مجموعه ذخیره شده مجددا این بخش از درخت را ساخت.
منابع [ویرایش]
 |
این یک نوشتار خُرد پیرامون رایانه است. با گسترش آن به ویکیپدیا کمک کنید. |
