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

112

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

bragboy
источник
7
Дерево сбалансировано?
kennytm
Это не. Но если бы все было сбалансировано, есть ли оптимальный путь?
bragboy
1
Если вы выполните поиск по «Статистике заказов», вы найдете то, что вам нужно.
RAL
Мне кажется, что большинство ответов ниже, хотя правильные - это обман, поскольку они используют какую-то глобальную переменную (будь то ссылка на целое число или переменная, которая уменьшается и возвращается). Если абсолютно ничего из этого не разрешено, я бы использовал рекурсию без передачи каких-либо ссылок.
Хенли Чиу,

Ответы:

170

Вот лишь краткое изложение идеи:

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

Мы можем дополнить BST, чтобы каждый узел в нем сохранял количество элементов в своем левом поддереве (предположим, что левое поддерево данного узла включает этот узел). С помощью этой части информации легко пройти по дереву, неоднократно запрашивая количество элементов в левом поддереве, чтобы решить, делать ли рекурсию в левое или правое поддерево.

Теперь предположим, что мы находимся в узле T:

  1. Если k == num_elements (левое поддерево T) , то ответ, который мы ищем, - это значение в node T.
  2. Если k> num_elements (левое поддерево T) , то, очевидно, мы можем игнорировать левое поддерево, потому что эти элементы также будут меньше kth наименьшего. Итак, мы сводим задачу к поиску k - num_elements(left subtree of T)наименьшего элемента правого поддерева.
  3. Если k <num_elements (левое поддерево T) , то kнаименьший по kразмеру элемент находится где-то в левом поддереве, поэтому мы сводим проблему к поиску th наименьшего элемента в левом поддереве.

Анализ сложности:

Это требует O(depth of node)времени, что O(log n)в худшем случае для сбалансированного BST или O(log n)в среднем для случайного BST.

Для BST требуется O(n)хранилище, а O(n)для хранения информации о количестве элементов требуется другое . Все операции BST требуют O(depth of node)времени, и требуется O(depth of node)дополнительное время для поддержания информации о «количестве элементов» для вставки, удаления или вращения узлов. Следовательно, хранение информации о количестве элементов в левом поддереве сохраняет пространственную и временную сложность BST.

IVlad
источник
59
Чтобы найти N-й наименьший элемент, вам нужно только сохранить размер левого поддерева. Вы можете использовать размер правого поддерева i, если хотите найти N-й по величине элемент. На самом деле, вы можете сделать это дешевле: сохранить общий размер дерева в корне и размер левого поддерева. Когда вам нужно изменить размер правого поддерева, вы можете вычесть размер левого из общего размера.
Джерри Коффин,
37
Такой расширенный BST называется «деревом статистики заказов».
Дэниел
10
@Ivlad: на шаге 2: я думаю, что «k - num_elements» должно быть «k - num_elements -1», так как вы также должны включить корневой элемент.
understack
1
@understack - нет, если вы предполагаете, что корень является частью поддерева.
IVlad
16
Если дерево не содержит поля, содержащего «количество элементов в его левом и правом поддереве», тогда метод будет BigO (n), так как вам нужно будет пройти по правому или левому поддереву в каждом узле, чтобы вычислить индекс k текущего узла.
Роберт С. Барнс
68

Более простым решением было бы выполнить обход по порядку и отслеживать элемент, который в настоящее время должен быть напечатан (без его печати). Когда мы дойдем до k, распечатайте элемент и пропустите оставшуюся часть обхода дерева.

