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

发布于 2024-08-22 15:01:10 字数 147 浏览 4 评论 0原文

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

I need to find the kth smallest element in the binary search tree without using any static/global variable. How to achieve it efficiently?
The solution that I have in my mind is doing the operation in O(n), the worst case since I am planning to do an inorder traversal of the entire tree. But deep down I feel that I am not using the BST property here. Is my assumptive solution correct or is there a better one available ?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(30

找个人就嫁了吧 2024-08-29 15:01:13

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

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

}

I couldn't find a better algorithm..so decided to write one :)
Correct me if this is wrong.

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

}

梅倚清风 2024-08-29 15:01:13

这是java代码,

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

Here is the java code,

max(Node root, int k) - to find kth largest

min(Node root, int k) - to find kth Smallest

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);
}
盛夏已如深秋| 2024-08-29 15:01:13

这也行。只需在树中调用带有 maxNode 的函数

def k_largest(self, node , k):
如果 k < 0:
返回无
如果 k == 0:
返回节点
别的:
k-=1
返回 self.k_largest(self.predecessor(node), k)

this would work too. just call the function with maxNode in the tree

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)

呆橘 2024-08-29 15:01:13

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

我们只需要使用中序遍历从左到右统计最小的节点,当计数等于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);
}

I think this is better than the accepted answer because it doesn't need to modify the original tree node to store the number of it's children nodes.

We just need to use the in-order traversal to count the smallest node from the left to right, stop searching once the count equals to 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);
}
尘世孤行 2024-08-29 15:01:13

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

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

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 );
}}
几度春秋 2024-08-29 15:01:13

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

Using auxiliary Result class to track if node is found and current 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;
    }
}
}
妄断弥空 2024-08-29 15:01:13

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

想法是使用 Morris 中序遍历

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  )

Python Solution
Time Complexity : O(n)
Space Complexity : O(1)

Idea is to use 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  )
聆听风音 2024-08-29 15:01:13
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;
    }

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

}     
拿命拼未来 2024-08-29 15:01:13

步骤如下:

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函数。

Here are the steps:

1.Add a field to each node indicating the size of the tree it roots. This supports operation in O(logN) average time.

2.To save space, one field indicating the size of a node it roots is enough. We don't need to save both the left subtree and right subtree size.

3.Do an inorder traversal until LeftTree == K, LeftTree = Size(T->Left) + 1.

4.Here is the sample code:

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.Similarly, we can also get the KthLargest function.

爱你是孤单的心事 2024-08-29 15:01:13

这个问题是LeetCode 230:BST中的第K个最小元素
根据BST性质,第k个最小的节点就是中序遍历时访问到的第k个节点。因此,我们进行递归中序遍历,并记录迄今为止访问过的节点的数量。

时间复杂度:最坏的情况,我们最终可能会访问所有节点,O(n)。但如果找到第 k 个节点,我们就会提前退出。

空间复杂度:O(1)(不考虑递归栈)。

Python 实现。

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    def dfs(node: TreeNode, count: int) -> tuple[int, int]:
        """
        :param node: Current node
        :param count: Number of nodes visited so far
        :returns: a 2-tuple consisting of the number of nodes visited, and the value of the last visited node.
            If the kth node is found, immediately returns the value of the kth node
        """
        if node.left is not None:
            # count is the number of nodes in the left subtree.
            count, val = dfs(node.left, count)
            if count == k:
                return k, val
        # count the current node.
        count += 1
        if count == k or node.right is None:
            return count, node.val
        return dfs(node.right, count)

    assert root is not None
    return dfs(root, 0)[1]

This question is LeetCode 230: Kth Smallest Element in a BST.
By BST property, the kth smallest node is the kth node visited during the inorder traversal. Thus, we do a recursive inorder traversal, and keep count of the nodes visited thus far.

Time Complexity: Worst case, we may end up visiting all nodes, O(n). But we exit early if the k-th node is found.

Space Complexity: O(1) (not considering recursion stack).

Python implementation.

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    def dfs(node: TreeNode, count: int) -> tuple[int, int]:
        """
        :param node: Current node
        :param count: Number of nodes visited so far
        :returns: a 2-tuple consisting of the number of nodes visited, and the value of the last visited node.
            If the kth node is found, immediately returns the value of the kth node
        """
        if node.left is not None:
            # count is the number of nodes in the left subtree.
            count, val = dfs(node.left, count)
            if count == k:
                return k, val
        # count the current node.
        count += 1
        if count == k or node.right is None:
            return count, node.val
        return dfs(node.right, count)

    assert root is not None
    return dfs(root, 0)[1]
雨后咖啡店 2024-08-29 15:01:13

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

i wrote a neat function to calculate the kth smallest element. I uses in-order traversal and stops when the it reaches the kth smallest element.

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);  }}
遥远的绿洲 2024-08-29 15:01:12

好吧,这是我的 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;
 }

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;
 }
牵你手 2024-08-29 15:01:12

这就是我的想法并且有效。它将运行在 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

This is what I though and it works. It will run in 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
情绪操控生活 2024-08-29 15:01:12

那么我们可以简单地使用中序遍历并将访问过的元素压入堆栈。
pop k 次,得到答案。

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

Well we can simply use the in order traversal and push the visited element onto a stack.
pop k number of times, to get the answer.

we can also stop after k elements

信仰 2024-08-29 15:01:12

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

Solution for complete BST case :-

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;
}
稀香 2024-08-29 15:01:12

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 ,以及 RbRoot.java 和 RbNode.java。第 n 个元素可以通过调用 RbNode.nth(RbNode node, int n) 来获取,传入树的根。

