Непрерывность памяти и дерево поиска
Я пытаюсь построить дерево поиска поверх моих результатов. Какое-то k-арное дерево с n листьями в конце. Я ищу решение C ++ и экспериментирую с std::vector но не могу сделать это, так как мне нужна согласованность памяти. Это может быть сделано вложенными векторами, но я не могу этого сделать.
Позвольте мне объяснить детали на примере:
Несортированный результат может быть
Result R = { 4, 7, 8, 3, 1, 9, 0, 2, 2, 9, 6 }
Кроме того, мне нужно дерево с узлами, в моей конкретной задаче — центроиды. Но для простоты я буду использовать здесь искусственные значения.
Я определяю размеры дерева поиска как
Height H = 2
Branch B = 3
Дерево сначала
4 7 8 3 1 9 0 2 2 9 6
Второй шаг
layer_0 1.6 5 8.2
| | |
+-+-+-+-+-+ +-+ +-+-+-+
| | | | | | | | | | | |
layer_1 3 1 0 2 2 3 4 6 7 8 9 9
Последний шаг
layer_0 1.6 5 8.2
| | |
+---+---+ +-+---+ +---+----+
layer_1 0.8 1.6 2.4 4.2 5 5.8 6.4 8.2 8.4
| | | | | | |
+-+ +-+-+ | | | | +-+
layer_2 1 0 2 2 3 4 6 7 8 9 9
Это последнее дерево не является k-арным деревом, так как размеры 0 <= size <= |R|,
В данный момент я экспериментирую с двумя векторами.
std::vector<size_t> layer_2;
std::vector<float> leafs;
std::size_t width, height;
С помощью width а также height было бы возможно перемещаться по leafs, Но я спрашиваю себя, как элегантно подключить leafs а также layer_2?
Как будет выглядеть хорошее решение?
Решение
Примечание. Это решение является непрерывным в том смысле, что оно использует непрерывную структуру данных (вектор или массив) вместо дерева стилей указателя узла, но потенциально может иметь неиспользуемое пространство в структуре данных в зависимости от приложения.
Случай, когда этот подход тратит много места: максимальное количество ветвей на узел велико, но у большинства узлов на самом деле гораздо меньше дочерних элементов. Это не повлияет на то, сколько времени потребуется, чтобы найти листья. На самом деле это компромисс, чтобы сделать это довольно быстро.
рассмотрим 3 ветви дерева с 4 уровнями в непрерывной памяти:
R,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,aba,abb,abc,baa.... где индекс дочерних узлов находится в диапазоне от (parent_index * 3) +1 до (parent_index * 3) +3
Важная оговорка, на которую я ссылался, заключается в том, что у каждого узла всегда должно быть три дочерних пространства в векторе, массиве и т.д. Если узел имеет, скажем, только 2 дочерних элемента, просто заполните это дополнительное пространство значением null_child, чтобы сохранить это пространство. (это откуда пустое пространство)
Преимущество состоит в том, что теперь найти все листья легко.
first_leaf_index = 0
for(i=0;i<(4-1);i++)//in this example 4 is the depth
first_leaf_index += 3^(i) //three is max branches per node
На этом этапе просто итерации до конца структуры данных
Другие решения
Других решений пока нет …