115

我需要在不使用任何静态/全局变量的情况下找到二叉搜索树中的第 k 个最小元素。如何有效地实现它?我想到的解决方案是在 O(n) 中进行操作,这是最坏的情况,因为我打算对整个树进行中序遍历。但在内心深处,我觉得我没有在这里使用 BST 属性。我的假设解决方案是正确的还是有更好的解决方案?

4

34 回答 34

173

这里只是这个想法的概要:

在 BST 中,节点的左子树T仅包含小于存储在 中的值的元素T。如果k小于左子树中的元素个数,则第一个k最小的元素必须属于左子树。否则,如果k更大,则第kth 小元素在右子树中。

我们可以扩充 BST,使其中的每个节点都存储其左子树中的元素数量(假设给定节点的左子树包括该节点)。有了这条信息,就很容易遍历树,通过反复询问左子树中元素的数量,来决定是递归到左子树还是右子树。

现在,假设我们在节点 T:

  1. 如果k == num_elements(left subtree of T),那么我们正在寻找的答案就是 node 中的值T
  2. 如果k > num_elements(left subtree of T),那么显然我们可以忽略左子树,因为这些元素也将小于kth 最小的。因此,我们将问题简化为找到k - num_elements(left subtree of T)右子树的最小元素。
  3. 如果k < num_elements(left subtree of T),则第 th 最小的元素在左子树k中的某个位置,因此我们将问题简化为在左子树中查找第kth 最小元素。

复杂性分析:

这需要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 的空间和时间复杂度。

于 2010-02-24T20:27:35.617 回答
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); 
}
于 2010-12-01T04:14:43.877 回答
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;
    }

this is my implementation in C# based on the algorithm above just thought I'd post it so people can understand better it works for me

thank you IVlad

于 2010-06-09T22:01:37.503 回答
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();
        }
    }
}
于 2012-12-29T04:09:49.580 回答
10

一个更简单的解决方案是进行中序遍历并使用计数器 k 跟踪当前要打印的元素。当我们到达 k 时,打印元素。运行时间为 O(n)。请记住函数返回类型不能为 void,它必须在每次递归调用后返回其更新后的 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;
}
于 2015-10-13T20:43:58.403 回答
7

您可以使用迭代中序遍历: http ://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal 在将节点弹出堆栈后简单检查第 k 个元素。

于 2011-01-16T22:24:13.797 回答
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 )需要在三个地方进行测试:(a)在左子树之后,(b)在根之后,以及(c)在右子树之后。这是为了确保为所有位置检测到第 k 个元素,即不管它位于哪个子树。

  2. if( result == -1 )需要进行测试以确保仅打印结果元素,否则打印从第 k 个最小元素到根的所有元素。

于 2014-04-14T19:53:44.187 回答
4

只给一个普通的二叉搜索树,你所能做的就是从最小的开始,然后向上遍历找到正确的节点。

如果您要经常这样做,您可以为每个节点添加一个属性,表示其左子树中有多少个节点。使用它,您可以将树直接下降到正确的节点。

于 2010-02-24T20:27:55.540 回答
3

对于不平衡的搜索树,它需要O(n)

对于平衡搜索树,在最坏的情况下需要O(k + log n) ,但在摊销意义上只需要O(k) 。

拥有和管理每个节点的额外整数:子树的大小给出O(log n)时间复杂度。这种平衡的搜索树通常称为RankTree。

一般来说,有解决方案(不是基于树)。

问候。

于 2010-02-25T09:19:28.433 回答
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 );
}
于 2011-01-27T19:57:04.133 回答
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;
}
于 2010-09-02T05:55:17.140 回答
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;
}
于 2011-04-03T06:36:43.290 回答
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;
 }
于 2010-09-08T12:51:03.520 回答
0

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

这是这个问题的确切答案:-

1.在 O(n) 时间使用中序遍历 2.在 k+log n 时间使用增强树

