Рубрики

К Размерное Дерево | Набор 1 (поиск и вставка)

Продвинутые Структуры данных

KD-дерево (также называемое K-мерным деревом) — это двоичное дерево поиска, где данные в каждом узле являются K-мерной точкой в пространстве. Вкратце, это структура данных разделения пространства (подробности ниже) для организации точек в K-мерном пространстве.

Нелистовый узел в дереве KD делит пространство на две части, называемые полупространствами.

Точки слева от этого пространства представлены левым поддеревом этого узла, а точки справа от этого пространства представлены правым поддеревом. Вскоре мы объясним концепцию разделения пространства и формирования дерева.

Для простоты, давайте разберем 2-D Дерево с примером.

Корень будет иметь плоскость, выровненную по x, потомки корня будут иметь плоскости, выровненные по оси y, все внуки корня будут иметь плоскости, выровненные по оси x, а правнуки корня будут иметь плоскости, выровненные по оси y, и так далее.

Обобщение:
Пронумеруем плоскости как 0, 1, 2,… (K — 1). Из приведенного выше примера совершенно ясно, что точка (узел) на глубине D будет иметь выровненную плоскость A, где A рассчитывается как:

A = D мод К

Как определить, будет ли точка лежать в левом поддереве или в правом поддереве?

Если корневой узел выровнен в плоскости A, то левое поддерево будет содержать все точки, координаты которых в этой плоскости меньше, чем у корневого узла. Точно так же правое поддерево будет содержать все точки, чьи координаты в этой плоскости больше или равны координатам корневого узла.

Создание двумерного дерева:
Рассмотрим следующие точки в двумерной плоскости:
(3, 6), (17, 15), (13, 15), (6, 12), (9, 1), (2, 7), (10, 19)

  1. Вставка (3, 6): Поскольку дерево пусто, сделайте его корневым узлом.
  2. Вставка (17, 15): Сравните это с точкой корневого узла. Поскольку корневой узел выровнен по X, значение X-координаты будет сравниваться, чтобы определить, находится ли оно в поддереве прав или в правом поддереве. Эта точка будет Y-выровнена.
  3. Вставка (13, 15): X-значение этой точки больше, чем X-значение точки в корневом узле. Итак, это будет лежать в правом поддереве (3, 6). Снова сравните Y-значение этой точки с Y-значением точки (17, 15) (почему?). Поскольку они равны, эта точка будет лежать в правом поддереве (17, 15). Эта точка будет выровнена по X.
  4. Вставка (6, 12): X-значение этой точки больше, чем X-значение точки в корневом узле. Итак, это будет лежать в правом поддереве (3, 6). Снова сравните Y-значение этой точки с Y-значением точки (17, 15) (почему?). Поскольку 12 <15, эта точка будет лежать в левом поддереве (17, 15). Эта точка будет выровнена по X.
  5. Вставка (9, 1): аналогично, эта точка будет лежать справа от (6, 12).
  6. Вставка (2, 7): аналогичным образом, эта точка будет находиться слева от (3, 6).
  7. Вставка (10, 19): аналогичным образом, эта точка будет находиться слева от (13, 15).

Как пространство разделено?
Все 7 точек будут построены в плоскости XY следующим образом:

  1. Точка (3, 6) разделит пространство на две части: проведите линию X = 3.
  2. Точка (2, 7) разделит пространство слева от линии X = 3 на две части по горизонтали.
    Нарисуйте линию Y = 7 слева от линии X = 3.
  3. Точка (17, 15) разделит пространство справа от линии X = 3 на две части по горизонтали.
    Нарисуйте линию Y = 15 справа от линии X = 3.

  • Точка (6, 12) разделит пространство под линией Y = 15 и справа от линии X = 3 на две части.
    Нарисуйте линию X = 6 справа от линии X = 3 и ниже линии Y = 15.
  • Точка (13, 15) разделит пространство под линией Y = 15 и справа от линии X = 6 на две части.
    Нарисуйте линию X = 13 справа от линии X = 6 и ниже линии Y = 15.
  • Точка (9, 1) разделит пространство между линиями X = 3, X = 6 и Y = 15 на две части.
    Нарисуйте линию Y = 1 между линиями X = 3 и X = 6.
  • Точка (10, 19) разделит пространство справа от линии X = 3 и над линией Y = 15 на две части.
    Нарисуйте линию Y = 19 справа от линии X = 3 и выше линии Y = 15.