void findK(Node* p, int* k) {
  if(!p || k < 0) return;
  findK(p->left, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->right, k); 
}
прасадвк
источник
1
+1: Идея в правильном направлении, но некоторые недостатки, возможно, необходимо исправить; см. stackoverflow.com/a/23069077/278326
Арун,
1
Мне нравится это решение, так как BST уже заказан, обхода должно быть достаточно.
Мерлин
3
Если n близко к общему количеству узлов в этом дереве, вашему алгоритму потребуется время O (n) для завершения, что плохо для выбранного ответа-O (log n)
Spark8006 02
13
public int ReturnKthSmallestElement1(int k)
    {
        Node node = Root;

        int count = k;

        int sizeOfLeftSubtree = 0;

        while(node != null)
        {

            sizeOfLeftSubtree = node.SizeOfLeftSubtree();

            if (sizeOfLeftSubtree + 1 == count)
                return node.Value;
            else if (sizeOfLeftSubtree < count)
            {
                node = node.Right;
                count -= sizeOfLeftSubtree+1;
            }
            else
            {
                node = node.Left;
            }
        }

        return -1;
    }

это моя реализация на C # на основе алгоритма выше, я просто подумал, что опубликую его, чтобы люди могли лучше понять, что он работает для меня

спасибо IVlad

Para
источник
11

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

public static int kthSmallest (Node pivot, int k){
    if(pivot == null )
        return k;   
    k = kthSmallest(pivot.left, k);
    k--;
    if(k == 0){
        System.out.println(pivot.value);
    }
    k = kthSmallest(pivot.right, k);
    return k;
}
Сумит Балани
источник
Думаю, ваше решение лучше с точки зрения пространственной сложности по сравнению с расширенным BST.
zach
Поиск не прекращается даже после того, как найден k-й наименьший элемент.
Vineeth Chitteti
10

// добавляем версию java без рекурсии

public static <T> void find(TreeNode<T> node, int num){
    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();

    TreeNode<T> current = node;
    int tmp = num;

    while(stack.size() > 0 || current!=null){
        if(current!= null){
            stack.add(current);
            current = current.getLeft();
        }else{
            current = stack.pop();
            tmp--;

            if(tmp == 0){
                System.out.println(current.getValue());
                return;
            }

            current = current.getRight();
        }
    }
}
Цзяцзи Ли
источник
Мне нравится это решение и соответствующее рекурсивное решение. Честно говоря, большинство ответов на этот вопрос слишком запутаны / сложны для чтения.
Хенли Чиу
Обожаю это решение! Понятно и здорово!
Rugal
Это решение проходит по дереву «по порядку» и уменьшает счетчик после посещения узла, чтобы позже остановиться, когда счетчик станет равным нулю. Тогда худший случай имеет порядок O (n). Не самое оптимальное по сравнению с рекурсивными решениями @ IVlad, для которых в худшем случае требуется O (log n)
Хорхе П.
4

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

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

Джерри Гроб
источник
4

Рекурсивная прогулка по порядку со счетчиком

Time Complexity: O( N ), N is the number of nodes
Space Complexity: O( 1 ), excluding the function call stack

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

// Private Helper Macro
#define testAndReturn( k, counter, result )                         \
    do { if( (counter == k) && (result == -1) ) {                   \
        result = pn->key_;                                          \
        return;                                                     \
    } } while( 0 )

// Private Helper Function
static void findKthSmallest(
    BstNode const * pn, int const k, int & counter, int & result ) {

    if( ! pn ) return;

    findKthSmallest( pn->left_, k, counter, result );
    testAndReturn( k, counter, result );

    counter += 1;
    testAndReturn( k, counter, result );

    findKthSmallest( pn->right_, k, counter, result );
    testAndReturn( k, counter, result );
}

// Public API function
void findKthSmallest( Bst const * pt, int const k ) {
    int counter = 0;
    int result = -1;        // -1 := not found
    findKthSmallest( pt->root_, k, counter, result );
    printf("%d-th element: element = %d\n", k, result );
}

Примечания (и отличия от решения @prasadvk):

  1. if( counter == k )test требуется в трех местах: (а) после левого поддерева, (б) после корня и (в) после правого поддерева. Это необходимо для того, чтобы обеспечить обнаружение k-го элемента для всех местоположений , т.е. независимо от того, в каком поддереве он находится.

  2. if( result == -1 )test требуется для обеспечения печати только элемента результата , в противном случае печатаются все элементы, начиная с k-го наименьшего до корня.

