这个算法是O(d)，其中d是二叉查找树的深度

Question

我正在练习数据结构考试，并一直在研究这个问题：“编写一个算法，在二叉搜索树 T 中找到第 k 个最高节点值。算法必须在O（d）中运行，其中d是树的深度。

我想出了这个（几个小时后），但不确定运行时，我已经遍历了树两次，这是2d吗？我还希望得到一些关于如何减少我使用的方法数量的建议（如果可能的话）。

下面是我的答案，使用递归帮助器方法来计算树中节点的数量和有序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的sorted属性在树中直接向下移动(相对于< code>d)。

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

话虽如此，如果不使用阶次统计树在每个节点中保留其他信息，则不清楚 O（d） 算法是否可行（有关详细信息，请参阅此答案）。