二叉搜索树中的第 N 个最大节点

Question

我试图在给定一个数字的二叉搜索树中找到第 N 个最大的节点。所有其他在线解决方案都找到第 N 个最小的节点，例如这个：

/**
 * Return the key in the symbol table whose rank is {@code k}.
 * This is the (k+1)st smallest key in the symbol table.
 *
 * @param  k the order statistic
 * @return the key in the symbol table of rank {@code k}
 * @throws IllegalArgumentException unless {@code k} is between 0 and
 *        <em>n</em>–1
 */
public Key select(int k) {
    if (k < 0 || k >= size()) {
        throw new IllegalArgumentException("argument to select() is invalid: " + k);
    }
    Node x = select(root, k);
    return x.key;
}

// Return key of rank k. 
private Node select(Node x, int k) {
    if (x == null) return null; 
    int t = size(x.left); 
    if      (t > k) return select(x.left,  k); 
    else if (t < k) return select(x.right, k-t-1); 
    else            return x; 
}

来源：https://algs4.cs.princeton.edu/32bst/BST.java.html

如何转换 select(Node x, int k) 方法来找到第 N 大节点？

例如，在看起来像这样的 BST 中：

       30
     /    \
    20    35
   / \    / \
 15   25 31 40

最大节点的key为40。

排位 BST 看起来像：

        4
     /    \
    6      2
   / \    / \
  7   5  3   1

Answer 1

这个BST需要注意的一点是rank是从0开始的

更简单的方法

对于包含编号为 0 到 (X-1)、

的 X 个元素的 BST

Nth最小元素等价于(X-N)th最大元素，反之亦然

如果实在不行只能换个方法

select 在这种情况下所做的类似于对排名的二进制搜索。因此，如果我们调整它，使其始终向右移动（对于更高的级别），我们可以return我们想要的答案。

反转 x.right 和 x.left:

private Node select(Node x, int k) {
    if (x == null) return null; 
    int t = size(x.right); 
    if      (t > k) return select(x.right,  k); 
    else if (t < k) return select(x.left, k-t-1); 
    else            return x; 
}

二叉搜索树中的第 N 个最大节点

Nth largest node in Binary Search Tree

java

ranking

binary-search-tree