Arun
источник
Временная сложность для этого решения равна O(k + d), где d- максимальная глубина дерева. Поэтому он использует глобальную переменную, counterно это незаконно для этого вопроса.
Валентин Шергин
Привет, Арун, не могли бы вы объяснить на примере. Я не понимаю именно этого вашего первого пункта.
Andy897 05
3

Для не сбалансирован поиска дерева, она занимает O (N) .

Для сбалансированного дерева поиска требуется O (k + log n) в худшем случае, но только O (k) в амортизированном смысле.

Наличие и управление дополнительным целым числом для каждого узла: размер поддерева дает временную сложность O (log n) . Такое сбалансированное дерево поиска обычно называется RankTree.

В общем, решения есть (основанные не на дереве).

С уважением.

Слава
источник
1

Это хорошо работает: status: это массив, который определяет, найден ли элемент. k: k-й элемент, который нужно найти. count: отслеживает количество узлов, пройденных во время обхода дерева.

int kth(struct tree* node, int* status, int k, int count)
{
    if (!node) return count;
    count = kth(node->lft, status, k, count);  
    if( status[1] ) return status[0];
    if (count == k) { 
        status[0] = node->val;
        status[1] = 1;
        return status[0];
    }
    count = kth(node->rgt, status, k, count+1);
    if( status[1] ) return status[0];
    return count;
}
пранджал
источник
1

Хотя это определенно не оптимальное решение проблемы, это еще одно потенциальное решение, которое, как я думал, может показаться некоторым людям интересным:

/**
 * Treat the bst as a sorted list in descending order and find the element 
 * in position k.
 *
 * Time complexity BigO ( n^2 )
 *
 * 2n + sum( 1 * n/2 + 2 * n/4 + ... ( 2^n-1) * n/n ) = 
 * 2n + sigma a=1 to n ( (2^(a-1)) * n / 2^a ) = 2n + n(n-1)/4
 *
 * @param t The root of the binary search tree.
 * @param k The position of the element to find.
 * @return The value of the element at position k.
 */
public static int kElement2( Node t, int k ) {
    int treeSize = sizeOfTree( t );

    return kElement2( t, k, treeSize, 0 ).intValue();
}

/**
 * Find the value at position k in the bst by doing an in-order traversal 
 * of the tree and mapping the ascending order index to the descending order 
 * index.
 *
 *
 * @param t Root of the bst to search in.
 * @param k Index of the element being searched for.
 * @param treeSize Size of the entire bst.
 * @param count The number of node already visited.
 * @return Either the value of the kth node, or Double.POSITIVE_INFINITY if 
 *         not found in this sub-tree.
 */
private static Double kElement2( Node t, int k, int treeSize, int count ) {
    // Double.POSITIVE_INFINITY is a marker value indicating that the kth 
    // element wasn't found in this sub-tree.
    if ( t == null )
        return Double.POSITIVE_INFINITY;

    Double kea = kElement2( t.getLeftSon(), k, treeSize, count );

    if ( kea != Double.POSITIVE_INFINITY )
        return kea;

    // The index of the current node.
    count += 1 + sizeOfTree( t.getLeftSon() );

    // Given any index from the ascending in order traversal of the bst, 
    // treeSize + 1 - index gives the
    // corresponding index in the descending order list.
    if ( ( treeSize + 1 - count ) == k )
        return (double)t.getNumber();

    return kElement2( t.getRightSon(), k, treeSize, count );
}
Роберт С. Барнс
источник
1

подпись:

Node * find(Node* tree, int *n, int k);

позвонить как:

*n = 0;
kthNode = find(root, n, k);

определение:

Node * find ( Node * tree, int *n, int k)
{
   Node *temp = NULL;

   if (tree->left && *n<k)
      temp = find(tree->left, n, k);

   *n++;

   if(*n==k)
      temp = root;

   if (tree->right && *n<k)
      temp = find(tree->right, n, k);

   return temp;
}
цель
источник
1

