N-й по величине узел в дереве двоичного поиска - PullRequest
Новая
       39

N-й по величине узел в дереве двоичного поиска

0 голосов
/ 15 ноября 2018

Я пытаюсь найти 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

Самый большой узел имеет ключ 40.

Рейтинг BST будет выглядеть так: 

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

1 Ответ

0 голосов
/ 15 ноября 2018

Об этом BST следует отметить, что ранг начинается с 0.

Более простой способ

Для BST, содержащего X пронумерованных элементов 0 to (X-1),

Наименьший элемент Nth эквивалентен наибольшему элементу (X-N)th, и наоборот.

Если у вас нет выбора, кроме как изменитьmethod

В этом случае выбор делает что-то вроде бинарного поиска по рангу.Поэтому, если мы настроим его так, чтобы он всегда шел вправо для меньших рангов (и оставил для более высоких рангов), мы сможем вернуть желаемый ответ.

Инвертировать 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; 
}
...