Ниже приведена реализация основных операций KD Tree на C ++, таких как поиск, вставка и удаление.

// Программа на C ++ для демонстрации операций дерева KD
#include<bits/stdc++.h>

using namespace std;

  

const int k = 2;

  
// Структура для представления узла дерева kd

struct Node

{

    int point[k]; // Для сохранения k размерной точки

    Node *left, *right;

};

  
// Метод для создания узла дерева KD

struct Node* newNode(int arr[])

{

    struct Node* temp = new Node;

  

    for (int i=0; i<k; i++)

       temp->point[i] = arr[i];

  

    temp->left = temp->right = NULL;

    return temp;

}

  
// Вставляет новый узел и возвращает корень модифицированного дерева
// Параметр глубины используется для определения оси сравнения

Node *insertRec(Node *root, int point[], unsigned depth)

{

    // Дерево пусто?

    if (root == NULL)

       return newNode(point);

  

    // Расчет текущего измерения (кд) сравнения

    unsigned cd = depth % k;

  

    // Сравнить новую точку с корнем в текущем измерении 'cd'

    // и выбираем левое или правое поддерево

    if (point[cd] < (root->point[cd]))

        root->left  = insertRec(root->left, point, depth + 1);

    else

        root->right = insertRec(root->right, point, depth + 1);

  

    return root;

}

  
// Функция для вставки новой точки с заданной точкой в
// KD Tree и возвращаем новый корень. В основном использует выше рекурсивный
// функция "insertRec ()"

Node* insert(Node *root, int point[])

{

    return insertRec(root, point, 0);

}

  
// Утилита для определения, совпадают ли две точки
// в K Пространстве

bool arePointsSame(int point1[], int point2[])

{

    // Сравнить отдельные значения pointinate

    for (int i = 0; i < k; ++i)

        if (point1[i] != point2[i])

            return false;

  

    return true;

}

  
// Поиск точки, представленной как «point []» в дереве KD.
// Параметр глубины используется для определения текущей оси.

bool searchRec(Node* root, int point[], unsigned depth)

{

    // Базовые случаи

    if (root == NULL)

        return false;

    if (arePointsSame(root->point, point))

        return true;

  

    // Текущее измерение вычисляется с использованием текущей глубины и итога

    // размеры (к)

    unsigned cd = depth % k;

  

    // Сравнить точку с корнем по отношению к cd (текущее измерение)

    if (point[cd] < root->point[cd])

        return searchRec(root->left, point, depth + 1);

  

    return searchRec(root->right, point, depth + 1);

}

  
// Поиск точки в дереве KD. В основном использует
// searchRec ()

bool search(Node* root, int point[])

{

    // передать текущую глубину как 0

    return searchRec(root, point, 0);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Node *root = NULL;

    int points[][k] = {{3, 6}, {17, 15}, {13, 15}, {6, 12},

                       {9, 1}, {2, 7}, {10, 19}};

  

    int n = sizeof(points)/sizeof(points[0]);

  

    for (int i=0; i<n; i++)

       root = insert(root, points[i]);

  

    int point1[] = {10, 19};

    (search(root, point1))? cout << "Found\n": cout << "Not Found\n";

  

    int point2[] = {12, 19};

    (search(root, point2))? cout << "Found\n": cout << "Not Found\n";

  

    return 0;

}

Выход:

Found
Not Found

См. Ниже статьи для поиска минимума и удаления операций.

Эта статья составлена Aashish Barnwal . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

К Размерное Дерево | Набор 1 (поиск и вставка)

0.00 (0%) 0 votes