درخت کی‌دی

درخت کی دی بر اساس یک مجموعه نمونه داده شده 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>                                  

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

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

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

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

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

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

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

اگر از مرتب سازی هایی با پیچیدگی زمانی ${\displaystyle o(nlogn)}$ مانند هیپ یا مرج سورت برای یافتن میانه استفاده شود برابر است با ${\displaystyle o(nlogn^{2})}$

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