Поиск и вставка в K-мерное дерево

Опубликовано: 26 Февраля, 2023

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

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

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

Для простоты давайте разберемся с двумерным деревом на примере.

Корень будет иметь плоскость, выровненную по оси X, дочерние элементы корня будут иметь плоскости, выровненные по оси Y, все внуки корня будут иметь плоскости, выровненные по оси X, а все правнуки корня будут иметь плоскости, выровненные по оси Y, и так далее.

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

А = D по модулю К

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

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

Создание 2-D дерева:
Рассмотрим следующие точки на двумерной плоскости:
(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 = 13.
  • Точка (10, 19) разделит пространство справа от линии X = 3 и выше линии Y = 15 на две части.
    Нарисуйте линию Y = 19 справа от линии X = 3 и выше линии Y = 15.

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

Выход:

Found
Not Found

Обратитесь к статьям ниже, чтобы найти минимальные и удалить операции.

  • Дерево KD (найти минимум)
  • Дерево KD (Удалить)

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