Как называется этот алгоритм поиска структуры данных?

Question

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

мой код работает, но я не знаю, как это назвать. Я думал, что это было Тройное Дерево, пока не прочитал страницу Вики, и это не так. Так что я просто не знаю, как это назвать.

вот мой класс. работает как двоичное дерево без ограничения количества ключей, где набор ключей отправляется в функции поиска / вставки в виде списка. Каждый раз, когда один ключ находит узел, следующий ключ удаляется из списка, и «Дерево следующего ключа» этого узла повторяет процесс до тех пор, пока у него не закончатся ключи и не отправит обратно данные. Я думаю, я могу использовать его для точного поиска категорий, таких как «имя», «имя», «род занятий», «город». они вводятся в той же последовательности, и любое поддерево может быть пройдено. до сих пор не уверен, насколько это лучше, чем обычное двоичное дерево для строк. У меня есть другая точная версия, которая имеет целочисленные ключи, которые могут оказаться более удобными.

public class classTernaryTree_StringKey
{
    classTernaryTree_StringKey_Node cRoot = null;

    public void Insert(ref object data, List<string> lstKeys)
    {
        classTernaryTree_StringKey cMyRef = this;
        _Insert(ref cMyRef, ref data, lstKeys);

    }

    static void _Insert(ref classTernaryTree_StringKey cTree, ref object data, List<string> lstKeys)
    {

        if (cTree.cRoot == null)
        {
            cTree.cRoot = new classTernaryTree_StringKey_Node();
            cTree.cRoot.key = lstKeys[0];
            lstKeys.RemoveAt(0);
            if (lstKeys.Count > 0)
            {
                cTree.cRoot.NextTree.Insert(ref data, lstKeys);
                return;
            }
            else
            {
                cTree.cRoot.data = data;
                return;
            }
        }

        classTernaryTree_StringKey_Node cNode = cTree.cRoot;
        do
        {
            int intComparison = string.Compare(lstKeys[0], cNode.key);
            if (intComparison > 0)
            {
                if (cNode.Right != null)
                    cNode = cNode.Right;
                else
                {
                    cNode.Right = new classTernaryTree_StringKey_Node();
                    cNode.Right.key = lstKeys[0];
                    lstKeys.RemoveAt(0);

                    if (lstKeys.Count > 0)
                    {
                        cNode.Right.NextTree.Insert(ref data, lstKeys);
                        return;
                    }
                    else
                    {
                        cNode.Right.data = data;
                        return;
                    }
                }
            }
            else if (intComparison < 0)
            {
                if (cNode.Left != null)
                    cNode = cNode.Left;
                else
                {
                    cNode.Left = new classTernaryTree_StringKey_Node();
                    cNode.Left.key = lstKeys[0];
                    lstKeys.RemoveAt(0);

                    if (lstKeys.Count > 0)
                    {
                        cNode.Left.NextTree.Insert(ref data, lstKeys);
                        return;
                    }
                    else
                    {
                        cNode.Left.data = data;
                        return;
                    }
                }
            }
            else
            {
                lstKeys.RemoveAt(0);
                if (lstKeys.Count > 0)
                {
                    cNode.NextTree.Insert(ref data, lstKeys);
                    return;
                }
                else
                {
                    cNode.data = data;
                    return;
                }
            }

        } while (true);
    }


    public object Search(List<string> lstKeys)
    {
        classTernaryTree_StringKey cMyRef = this;
        return _Search(ref cMyRef, lstKeys);
    }

    static object _Search(ref classTernaryTree_StringKey cTree, List<string> lstKeys)
    {

        if (cTree.cRoot == null) return null;
        classTernaryTree_StringKey_Node cNode = cTree.cRoot;
        do
        {
            int intComparison = string.Compare(lstKeys[0], cNode.key);
            if (intComparison > 0)
            {
                if (cNode.Right != null)
                    cNode = cNode.Right;
                else
                    return null;
            }
            else if (intComparison < 0)
            {
                if (cNode.Left != null)
                    cNode = cNode.Left;
                else
                    return null;
            }
            else
            {
                lstKeys.RemoveAt(0);
                if (lstKeys.Count > 0)
                    return cNode.NextTree.Search(lstKeys);
                else
                    return cNode.data;
            }
        } while (true);
    }

}

public class classTernaryTree_StringKey_Node
{
    public string key = "";
    public classTernaryTree_StringKey_Node Left = null;
    public classTernaryTree_StringKey_Node Right = null;
    public classTernaryTree_StringKey NextTree = new classTernaryTree_StringKey();
    public object data = null;
}

Answer 1

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

Тернарное дерево поиска - это способ кодирования tr ie структура данных. Попытки - это деревья, представляющие последовательности элементов. Обычно эти элементы являются отдельными персонажами, но в принципе они могут быть чем угодно. Ваша структура данных - это, по сути, троичное дерево поиска, в котором вы храните строки, а не символы в каждом узле.