درخت کی دی

درخت کی دی نوعی ساختمان داده است که برای نگه داری نقطه ها در فضای k-بعدی استفاده می شود.درخت کی دی نوعی درخت دودویی است. در واقع می توان گفت این داده ساختار این قبلیت را دارد که بخشی متناهی از یک فضای k-بعدی را ذخیره کند.

نحوه ی ساخت

نقاط ورودی داده ساختار نقاطی در فضای k-بعدی هستند. هر راس از درخت کی دی یک نقطهٔ k-بعدی است و هر راس غیر برگ را می توان یک ابر صفحه در نظر گرفت که فضا را به دو قسمت تقسیم می کند و دو راسی که فرزند این راس هستنند نماینده آن بخش از فضا به حساب می آیند.

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

 
function build_kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;
 
    // Sort point list and choose median as pivot element
    select median by axis from pointList;
 
    // Create node and construct subtree
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

عملیات ها