algorithm - 这个算法是O(d)吗，其中d是二叉搜索树的深度

Question

我正在练习数据结构考试，并一直在研究以下问题:“编写一个算法，查找二叉搜索树中的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());
}

Answer 1

您混淆了两个完全不同的变量n和d。 d 是树的深度，n 是节点数。算法的复杂度是 O(n)，因为它的增长速度与树中节点的数量有关，并且与树的深度无关。在只有左子节点的退化树(链表)中，您的复杂性仍然是相同的。

一般来说，O(d) 算法需要使用比较递归步骤，该步骤询问有关当前节点的值的问题并相应地进行遍历(二分搜索)。通过这种方式，您可以使用 BST 的排序属性沿树直接向下移动(相对于 d)。

这也是为什么保持 BST 平衡(AVL/红黑树等)很重要。如果没有平衡，d 就不再有意义，插入/删除/查找的复杂性开始看起来像 n 而不是所需的 O(n log(n))，这是每次迭代时将搜索空间减半的算法的典型复杂度。

话虽如此，如果不使用 order statistic tree 在每个节点中保留附加信息，O(d) 算法是否可行尚不清楚。 (see this answer for details)。