Ну вот мои 2 цента ...

int numBSTnodes(const Node* pNode){
     if(pNode == NULL) return 0;
     return (numBSTnodes(pNode->left)+numBSTnodes(pNode->right)+1);
}


//This function will find Kth smallest element
Node* findKthSmallestBSTelement(Node* root, int k){
     Node* pTrav = root;
     while(k > 0){
         int numNodes = numBSTnodes(pTrav->left);
         if(numNodes >= k){
              pTrav = pTrav->left;
         }
         else{
              //subtract left tree nodes and root count from 'k'
              k -= (numBSTnodes(pTrav->left) + 1);
              if(k == 0) return pTrav;
              pTrav = pTrav->right;
        }

        return NULL;
 }
Маниш Шукла
источник
0

Это то, что я думал, и это работает. Он запустится через o (log n)

public static int FindkThSmallestElemet(Node root, int k)
    {
        int count = 0;
        Node current = root;

        while (current != null)
        {
            count++;
            current = current.left;
        }
        current = root;

        while (current != null)
        {
            if (count == k)
                return current.data;
            else
            {
                current = current.left;
                count--;
            }
        }

        return -1;


    } // end of function FindkThSmallestElemet
ученик
источник
3
я не думаю, что это решение сработает. Что, если K-й наименьший находится в правом поддереве узла дерева?
Анил Вишной
0

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

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

Картик Бабу
источник
1
это не оптимальное решение
bragboy
0

Решение для полного случая 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;
}
Гвиджай
источник
0

Ядро 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), передав его в корень дерева.

Даниэль
источник
0

Вот краткая версия на 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 (журнал N) , чтобы найти в наименьший узел, а затем вывода (к) , чтобы пройти к к-го узла, так что это O (к + войти п).

Erhhung
источник
как насчет версии java?
Хенли Чиу,
0

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

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

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

Shivendra
источник
0

Лучшего алгоритма я не нашел ... решил написать :) Поправьте меня, если это не так.

class KthLargestBST{
protected static int findKthSmallest(BSTNode root,int k){//user calls this function
    int [] result=findKthSmallest(root,k,0);//I call another function inside
    return result[1];
}
private static int[] findKthSmallest(BSTNode root,int k,int count){//returns result[]2 array containing count in rval[0] and desired element in rval[1] position.
    if(root==null){
        int[]  i=new int[2];
        i[0]=-1;
        i[1]=-1;
        return i;
    }else{
        int rval[]=new int[2];
        int temp[]=new int[2];
        rval=findKthSmallest(root.leftChild,k,count);
        if(rval[0]!=-1){
            count=rval[0];
        }
        count++;
        if(count==k){
            rval[1]=root.data;
        }
        temp=findKthSmallest(root.rightChild,k,(count));
        if(temp[0]!=-1){
            count=temp[0];
        }
        if(temp[1]!=-1){
            rval[1]=temp[1];
        }
        rval[0]=count;
        return rval;
    }
}
public static void main(String args[]){
    BinarySearchTree bst=new BinarySearchTree();
    bst.insert(6);
    bst.insert(8);
    bst.insert(7);
    bst.insert(4);
    bst.insert(3);
    bst.insert(4);
    bst.insert(1);
    bst.insert(12);
    bst.insert(18);
    bst.insert(15);
    bst.insert(16);
    bst.inOrderTraversal();
    System.out.println();
    System.out.println(findKthSmallest(bst.root,11));
}

}

Laxman
источник
0

Вот код Java,

max (Node root, int k) - найти k-й по величине

min (Node root, int k) - найти kth наименьший

static int count(Node root){
    if(root == null)
        return 0;
    else
        return count(root.left) + count(root.right) +1;
}
static int max(Node root, int k) {
    if(root == null)
        return -1;
    int right= count(root.right);

    if(k == right+1)
        return root.data;
    else if(right < k)
        return max(root.left, k-right-1);
    else return max(root.right, k);
}

