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

Question

我正在为数据结构考试练习，并且一直在研究这个问题:“编写一个算法，在二叉搜索树 T 中找到第 k 个最高节点值. 该算法必须在 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)，因为它的增长速度与树中节点的数量有关，并且与树的深度无关。在只有左 child (链表)的退化树中，您的复杂性仍然相同。

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

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

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