MHB Finding the $j^{th}$ Smallest Element in an AVL Tree

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Element Tree
AI Thread Summary
The discussion revolves around finding the j-th smallest element in an AVL tree, utilizing the stored count of nodes in the left subtree of each node. The proposed algorithm operates in O(log m) time, where m is the total number of nodes in the tree. The process involves comparing the number of nodes in the left subtree with j-1 to determine the position of the desired element. If the left subtree has fewer nodes than j-1, the search continues in the right subtree, adjusting the index accordingly. A C++ implementation is provided, illustrating how to navigate the tree recursively to find the j-th smallest element. The reasoning behind adjusting the index to k-n-1 when searching the right subtree is clarified, emphasizing that this reflects the number of elements smaller than the target in the left subtree. The discussion concludes with an affirmation of understanding the algorithm's logic.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

We consider an $\text{ AVL }$ tree $T$. At each node $v$ of the tree the number of nodes of the left subtree of $v$ is stored.
I want to write an algorithm that returns the $j^{th}$ smallest element of the tree in time $O(\log m)$ where $m$ is the number of nodes of the tree.

How could we do this? Could you give me a hint? (Thinking)
 
Technology news on Phys.org
An $\text{ AVL } tree$ is a sorted binary tree. So the smallest element will be at the last level of the left subtree of the root, right? (Thinking)
 
We know that at each node $v$ of the tree, the number of nodes of the left subtree of $v$ is stored.
Does this mean that the number of nodes of the left subtree is the key or are there two fields? (Thinking)
 
I think that we could do it like that:

We check if the number of nodes of the left subtree of the root is smaller that $j-1$ and if this holds we know that the $j^{th}$ smallest element is at the left subtree of the root.
If the number of nodes of the left subtree of the root is equal to $j-1$, then we know that the root is the $j^{th}$ smallest element.
Otherwise, we know that we can find the desired element at the right subtree of the root.So if the root is not the $j^{th}$ smallest element , we will look at the nodes of the left/right subtree, till we find a node,of which the left subtree has $j-1$ elements.Am I right? (Thinking)
 
You haven't precisely specified an algorithm. Here's an implementation in C++:

Code:
class Node {
public:
  int key;
  int leftCount;
  Node* left;
  Node* right;
  Node();
};

Node* findKthSmallest(Node* p, int k) {
  int n = p->leftCount;
  if (n == k - 1) {
    return (p);
  }
  if (k <= n) {
    return (findKthSmallest(p->left, k));
  }
  return (findKthSmallest(p->right, k - n - 1));
}
 
johng said:
You haven't precisely specified an algorithm. Here's an implementation in C++:

Code:
class Node {
public:
  int key;
  int leftCount;
  Node* left;
  Node* right;
  Node();
};

Node* findKthSmallest(Node* p, int k) {
  int n = p->leftCount;
  if (n == k - 1) {
    return (p);
  }
  if (k <= n) {
    return (findKthSmallest(p->left, k));
  }
  return (findKthSmallest(p->right, k - n - 1));
}

Could you maybe explain me why at this command: [m] return (findKthSmallest(p->right, k - n - 1)); [/m] the second argument is $k-n-1$?
Why are we looking for the $(k-n-1)^{th}$ smallest element of the right subtree? (Thinking)
 
Think of the keys in the tree as being 1,2, etc. Of course, this need not be the case but it's easier to think this way. As you originally pointed out, the kth smallest element in a list is characterized by there being k-1 elements in the list that are smaller. Now if the function gets to
return(findKthSmallest(p->right,k-n-1), it is true that there are n elements in the left subtree smaller than k;also k is not n+1. So in the right subtree, there are then k-n-1 elements smaller than k. That is in the right subtree we want the (k-n-1)th smallest element.
Maybe it would help if you traced the function for the following AVL tree (the 1st value in each node is the key: the 2nd value is leftCount):

641dop.png
 
Last edited:
johng said:
Think of the keys in the tree as being 1,2, etc. Of course, this need not be the case but it's easier to think this way. As you originally pointed out, the kth smallest element in a list is characterized by there being k-1 elements in the list that are smaller. Now if the function gets to
return(findKthSmallest(p->right,k-n-1), it is true that there are n elements in the left subtree smaller than k;also k is not n+1. So in the right subtree, there are then k-n-1 elements smaller than k. That is in the right subtree we want the (k-n-1)th smallest element.
Maybe it would help if you traced the function for the following AVL tree (the 1st value in each node is the key: the 2nd value is leftCount):

Great! (Happy) Thanks a lot!
 
Back
Top