static int min(Node root, int k) {
    if (root==null)
        return -1;

    int left= count(root.left);
    if(k == left+1)
        return root.data;
    else if (left < k)
        return min(root.right, k-left-1);
    else
        return min(root.left, k);
}
code_2_peep
источник
0

это тоже сработает. просто вызовите функцию с maxNode в дереве

def k_largest (self, node, k): if k <0: return None
if k == 0: return node else: k - = 1 return self.k_largest (self.predecessor (node), k)

user2229805
источник
0

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

Нам просто нужно использовать обход по порядку, чтобы подсчитать наименьший узел слева направо, прекратить поиск, когда счетчик станет равным 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);
}
цзиньшуй
источник
0

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

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 );
}}
ПрашантКумарНирмал
источник
0

Использование вспомогательного класса Result для отслеживания того, найден ли узел и есть ли текущий k.

public class KthSmallestElementWithAux {

public int kthsmallest(TreeNode a, int k) {
    TreeNode ans = kthsmallestRec(a, k).node;
    if (ans != null) {
        return ans.val;
    } else {
        return -1;
    }
}

private Result kthsmallestRec(TreeNode a, int k) {
    //Leaf node, do nothing and return
    if (a == null) {
        return new Result(k, null);
    }

    //Search left first
    Result leftSearch = kthsmallestRec(a.left, k);

    //We are done, no need to check right.
    if (leftSearch.node != null) {
        return leftSearch;
    }

    //Consider number of nodes found to the left
    k = leftSearch.k;

    //Check if current root is the solution before going right
    k--;
    if (k == 0) {
        return new Result(k - 1, a);
    }

    //Check right
    Result rightBalanced = kthsmallestRec(a.right, k);

    //Consider all nodes found to the right
    k = rightBalanced.k;

    if (rightBalanced.node != null) {
        return rightBalanced;
    }

    //No node found, recursion will continue at the higher level
    return new Result(k, null);

}

private class Result {
    private final int k;
    private final TreeNode node;

    Result(int max, TreeNode node) {
        this.k = max;
        this.node = node;
    }
}
}
Алексей Федулов
источник
0

Сложность времени решения Python: O (n) Сложность пространства: O (1)

Идея состоит в том, чтобы использовать Morris Inorder Traversal

class Solution(object):
def inorderTraversal(self, current , k ):
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                k -= 1
                if(k == 0):
                    return current.val
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R 
            k -= 1
            if(k == 0):
                return current.val
            current = current.right

    return 0

def kthSmallest(self, root, k):
    return self.inorderTraversal( root , k  )
Маниш Чаухан
источник
-1

Я написал аккуратную функцию для вычисления 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);  }}
Тарунджит Сингх
источник
Не предоставлено никаких показателей, объясняющих, почему это оптимально. И в больших, и в малых случаях
Woot4Moo
-1
int RecPrintKSmallest(Node_ptr head,int k){
  if(head!=NULL){
    k=RecPrintKSmallest(head->left,k);
    if(k>0){
      printf("%c ",head->Node_key.key);
      k--;
    }
    k=RecPrintKSmallest(head->right,k);
  }
  return k;
}
Эбрахим Саада
источник
2
Пожалуйста, всегда сопровождайте код некоторым уровнем описания того, что он делает и как помогает решить проблему.
Ren
-1
public TreeNode findKthElement(TreeNode root, int k){
    if((k==numberElement(root.left)+1)){
        return root;
    }
    else if(k>numberElement(root.left)+1){
        findKthElement(root.right,k-numberElement(root.left)-1);
    }
    else{
        findKthElement(root.left, k);
    }
}

public int numberElement(TreeNode node){
    if(node==null){
        return 0;
    }
    else{
        return numberElement(node.left) + numberElement(node.right) + 1;
    }
}
Амазонка я иду
источник
-1
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;

      }
  }

}

Райан
источник