于 2012-11-07T12:55:58.907 回答
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)

于 2013-03-31T17:52:58.917 回答
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;
}
于 2011-12-09T06:55:47.957 回答
0

Linux 内核具有出色的增强型红黑树数据结构,支持 linux/lib/rbtree.c 中 O(log n) 中的基于秩的操作。

还可以在http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java找到一个非常粗略的 Java 端口,连同 RbRoot.java 和 RbNode.java。第 n 个元素可以通过调用 RbNode.nth(RbNode node, int n) 获得,传入树的根。

于 2012-04-30T22:21:18.583 回答
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
于 2010-05-13T06:58:39.433 回答
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);
}
于 2013-09-01T12:02:23.857 回答
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));
}

}

于 2013-03-14T05:10:18.627 回答
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(log n) 然后遍历到第k个节点是O(k),所以是O(k + log n)。

于 2012-06-26T04:05:24.740 回答
0

好吧,我们可以简单地使用顺序遍历并将访问的元素压入堆栈。弹出 k 次,得到答案。

我们也可以在 k 个元素之后停止

于 2011-02-12T07:34:44.787 回答
0

这是java代码,

max(Node root, int k) - 找到第 k 个最大的

min(Node root, int k) - 找到第 k 个最小的

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);
}
于 2013-03-19T23:27:33.070 回答
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;
    }
}
}
于 2016-12-23T15:53:56.907 回答
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 );
}}
于 2016-06-10T00:19:19.640 回答
0

Python 解决方案时间复杂度:O(n) 空间复杂度:O(1)

想法是使用莫里斯中序遍历

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  )
于 2020-04-06T16:17:57.333 回答
0

以下是步骤:

1.向每个节点添加一个字段,指示其根的树的大小。这支持O(logN)平均时间的操作。

2.为了节省空间,一个字段表示它根节点的大小就足够了。我们不需要同时保存左子树和右子树的大小。

3.进行中序遍历,直到LeftTree == K, LeftTree = Size(T->Left) + 1

4.示例代码如下:

int Size(SearchTree T)
{
    if(T == NULL) return 0;
    return T->Size;
}
Position KthSmallest(SearchTree T, int K)
{
    if(T == NULL) return NULL;

    int LeftTree;
    LeftTree = Size(T->Left) + 1;

    if(LeftTree == K) return T;

    if(LeftTree > K){ 
        T = KthSmallest(T->Left, K); 
    }else if(LeftTree < K){ 
        T = KthSmallest(T->Right, K - LeftTree);
    }   

    return T;
}

5.同理,我们也可以得到KthLargest函数。

于 2021-08-02T08:29:14.590 回答
0
public int kthSmallest(TreeNode root, int k) {
     
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();

    while (true) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      k = k - 1;
      if (k == 0) return root.val;
      root = root.right;
    }

}     
于 2021-05-15T18:13:11.203 回答
-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;

      }
  }

}

于 2015-01-10T19:00:32.893 回答
-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);  }}
于 2012-05-25T11:23:49.567 回答
-1
 public int printInorder(Node node, int k) 
    { 
        if (node == null || k <= 0) //Stop traversing once you found the k-th smallest element
            return k; 

        /* first recur on left child */
        k = printInorder(node.left, k); 

        k--;
        if(k == 0) {  
            System.out.print(node.key);
        }

        /* now recur on right child */
        return printInorder(node.right, k);
    } 

这个java递归算法,一旦找到第k个最小元素就停止递归。

于 2018-11-29T12:22:18.207 回答
-2
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;
}
于 2013-01-18T13:57:02.517 回答
-2
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;
    }
}
于 2013-02-22T20:29:04.093 回答
-5

对于二叉搜索树,中序遍历将按顺序返回元素...。

只需进行中序遍历并在遍历 k 个元素后停止。

对于 k 的常数值,O(1)。

于 2010-02-24T20:21:27.017 回答