Печать преемника и предшественника в BST

Хотя вы правы в том, что поиск последовательного преемника или предшественника может занять O(h) времени, оказывается, что если вы начинаете с наименьшего значения в BST и неоднократно находите его преемника, общий объем проделанной работы в конечном итоге составит до O(n) независимо от формы дерева.

На интуиции для этого нужно подумать о том, сколько раз вы проходите каждое ребро в дереве при итеративном поиске преемника. В частности, вы посетите каждое ребро в дереве ровно дважды: один раз, когда вы спускаетесь в поддерево, и один раз, когда вы выходите из него, посетив каждый узел в этом поддереве. Поскольку дерево с n узлами имеет O (n) ребер, для его завершения требуется время O (n).

Если вы скептически относитесь к этому, попробуйте написать простую программу, чтобы проверить это. Я помню, как не поверил этому результату, когда впервые услышал его, пока не написал программу, подтверждающую его. :-)

В псевдокоде логика выглядела бы так:

1. Найдите наименьшее значение в дереве, начиная с корня и многократно следуя за левым дочерним указателем, пока такой указатель не исчезнет.
2. Until all nodes are visited, remember the current node and find its successor as follows:
   1. If the current node has a right child:
      1. Go right.
      2. Идите налево, пока не останется детей.
      3. Выведите узел, с которого вы начали, затем этот узел. 2: В противном случае:
      4. Подойдите к родительскому узлу, пока не обнаружите, что узел, с которого вы начали, был левым дочерним элементом своего родителя.
      5. Если вы попали в корень и так и не обнаружили, что перешли от левого дочернего элемента вверх, все готово.
      6. В противном случае выведите узел, который вы помните, а затем текущий узел.

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

Оли прав в том, что неупорядоченный обход — это O(n), но вы правы в том, что использование общих процедур преемника/предшественника увеличит алгоритмическую сложность. Так:

Простым решением было бы пройтись по дереву, используя обход по порядку, отслеживая последний раз, когда вы взяли ребро, указывающее вправо (например, используя переменную с именем last_right_ancestor_seen, чтобы указать на его родителя). узел) и последний просмотренный вами листовой узел (скажем, в last_leaf_seen (фактически любой узел без правого дочернего элемента). Каждый раз, когда вы обрабатываете листовой узел, его предшественником является last_right_ancestor< /strong>, и каждый раз, когда вы сталкиваетесь с неконечным узлом, его предшественником является last_leaf_seen, и вы просто печатаете два O(n) времени, O(1) пространства.

walk(node* current, node* last_right_ancestor_seen, node* last_leaf_seen) {

    if(current->left != null) {
        walk(current->left, last_right_ancestor_seen, last_leaf_seen);
    }

    if(current->is_leaf()) {
            if(last_right_ancestor_seen != null)
                print(last_right_ancestor_seen->value, current->value);
    }
    else {
        print(last_leaf_seen->value, current->value);
    }

    if(current->right != null) {
        *last_right_ancestor_seen = *current;
        walk(current->right, last_right_ancestor_seen, last_leaf_seen);
    }
    else {
        *last_leaf_seen = *current;
    }

}