Эффективно преобразовать массив в декартово дерево

Question

Я знаю, как преобразовать массив в декартово дерево в O(N) времени

1. http://en.wikipedia.org/wiki/Cartesian_tree и
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor RMQ в LCA

Однако объем требуемой памяти слишком велик (константы), так как мне нужно связать левый и правый указатель, по крайней мере, с каждым узлом в декартовом дереве.

Может ли кто-нибудь связать меня с проделанной работой по сокращению этих констант (надеюсь до 1)?

Answer 1

Вам не нужно сохранять правый и левый указатели, связанные с вашими декартовыми узлами дерева. Вам просто нужно сохранить родителя каждого узла и по определению декартового дерева (декартово дерево массива A[0, N - 1] является двоичным деревом C(A), корень которого является минимальным элементом A, помеченным с позицией i этого минимума. Левым потомком корня является декартово дерево A[0, i - 1], если i > 0. В противном случае дочернего элемента нет. Правый дочерний элемент определяется аналогично A[i + 1, N - 1].), Вы можете просто пройти через этот массив, и если родительский узел имеет более низкий индекс, чем сам узел, чем узел, будет правым сыном своего родителя, и аналогично, если родительский узел имеет более высокий индекс чем узел останется сыном своего родителя.

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

Answer 2

Можно построить декартово дерево только с дополнительным пространством для ссылок между дочерними элементами (по индексу): поэтому, помимо входного массива, вам понадобится массив равного размера, содержащий значения индекса, которые относятся к первому массиву. Если мы назовем этот дополнительный массивparentOf, тогда array[parentOf[i]] будет родителем array[i], кроме случаев, когда array[i]это корень. В этом случаеparentOf[i] должен быть похож на указатель NIL (или, например, -1).

Статья Википедии на декартовых деревьев, дает простой метод строительства:

Один из способов - просто обработать значения последовательности в порядке [...] слева направо в структуре, которая позволяет обход дерева как вверх, так и вниз.

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

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

Идя по этому пути в противоположном направлении от листа, отслеживайте родителя и его правого ребенка (откуда вы пришли). Как только вы найдете точку вставки, этот дочерний элемент получит новый узел в качестве родителя, а новый дочерний элемент получит "старый" родительский элемент в качестве своего родителя.

Ни в коем случае в этом процессе вам не нужно хранить указатели на детей.

Вот алгоритм, написанный на JavaScript. Например, дерево заполняется из входного массива [9,3,7,1,8,12,10,20,15,18,5]. Только для проверки печатаются как входной массив, так и родительские ссылки:

class CartesianTree {
    constructor() {
        this.values = [];
        this.parentOf = [];
    }
    extend(values) {
        for (let value of values) this.push(value);
    }
    push(value) {
        let added = this.values.length; // index of the new value
        let parent = added - 1; // index of the most recently added value
        let child = -1; // a NIL pointer
        this.values.push(value);
        while (parent >= 0 && this.values[parent] > value) {
            child = parent;
            parent = this.parentOf[parent]; // move up
        }
        // inject the new node between child and parent
        this.parentOf[added] = parent;
        if (child >= 0) this.parentOf[child] = added;
    }
}

let tree = new CartesianTree;
tree.extend([9,3,7,1,8,12,10,20,15,18,5]);

printArray("indexes:", tree.values.keys());
printArray(" values:", tree.values);
printArray("parents:", tree.parentOf);

function printArray(label, arr) {
    console.log(label, Array.from(arr, value => (""+value).padStart(3)).join(" "));
}

Answer 3

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

http://en.wikipedia.org/wiki/Binary_heap