Как реализовать древовидную структуру, но при этом иметь возможность ссылаться на нее как на плоский массив по индексу?

Question

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

    a1
       b1
       b2
       b3
    c1
       d1
          e1
          e2
       d2
          f1

Было бы представлено в виде плоской структуры, как я изложил (т.е.; a1 = 0, b1 = 1, d1 = 5 и т. Д.)

В идеале, я бы хотел, чтобы поиск по индексу был O (1), и поддерживал бы вставку, добавление, удаление и т. Д. С бонусом, что он безопасен для потоков, но если это невозможно, дайте мне знать.

Answer 1

Если у вас достаточно сбалансированное дерево, вы можете получить индексированные ссылки за O (log n) - просто сохраните в каждом узле счетчик количества узлов под ним и обновите счетчик по пути до измененного листа когда вы делаете вставки, удаления и т. д. Затем вы можете вычислить индексированный доступ, посмотрев на число узлов на каждом дочернем элементе, когда вы спускаетесь из корня. Насколько важно для вас, чтобы индексированные ссылки были O (1) вместо O (log n)?

Если изменения нечасты в отношении доступа, вы можете вычислить побочный вектор указателей на узлы, когда закончите с набором изменений, выполнив обход дерева. Тогда вы можете получить O (1) доступ к отдельным узлам, ссылаясь на боковой вектор, до следующего изменения дерева. Стоимость состоит в том, что вам нужно выполнить обход дерева O (n) после внесения изменений, прежде чем вы сможете вернуться к поиску узлов O (1). Ваш шаблон доступа таков, что это будет хорошим компромиссом для вас?

Answer 2

Я использую нечто похожее на это в универсальном красно-черном дереве, которое я использую. По сути, для начала вам нужен класс-оболочка типа Tree, который содержит фактические узлы.

Это основано на возможности ссылаться на дерево по индексу

Таким образом, вы можете сделать что-то вроде следующего, чтобы настроить дерево с ключом, значением

class Tree<K, V>
{
    //constructors and any methods you need

    //Access the Tree like an array
    public V this[K key]
    {
        get {
            //This works just like a getter or setter
            return SearchForValue(key);
        }
        set {
            //like a setter, you can use value for the value given
            if(SearchForValue(key) == null)
            {
                // node for index doesn't exist, add it
                AddValue(key, value);
            } else { /* node at index already exists... do something */ }
     }
}

Это работает при условии, что вы уже знаете, как создать дерево, но хотите иметь возможность делать такие вещи, как доступ к дереву по индексу. Теперь вы можете сделать что-то вроде этого:

Tree<string,string> t = new Tree<string,string>();
t["a"] = "Hello World";
t["b"] = "Something else";
Console.Writeline("t at a is: {0}", t["a"]);

Наконец, для обеспечения безопасности потоков вы можете добавить объект к вашему классу Tree, и для любого метода, доступного внешнему миру, просто вызовите

Lock(threadsafetyobject) { /*Code you're protecting */ }

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

И последнее: я переписал код, чтобы сделать это из памяти, чтобы он не компилировался, но он должен быть закрыт:)

Answer 3

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

Answer 4

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

Однако, как отмечают другие, в большинстве случаев проще проходить дерево напрямую как связанные узлы. Часто используемая реализация массива дерева представляет собой двоичное дерево поиска, поскольку для узла n родительский элемент равен (n-1)/2, левый дочерний элемент равен 2n+1, а правый дочерний элемент равен 2n+2

.

Недостатком использования массивов являются вставки, удаления, обрезка и пересадка - все (обычно) требуют изменения массива при изменении дерева.

Вы также можете прочитать о B-деревьях

Answer 5

Это возможно с небольшой работой, но ваши методы вставки и удаления станут намного более дорогостоящими. Чтобы правильно упорядочить массив, вам нужно сместить большие порции данных, чтобы создать или заполнить пространство. Единственное очевидное преимущество - очень быстрый обход (минимальное количество кешей).

Как бы то ни было, одним из решений является сохранение количества дочерних элементов в каждом узле, например:

struct TreeNode
{
    int numChildren;
    /* whatever data you like */
};

Вот пример того, как пройти по дереву ...

TreeNode* example(TreeNode* p)
{
    /* do something interesting with p */

    int numChildren = p->numChildren;
    ++p;
    for(int child = 1; child <= numChildren; ++child)
       p = example(p);
    return p;
}

Надеюсь, что вы можете извлечь, удалить и т.д. самостоятельно.

:)

Answer 6

Если у вас есть определенное количество дочерних элементов для каждого дерева (например, Двоичное дерево ), то это не так уж сложно (хотя вы потенциально тратите много места).

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

Я не вижу, как это было бы полезно сделать, хотя. Смысл деревьев в том, чтобы иметь возможность хранить и извлекать элементы ниже определенного узла. Если вам нужен постоянный поиск по индексу, это совсем не похоже на дерево. Храня его в массиве, вы должны учитывать тот факт, что если вы добавите элемент в середину, все индексы, которые вы изначально сохранили, будут недействительными.

Однако, если вы действительно хотите дерево и вам все еще требуется вставка / поиск в постоянном времени, просто сохраните ссылку на родительский узел в переменной, а затем вставьте дочерний элемент под ним. Это является постоянным временем.