Найти k-й наименьший элемент в бинарном дереве поиска оптимальным способом

Question

Мне нужно найти k-й наименьший элемент в бинарном дереве поиска без использования статической / глобальной переменной. Как добиться этого эффективно? Решение, которое я имею в виду, заключается в выполнении операции в O (n), наихудшем случае, поскольку я планирую выполнить обход по всему дереву. Но в глубине души я чувствую, что здесь не используется свойство BST. Правильно ли мое предположение или есть лучшее?

Answer 1

IVlad решение с использованием order statistics tree является наиболее эффективным. Но если вы не можете использовать order statistics tree и застряли в обычном старом BST, тогда лучшим подходом будет сделать обход в порядке (как указано в prasadvk). Но его решение неадекватно, если вы хотите вернуть k-й наименьший элемент, а не просто распечатать значение. Кроме того, поскольку его решение является рекурсивным, существует опасность переполнения стека. Поэтому я написал решение Java, которое возвращает k-й наименьший узел и использует стек для выполнения обхода заказа. Время выполнения равно O (n), а сложность пространства равна O (h), где h - максимальная высота дерева.

// The 0th element is defined to be the smallest element in the tree.
public Node find_kth_element(Node root , int k) {

    if (root == null || k < 0) return null;

    Deque<Node> stack = new ArrayDeque<Node>();
    stack.push(root);

    while (!stack.isEmpty()) {

        Node curr = stack.peek();

        if (curr.left != null) {

            stack.push(curr.left);
            continue;
        }

        if (k == 0) return curr;
        stack.pop();
        --k;

        if (curr.right != null) {

            stack.push(curr.right);

        }

    }

    return null;
}

Answer 2

public static Node kth(Node n, int k){
    Stack<Node> s=new Stack<Node>();
    int countPopped=0;
    while(!s.isEmpty()||n!=null){
      if(n!=null){
        s.push(n);
        n=n.left;
      }else{
        node=s.pop();
        countPopped++;
        if(countPopped==k){
            return node;
        }
        node=node.right;

      }
  }

}

Answer 3

Ну, мы можем просто использовать обход по порядку и поместить посещенный элемент в стек. нажмите k раз, чтобы получить ответ.

мы также можем остановиться после k элементов

Answer 4

Я думаю, что это лучше, чем принятый ответ, потому что не нужно изменять исходный узел дерева для хранения количества его дочерних узлов.

Нам просто нужно использовать обход по порядку, чтобы подсчитать наименьший узел слева направо, прекратить поиск, как только счет будет равен K.

private static int count = 0;
public static void printKthSmallestNode(Node node, int k){
    if(node == null){
        return;
    }

    if( node.getLeftNode() != null ){
        printKthSmallestNode(node.getLeftNode(), k);
    }

    count ++ ;
    if(count <= k )
        System.out.println(node.getValue() + ", count=" + count + ", k=" + k);

    if(count < k  && node.getRightNode() != null)
        printKthSmallestNode(node.getRightNode(), k);
}

Answer 5

Решение для полного корпуса BST: -

Node kSmallest(Node root, int k) {
  int i = root.size(); // 2^height - 1, single node is height = 1;
  Node result = root;
  while (i - 1 > k) {
    i = (i-1)/2;  // size of left subtree
    if (k < i) {
      result = result.left;
    } else {
      result = result.right;
      k -= i;
    }  
  }
  return i-1==k ? result: null;
}

Answer 6

http://www.geeksforgeeks.org/archives/10379

это точный ответ на этот вопрос: -

1.использование обхода по порядку за O (n) время 2. Использование дополненного дерева в k + log n раз

Answer 7

Ядро Linux имеет превосходную расширенную красно-черную структуру данных, которая поддерживает операции на основе рангов в O (log n) в linux / lib / rbtree.c.

Очень грубый порт Java также можно найти по адресу http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java, вместе с RbRoot.java и RbNode.java. N-й элемент можно получить, вызвав RbNode.nth (узел RbNode, int n), передав в корень дерева.

Answer 8

я написал аккуратную функцию для вычисления k-го наименьшего элемента. Я использую обход по порядку и останавливается, когда он достигает k-го наименьшего элемента.

void btree::kthSmallest(node* temp, int& k){
if( temp!= NULL)   {
 kthSmallest(temp->left,k);       
 if(k >0)
 {
     if(k==1)
    {
      cout<<temp->value<<endl;
      return;
    }

    k--;
 }

 kthSmallest(temp->right,k);  }}

Answer 9

Лучший подход уже есть. Но я бы хотел добавить простой Код для этого

int kthsmallest(treenode *q,int k){
int n = size(q->left) + 1;
if(n==k){
    return q->val;
}
if(n > k){
    return kthsmallest(q->left,k);
}
if(n < k){
    return kthsmallest(q->right,k - n);
}

}

int size(treenode *q){
if(q==NULL){
    return 0;
}
else{
    return ( size(q->left) + size(q->right) + 1 );
}}

Answer 10

Вот краткая версия в C # , которая возвращает k-й наименьший элемент, но требует передачи k в качестве аргумента ref (это тот же подход, что и @prasadvk):

Node FindSmall(Node root, ref int k)
{
    if (root == null || k < 1)
        return null;

    Node node = FindSmall(root.LeftChild, ref k);
    if (node != null)
        return node;

    if (--k == 0)
        return node ?? root;
    return FindSmall(root.RightChild, ref k);
}

Это O (log n), чтобы найти наименьший узел, а затем O (k), чтобы пройти к k-му узлу, так что это O (k + log n).