در علوم رایانه، درخت کی دی ( کوتاه شده درخت 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> افزودن یک عنصر افزودن یک نقطه به درخت کی دی، همانند افزودن یک عنصر به هر درخت جستجوی دیگر است .
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین درخت، داده ساختاری است برای ذخیره سازی مجموعه متناهی از یک فضای 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> افزودن یک عنصر افزودن یک نقطه به درخت کی دی، همانند افزودن یک عنصر به هر درخت جستجوی دیگر است .
wiki: درخت کی دی