以最佳方式在二叉查找树中查找第k个最小元素

我需要在二叉search树中find第k个最小的元素，而不使用任何静态/全局variables。 如何有效地实现它？ 我脑海中的解决scheme是在O（n）中进行操作，这是最坏的情况，因为我打算对整棵树进行遍历遍历。 但内心深处，我觉得我不在这里使用BST财产。 我的假设解决scheme是否正确或有更好的解决scheme吗？

Answer 1

这只是一个概念的概述：

在BST中，节点T的左子树只包含比存储在T的值小的元素。 如果k小于左子树中元素的个数，则第k个最小元素必须属于左子树。 否则，如果k较大，则第k个最小的元素在右子树中。

我们可以扩充BST以使其中的每个节点存储其左子树中的元素的数量（假定给定节点的左子树包括该节点）。 用这条信息，通过反复询问左子树中元素的数量来遍历树是很简单的，以决定是进行recursion到左子树还是右子树。

现在，假设我们在节点T：

1. 如果k == num_elements（T的左子树） ，那么我们正在寻找的答案是节点T的值。
2. 如果k> num_elements（T的左子树） ，那么显然我们可以忽略左子树，因为那些元素也会小于第k个最小。 因此，我们将这个问题简化为findk - num_elements(left subtree of T)最小元素k - num_elements(left subtree of T) 。
3. 如果k <num_elements（T的左子树） ，那么第k个最小的是左子树中的某个地方，所以我们减less了寻找左子树中第k个最小元素的问题。

复杂性分析：

这需要O(depth of node)时间，在平衡BST上最坏的情况下是O(log n) ，或者是随机BST的平均值O(log n) 。

BST需要O(n)存储，并且需要另一个O(n)来存储关于元素数量的信息。 所有的BST操作都需要O(depth of node)时间，并且需要花费O(depth of node)额外的时间来维护用于插入，删除或旋转节点的“元素数”信息。 因此，在左子树中存储有关元素数量的信息保持了BST的空间和时间复杂度。

Answer 2

一个更简单的解决scheme是做一个inorder遍历并跟踪当前要打印的元素（不打印它）。 当我们到达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); } 

Answer 3

 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＃中的实现基于上面的algorithm只是想我会发布它，让人们可以更好地理解它适用于我

谢谢你IVlad

Answer 4

/ /添加一个Java版本没有recursion

 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(); } } } 

Answer 5

一个更简单的解决scheme是做一个inorder遍历并跟踪当前要用计数器k打印的元素。 当我们到达k，打印元素。 运行时间是O（n）。 请记住，函数返回types不能为空，它必须在每次recursion调用之后返回其更新的k值。 一个更好的解决scheme是在每个节点上sorting位置值的增强型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; } 

Answer 6

你可以使用迭代遍历： http : //en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal在从堆栈中popup一个节点之后，简单检查第k个元素。

Answer 7

给定一个普通的二叉search树，你所能做的就是从最小的开始，向上遍历find正确的节点。

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

Answer 8

recursion顺序与计数器一起走

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

这个想法与@prasadvk解决scheme类似，但它有一些缺点（请参阅下面的注释），所以我将其作为单独的答案发布。

 // 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解决scheme的区别）：

1. if( counter == k )testing需要在三个地方：（a）在左子树之后，（b）在根之后，和（c）在右子树之后。 这是为了确保第k个元素被检测到的所有位置 ，即不pipe它所在的子树。

2. if( result == -1 )testing需要确保只打印结果元素 ，否则将打印从第k个最小直到根的所有元素。

Answer 9

对于不平衡的search树，它需要O（n） 。

对于平衡search树，在最坏情况下需要O（k + log n） ，而在摊销意义上只需要O（k） 。

具有和pipe理每个节点的额外整数：子树的大小给出O（log n）时间复杂度。 这种平衡search树通常被称为RankTree。

一般来说，有解决scheme（不是基于树）。

问候。

Answer 10

这效果很好：status：是保存元素是否被find的数组。 k：是要find的第k个元素。 count：logging树遍历期间遍历的节点数。

 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; } 

Answer 11

虽然这绝对不是解决这个问题的最佳解决scheme，但这也是我认为有些人可能会感兴趣的另一个潜在的解决scheme：

 /** * 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 ); } 

Answer 12

签名：

 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; } 

Answer 13

那么这里是我的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; } 

Answer 14

这是我虽然和它的作品。 它将运行在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 

Answer 15

那么我们可以简单地使用遍历，并将访问元素推到堆栈上。 popupk次，得到答案。

我们也可以在k元素之后停下来

Answer 16

完整的BST案例解决scheme： –

 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 17

Linux内核有一个很好的增强型红黑树数据结构，它支持在linux / lib / rbtree.c的O（log n）中的基于sorting的操作。

一个非常粗糙的Java端口也可以在http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.javafind，连同RbRoot.java和RbNode.java。; 第n个元素可以通过调用RbNode.nth（RbNode节点，int n）传入树的根来获得。

Answer 18

下面是C＃中的简洁版本，它返回第k个最小的元素，但要求将k作为参数传入（与@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); } 

find最小的节点是O（log n），然后O（k）遍历到第k个节点，所以它是O（k + log n）。

Answer 19

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

这是这个问题的确切答案：

1.在O（n）时间使用中序遍历2.在k + log n时间使用增广树

Answer 20

我找不到更好的algorithm..所以决定写一个:)纠正我，如果这是错误的。

 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)); } 

}

Answer 21

这里是java代码，

max（节点根，int k） – find第k个最大值

min（节点根，int k） – find第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); } 

Answer 22

这也会起作用。 只需在树中调用maxNode函数

def k_largest（self，node，k）：如果k <0：return None
如果k == 0：return node else：k – = 1 return self.k_largest（self.predecessor（node），k）

Answer 23

我认为这比接受的答案好，因为它不需要修改原始树节点来存储其子节点的数量。

我们只需要使用按顺序遍历来从左到右计算最小的节点，一旦计数等于K就停止search。

 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 24

使用order statistics tree IVlad解决scheme是最有效的。 但是，如果你不能使用order statistics tree并且被一个普通的老BST卡住，那么最好的方法就是进行一个订单遍历（就像prasadvk指出的那样）。 但是如果你想返回第k个最小的元素，而不是简单地打印出这个值，他的解决scheme是不够的。 而且，由于他的解决scheme是recursion的，所以存在堆栈溢出的危险。 因此，我写了一个java解决scheme，返回第k个最小的节点，并使用堆栈进行In Order Traversal。 运行时间是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 25

最好的方法已经存在了，但我想为此添加一个简单的代码

 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 26

使用辅助Result类来跟踪节点是否被find和当前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; } } } 

Answer 27

我写了一个简洁的函数来计算第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 28

 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; } 

Answer 29

 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; } } 

Answer 30

 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; } } 

}