Поддержание порядка списка в двоичном дереве - PullRequest
Новая
       2

Поддержание порядка списка в двоичном дереве

3 голосов
/ 17 февраля 2011

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

Как создать метод вставки, соответствующий этому требованию?

Помните, что дерево должно быть сбалансированным, поэтому не существует абсолютно тривиального решения. Я пытался сделать это с помощью модифицированной версии дерева AVL, но я не уверен, что это сработает.

Я также хотел бы иметь возможность реализовать операцию удаления. Удалить следует удалить элемент в i-й позиции в списке.

Редактировать: уточнение:

Я хочу иметь: Insert (i, e), которая вставляет один элемент e прямо перед i-м элементом в последовательности. Delete (i), который удаляет i-й элемент последовательности.

Если я вставлю (0, 5), вставлю (0, 4), вставлю (0, 7), то моя сохраненная последовательность теперь будет 7, 4, 5, а обход по двоичному дереву должен дать мне 7, 4, 5.

Если я удаляю (1), то обход по бинарному дереву должен дать мне 7, 5. Как вы можете видеть, порядок последовательности сохраняется после удаления i-го элемента последовательности с i = 1 в этом случае (как Я проиндексировал мою последовательность от 0).

Ответы [ 3 ]

1 голос
/ 17 февраля 2011

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

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

Вот немного кода на C ++. Обратите внимание, что «конец» относится к индексу элемента после конца текущего сегмента массива. 

struct Node {
    Node(int v) : value(v), l(0), r(0) {}

    int value;
    Node* l;
    Node* r;
};

Node* vector_to_tree(int begin, int end, int array[]) {
    if (begin == end)
        return NULL;

    Node* root = new Node(array[begin++]);
    int mid = (begin + end) / 2;
    root->l = vector_to_tree(begin, mid, array);
    root->r = vector_to_tree(mid,   end, array);

    return root;
}

void preorder_traverse(Node* root) {
    if (!root)
        return;

    std::cout << root->value << std::endl;
    traverse(root->l);
    traverse(root->r);
}
1 голос
/ 18 февраля 2011

Это можно сделать с помощью дерева AVL.

Добавление элементов в дерево AVL путем добавления к крайнему правому узлу дерева.

Балансировка AVL не влияет на свойство обхода заказа из-за характера вращений.

Сохранение размера дерева на каждом узле и поддержание этих значений для каждого узла, на который повлияли операции вставки / удаления / балансировки, можно выполнить за O (log n). Хранение размера дерева в каждом узле позволяет искать элемент по рангу в последовательности, поскольку ранг элемента в дереве известен по размеру левого дочернего узла + 1.

Удаление из дерева AVL можно выполнить, заменив удаленный узел самым левым узлом правого поддерева узла.

Операции вставки и удаления затем выполняются за O (log n), поскольку дерево всегда сбалансировано, а обновления размера на узлах выполняются по пути от вставленного / удаленного узла к корню.

Поскольку не существует структуры вспомогательных данных, кроме двоичного дерева, могут быть выполнены другие операции, которые получают выгоду от дерева, например, поиск суммы диапазона [m, n] элементов в последовательности в O (log n ) время.

1 голос
/ 17 февраля 2011

Хранить связанный список в дереве.У вас уже есть указатели / ссылки на узлы благодаря дереву.Когда вы вставляете в дерево, также вставляйте в конце связанного списка.При удалении из дерева, удалить из связанного списка.Поскольку у вас есть ссылки, все они являются операциями O (1), и вы можете выполнять итерацию в порядке вставки, если захотите.

Редактировать: чтобы прояснить проблему Барта, вот реализация Java 

class LinkedTreeNode<E> {
   E data;
   LinkedTreeNode<E> parent;
   LinkedTreeNode<E> left;
   LinkedTreeNode<E> right;
   LinkedTreeNode<E> insertNext;
   LinkedTreeNode<E> insertPrev;
}

class LinkedTree<E> {
    LinkedTreeNode<E> root;
    LinkedTreeNode<E> insertHead;
    LinkedTreeNode<E> insertTail;

    // skip some stuff
    void add(E e) {
        LinkedTreeNode<E> node = new LinkedTreeNode<E>(e);

        // perform the tree insert using whatever method you like

        // update the list
        node.insertNext = insertTail;
        node.insertPrev = insertTail.insertPrev.insertPrev;
        node.insertPrev.insertNext = node;
        insertTail.insertPrev = node;
    }

    E remove(E e) {
        LinkedTreeNode<E> rem = // whatever method to remove the node
        rem.insertNext.insertPrev = rem.insertPrev;
        rem.insertPrev.insertNext = rem.insertNext;
        return rem.data;
    }
}
...