用最佳方法找出二叉查找树中的 kth 最小元素

小开

对于二叉查找树，无序遍历将返回元素... 有序。

Just do an inorder traversal and stop after traversing k elements.

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

小开

最佳答案

下面是这个想法的大致轮廓:

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

我们可以扩展 BST，使其中的每个节点在其左侧子树中存储元素的数量(假设给定节点的左侧子树包含该节点)。有了这段信息，通过反复询问左侧子树中的元素数来遍历树就变得非常简单，从而决定是向左侧子树递归还是向右侧子树递归。

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

如果是 K = = num _ element (T 的左子树)，那么我们要寻找的答案是节点 T中的值。
If k > num_elements(left subtree of T), then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
如果是 K < num _ element (T 的左子树)，那么 kth 最小元素就在左侧子树中的某个位置，因此我们将问题简化为在左侧子树中找到 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 的空间和时间复杂性。

小开

Given just a plain binary search tree, about all you can do is start from the smallest, and traverse upward to find the right node.

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

小开

对于没有平衡搜索树，它采用 O (n)。

对于平衡搜索树，在最坏的情况下采用 O (k + log n)，而在 分期付款意义上仅采用 O(k)。

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

In general, there are solutions (based not on tree).

问候。

小开

这是我想的，它工作。它将运行在 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

小开

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

小开

Status: 是保存是否找到元素的数组。是要找到的第 kth 元素。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;
}

小开

Well here is my 2 cents...

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

小开

一个更简单的解决方案是进行无序遍历，并跟踪当前要打印的元素(不打印它)。当我们到达 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);
}

小开

可以使用迭代无序遍历: Http://en.wikipedia.org/wiki/tree_traversal#iterative_traversal 在从堆栈中弹出一个节点之后，使用简单的 kth 元素检查。

小开

尽管这肯定不是解决这个问题的最佳方案，但它是另一个潜在的解决方案，我认为有些人可能会对此感兴趣:

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

小开

我们可以简单地使用顺序遍历并将访问的元素推送到堆栈上。弹出 k 的次数，以得到答案。

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

小开

签名:

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

电话:

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

definition:

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

小开

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

小开

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。可以通过调用 RbNode.nth (RbNode node，int n)并传递树的根来获得 not h 元素。

小开

我写了一个简洁的函数来计算 kth 最小元素。我使用顺序遍历，当它到达第 kth 最小元素时停止。

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

小开

下面是 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);
}

找到的最小节点是 O (logn) ，然后 O (k)遍历到 k-th 节点，所以是 O (k + logn)。

小开

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

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

1. 在 O (n)时间上使用无序遍历 2. 在 k + logn 时间内使用增广树

小开

//add a java version without 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();
}
}
}

小开

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

小开

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

小开

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

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

}

小开

这是 Java 代码,

Max (Node root，int k) -查找 kth 最大值

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

小开

只要在树中调用 maxNode 就可以了

def k_largest(self, node , k): 如 k < 0: 返回无
if k == 0: return node 其他: K-= 1 return self.k_largest(self.predecessor(node), k)

小开

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

我们只需要使用顺序遍历从左到右计数最小节点，一旦计数等于 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);
}

小开

带计数器的递归顺序步行

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 解决方案的不同之处) :

在三位置需要进行 if( counter == k )测试: (a)在左子树之后，(b)在根之后，(c)在右子树之后。这就是 确保在所有位置都检测到 kth 元素，也就是说，不管它所在的子树是什么。
确保 只打印 result 元素所需的 if( result == -1 )测试，否则从 kth 最小到根的所有元素都会被打印出来。

小开

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;


}
}

}

小开

一个更简单的解决方案是进行无序遍历，并跟踪当前要用计数器 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;
}

小开

Best approach is already there.But I'd like to add a simple Code for that

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

小开

使用辅助 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;
}
}
}

小开

 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 次最小的元素就停止递归。

小开

Python Solution 时间复杂度: 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  )

小开

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


}

小开

以下是步骤:

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

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

进行无序遍历，直到 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. 同样，我们也可以得到 KthLarest 函数。