The Linux Kernel has an excellent augmented red-black tree data structure that supports rank-based operations in O(log n) in linux/lib/rbtree.c.

A very crude Java port can also be found at http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java, together with RbRoot.java and RbNode.java. The n'th element can be obtained by calling RbNode.nth(RbNode node, int n), passing in the root of the tree.

北风几吹夏 2024-08-29 15:01:12

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

这是 (log n) 找到最小的节点,然后 O(k) 遍历到第 k 个节点,所以它是 O(k + log n)。

Here's a concise version in C# that returns the k-th smallest element, but requires passing k in as a ref argument (it's the same approach as @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);
}

It's O(log n) to find the smallest node, and then O(k) to traverse to k-th node, so it's O(k + log n).

翻了热茶 2024-08-29 15:01:12

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

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

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

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

this is the exact answer to this question:-

1.using inorder traversal on O(n) time
2.using Augmented tree in k+log n time

玩心态 2024-08-29 15:01:11
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

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

A君 2024-08-29 15:01:11

//添加一个不带递归的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();
        }
    }
}

//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();
        }
    }
}
冰葑 2024-08-29 15:01:11

一个更简单的解决方案是进行中序遍历并使用计数器 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;
}

A simpler solution would be to do an inorder traversal and keep track of the element currently to be printed with a counter k. When we reach k, print the element. The runtime is O(n). Remember the function return type can not be void, it has to return its updated value of k after each recursive call. A better solution to this would be an augmented BST with a sorted position value at each node.

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;
}
深爱不及久伴 2024-08-29 15:01:11

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

You can use iterative inorder traversal:
http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal
with a simple check for kth element after poping a node out of the stack.

掩耳倾听 2024-08-29 15:01:11

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

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

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.

If you're going to do this very often, you can add an attribute to each node signifying how many nodes are in its left sub-tree. Using that, you can descend the tree directly to the correct node.

守望孤独 2024-08-29 15:01:11

带计数器的递归有序遍历

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 个最小的元素开始一直到根的所有元素打印。

Recursive In-order Walk with a counter

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

The idea is similar to @prasadvk solution, but it has some shortcomings (see notes below), so I am posting this as a separate answer.

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

Notes (and differences from @prasadvk's solution):

  1. if( counter == k ) test is required at three places: (a) after left-subtree, (b) after root, and (c) after right subtree. This is to ensure that kth element is detected for all locations, i.e. irrespective of the subtree it is located.

  2. if( result == -1 ) test required to ensure only the result element is printed, otherwise all the elements starting from the kth smallest up to the root are printed.

风柔一江水 2024-08-29 15:01:11

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

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

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

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

问候。

For not balanced searching tree, it takes O(n).

For balanced searching tree, it takes O(k + log n) in the worst case but just O(k) in Amortized sense.

Having and managing the extra integer for every node: the size of the sub-tree gives O(log n) time complexity.
Such balanced searching tree is usually called RankTree.

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

Regards.

凹づ凸ル 2024-08-29 15:01:11

这很有效: 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;
}

This works well: status : is the array which holds whether element is found. k : is kth element to be found. count : keeps track of number of nodes traversed during the tree traversal.

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;
}
最近可好 2024-08-29 15:01:11

虽然这绝对不是问题的最佳解决方案,但它是另一个潜在的解决方案,我认为有些人可能会觉得有趣:

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

While this is definitely not the optimal solution to the problem, it is another potential solution which I thought some people might find interesting:

/**
 * 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 );
}
提笔落墨 2024-08-29 15:01:11

签名:

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

signature:

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

call as:

*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;
}
甜中书 2024-08-29 15:01:10

下面只是这个想法的概述:

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

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

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

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

复杂度分析:

这需要O(节点深度)时间,在平衡BST的最坏情况下为O(log n),或者O(log n) 随机 BST 的平均值。

BST 需要 O(n) 存储,并且需要另一个 O(n) 来存储有关元素数量的信息。所有BST操作都需要O(节点深度)时间,并且需要O(节点深度)额外时间来维护插入、删除的“元素数量”信息或节点的旋转。因此,存储有关左子树中元素数量的信息可以保持 BST 的空间和时间复杂度。

Here's just an outline of the idea:

In a BST, the left subtree of node T contains only elements smaller than the value stored in T. If k is smaller than the number of elements in the left subtree, the kth smallest element must belong to the left subtree. Otherwise, if k is larger, then the kth smallest element is in the right subtree.

We can augment the BST to have each node in it store the number of elements in its left subtree (assume that the left subtree of a given node includes that node). With this piece of information, it is simple to traverse the tree by repeatedly asking for the number of elements in the left subtree, to decide whether to do recurse into the left or right subtree.

Now, suppose we are at node T:

  1. If k == num_elements(left subtree of T), then the answer we're looking for is the value in node T.
  2. 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.
  3. If k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.

Complexity analysis:

This takes O(depth of node) time, which is O(log n) in the worst case on a balanced BST, or O(log n) on average for a random BST.

A BST requires O(n) storage, and it takes another O(n) to store the information about the number of elements. All BST operations take O(depth of node) time, and it takes O(depth of node) extra time to maintain the "number of elements" information for insertion, deletion or rotation of nodes. Therefore, storing information about the number of elements in the left subtree keeps the space and time complexity of a BST.

你穿错了嫁妆 2024-08-29 15:01:10

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

A simpler solution would be to do an inorder traversal and keep track of the element currently to be printed (without printing it). When we reach k, print the element and skip rest of tree traversal.

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); 
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文