Find Nearest Record in Binary Search Tree | C++ Implementation

In summary, The conversation discusses finding a record with a given key in a binary search tree and returning the two nearest records in the tree if the key is not found. The return values and implementation of n1 and n2 in the code are also mentioned.
  • #1
skyhyyzlz
Hi everyone, i have a binary search tree proble, please help me..


* Find record with key x in the tree. If not found, return the two nearest records in the tree (in alphabetical order)
* Return values:
* FOUND: Return the address of the node in the tree which contains key x, set n1 = n2 = NULL;
* NOT FOUND: Return NULL, n1, n2 are set to the nearest node to x in the tree, if exist.
* n1 is set to the address of the BSTNode whose key is just smaller than x in alphabetical order, if exists (Otherwise NULL).
* n2 is set to the address of the BSTNode whose key is just larger than x in alphabetical order, if exists (Otherwise NULL).
* NOTE:
* Always return the address of the existing "BSTNode"s. DO NOT allocate new spaces for returned strings.

How can I implement n1 and n2 in the following code for finding the nearest record when the key x is NOT FOUND?


const BSTNode * BST_findNearest( BSTNode * treeRoot, const string & x, BSTNode* &n1, BSTNode* &n2 )
{
if(treeRoot==NULL)
{
return NULL;
}
else if(x < treeRoot->name)
{
return BST_findNearest(treeRoot->left,x,n1,n2);
}
else if(x > treeRoot->name)
{
return BST_findNearest(treeRoot->right,x,n1,n2);
}
else
{
n1 = NULL;
n2 = NULL;
return treeRoot;
}

}
 
Technology news on Phys.org
  • #2
From your question, I think I'm taking same course with you, in same University.
Just simply set n1 or n2 before returning the next node.

const BSTNode* BST_findNearest( BSTNode* treeRoot, const string &x, BSTNode* &n1, BSTNode* &n2 )
{
if (treeRoot == NULL) return NULL;
if (x == treeRoot->name) {
n1 = n2 = NULL;
return treeRoot;
}
else if (x < treeRoot->name) {
n2 = treeRoot;
return BST_findNearest(treeRoot->left, x, n1, n2);
}
else if (x > treeRoot->name) {
n1 = treeRoot;
return BST_findNearest(treeRoot->right, x, n1, n2);
}
}
 
  • #3



I would suggest implementing n1 and n2 by using the properties of a binary search tree. Since the tree is already sorted in alphabetical order, we can use the fact that the left child of a node is always smaller and the right child is always larger.

To find n1, we can start at the root node and traverse the tree to the left until we reach a node whose key is smaller than x. This node will be the nearest node to x in alphabetical order. If we reach a leaf node without finding n1, then n1 does not exist in the tree.

To find n2, we can start at the root node and traverse the tree to the right until we reach a node whose key is larger than x. This node will be the nearest node to x in alphabetical order. If we reach a leaf node without finding n2, then n2 does not exist in the tree.

These steps can be implemented in the code by adding additional conditions to the existing code. For example, to find n1, we can add a condition in the else if statement for when x < treeRoot->name. This condition would check if treeRoot->left is NULL, and if it is, then we have found n1. Similarly, for finding n2, we can add a condition in the else if statement for when x > treeRoot->name, checking if treeRoot->right is NULL.

Additionally, we can also keep track of the previous node while traversing the tree, and if we reach a leaf node without finding n1 or n2, we can use the previous node as n1 or n2 respectively. This would cover the case when x is not present in the tree and n1 or n2 is the last node in the tree.

Overall, implementing n1 and n2 would involve using the existing code and adding additional conditions to handle the cases when x is not found in the tree.
 

1. How does a Binary Search Tree work?

A Binary Search Tree is a data structure where each node in the tree has at most two children, a left child and a right child. The nodes are organized in a specific way where the left child is always smaller than the parent node and the right child is always larger. This organization makes it efficient for searching for a specific value in the tree.

2. What is the time complexity of finding the nearest record in a Binary Search Tree?

The time complexity of finding the nearest record in a Binary Search Tree is O(log n), where n is the number of nodes in the tree. This is because the search algorithm can eliminate half of the remaining nodes in the tree at each step, making it highly efficient for large datasets.

3. Can a Binary Search Tree contain duplicate values?

Yes, a Binary Search Tree can contain duplicate values. However, the implementation of the search algorithm may differ. Some implementations may return the first occurrence of the value, while others may return all occurrences.

4. What happens if the nearest record does not exist in the Binary Search Tree?

If the nearest record does not exist in the Binary Search Tree, the search algorithm will return the next closest value. This may be the value that is just larger or just smaller than the given value, depending on the implementation.

5. How can a Binary Search Tree be efficiently implemented in C++?

A Binary Search Tree can be efficiently implemented in C++ using a pointer-based approach. This involves creating a Node class that contains a value and two pointers, one for the left child and one for the right child. The insert and search functions can then be implemented recursively, taking advantage of the structure of the tree.

Similar threads

  • Programming and Computer Science
Replies
3
Views
3K
  • Programming and Computer Science
Replies
3
Views
2K
  • Programming and Computer Science
Replies
13
Views
4K
  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
Replies
10
Views
3K
  • Programming and Computer Science
Replies
11
Views
3K
  • Programming and Computer Science
Replies
8
Views
1K
  • Programming and Computer Science
Replies
7
Views
75K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Programming and Computer Science
Replies
8
Views
2K
Back
Top