M способ поиска дерева

Question

Я хотел бы реализовать m-way search tree, и мне нужны основы реализации m-way search tree. Может ли кто-нибудь предоставить мне хорошие ресурсы, которые помогут мне в реализации того же ??

Answer 1

Большинство m-way деревьев поиска работают путем хранения (m-1) ключей в отсортированном порядке в каждом узле.Эти значения затем разделяют элементы на m областей: m-2 области, ограниченные между (m-1) клавишами, одна область меньше, чем самая левая клавиша, и одна область больше, чем самая большая клавиша.Например, узел в четырехстороннем дереве может выглядеть следующим образом:

       1              3              7
x < 1    1 < x < 3      3 < x < 7     7 < x

Чтобы выполнить поиск, вы начинаете с корня дерева и сравниваете элемент с каждым из значений, хранящихся в узле.,В зависимости от того, к какой группе он принадлежит, либо сообщите, что узел найден, либо спуститесь вниз в соответствующий дочерний элемент.

Фактическая механика того, как вы вставляете и удаляете узлы, зависит от типа используемого вами многогранного дерева, простоНапример, как в двоичном дереве поиска вставка и удаление зависят от типа дерева (AVL, Splay, Red / Black и т. д.).Хорошей отправной точкой может быть B-дерево , возможно, самое известное из m-way деревьев.Знаменитый учебник CLRS имеет целую главу, посвященную структуре, которая была бы отличным ресурсом для алгоритмических деталей.

Надеюсь, это поможет!

Answer 2

Может быть, вы хотите искать троичное дерево? Тройное дерево - это структура данных, подобная древовидной структуре, но, подобно дереву патриций или дереву критических битов, оно использует B-дерево в качестве модели типа или дерева. Карт-три тоже хорошая отправная точка.