Является ли этот алгоритм O (d), где d - глубина бинарного дерева поиска - PullRequest
Новая
       15

Является ли этот алгоритм O (d), где d - глубина бинарного дерева поиска

1 голос
/ 11 июня 2019

Я тренируюсь на экзамене по структурам данных и работаю над вопросом: «Напишите алгоритм, который находит kth самое высокое значение узла в двоичном дереве поиска T .алгоритм должен работать в O (d), где d - глубина дерева. "

Я пришел с этим (через несколько часов) и не уверен насчет времени выполнения, я дважды прошел дерево,это 2d и поэтому просто d?Я также надеялся получить несколько советов о том, как уменьшить количество используемых мной методов (если это возможно).

Вот мой ответ, использующий рекурсивный вспомогательный метод для подсчета количества узлов в дереве ипорядок DFS: 

public int getKthHighestValue(Node root, int k) {
    int nodeCount = countNodes(root);
    if (k < 0 || k > nodeCount)
        return -1;
    ArrayList<Integer> nodeList = new ArrayList<>();
    getNodeValues(root, nodeList);
    return nodeList.get(k-1);
}

private void getNodeValues(Node root, ArrayList<Integer> nodeList) {
    if (root == null) {
        return;
    }
    getNodeValues(root.getLeft(), nodeList);
    nodeList.add(root.getValue());
    getNodeValues(root.getRight(), nodeList);
}


private int countNodes(Node root) {
    if (root == null) {
        return 0;
    }
    return 1 + countNodes(root.getLeft()) + countNodes(root.getRight());
}

Ответы [ 2 ]

5 голосов
/ 11 июня 2019

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

Говоря в общем, алгоритм O (d) влечет за собой использование сравнительного рекурсивного шага, который задает вопросы о значении текущего узла и перемещается соответственно (бинарный поиск). Таким образом, вы можете двигаться вниз по дереву (относительно d), используя отсортированное свойство BST.

Именно поэтому важно поддерживать баланс BST (AVL / красно-чёрное дерево и т. Д.). Без баланса d больше не имеет смысла, и сложность для вставок / удалений / поисков начинает выглядеть как n вместо желаемого O (n log (n)), что является типичной сложностью для алгоритмов, которые сокращают поиск пробел пополам на каждой итерации.

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

0 голосов
/ 11 июня 2019

Предположим, n = количество элементов в дереве.
Сложность времени выполнения для countNodes(Node root) равна O(n) - он посещает каждый узел только один раз, такая же сложность имеет getNodeValues(Node root, ArrayList<Integer> nodeList) по той же причине.

Учитывая, что вы используете эти 2 метода в int getKthHighestValue(Node root, int k) один за другим, и мы можем опустить константы при вычислении сложности времени выполнения в терминах big O, НЕТ - сложность времени выполнения ваших алгоритмов равна O(n), а не O(d).

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

...