基于二叉搜索树优化vector查找并返回原索引的问题求助

Hey there! Let's break down how to fix your BST index issue and explore some better alternatives too.

The core idea here is straightforward: when building your binary search tree, you need to associate each element from the vector with its original index at the time of insertion. Your node structure is already on the right track—you just need to make sure you're populating the index field correctly and using the data field (not the index) to maintain the BST ordering.

Step 1: Fix the Node & Insertion Logic #

First, let's adjust your node struct to include a constructor for easier initialization, then write a proper insertion function that uses the element's value to determine placement:

struct Node {
    int data;
    int index;
    Node* left;
    Node* right;
    
    // Constructor to initialize data and index together
    Node(int val, int idx) : data(val), index(idx), left(nullptr), right(nullptr) {}
};

// Insert a value-index pair into the BST, ordered by data value
Node* insert(Node* root, int data, int index) {
    if (root == nullptr) {
        return new Node(data, index);
    }
    // Use data to decide left/right placement (not index!)
    if (data < root->data) {
        root->left = insert(root->left, data, index);
    } else {
        root->right = insert(root->right, data, index);
    }
    return root;
}

Step 2: Build the Tree from Your Vector #

When traversing your original vector, pass both the element value and its current index to the insertion function:

#include <vector>
using namespace std;

int main() {
    vector<int> numbers = {5,4,3,2,1};
    Node* root = nullptr;
    
    for (int i = 0; i < numbers.size(); ++i) {
        root = insert(root, numbers[i], i);
    }
    
    // Now search for 4
    int targetIndex = search(root, 4); // Should return 1
    return 0;
}

Step 3: Implement the Search Function #

Your search function should look for the target data value, then return the associated index once found:

int search(Node* root, int target) {
    if (root == nullptr) {
        return -1; // Return -1 if target isn't found
    }
    if (target == root->data) {
        return root->index;
    } else if (target < root->data) {
        return search(root->left, target);
    } else {
        return search(root->right, target);
    }
}

Common Mistakes to Avoid #

• Using the index to order the BST: If you accidentally compare index values instead of data during insertion, your tree will be sorted by index—not the element values—so searching for 4 won't find the right node.
• Incorrect index assignment: Double-check that you're passing the loop variable i (the original index) to the Node constructor, not the element value.
• Ignoring duplicate values: If your vector has duplicate elements, a standard BST will overwrite the first index with the last one. To fix this, modify your node to store a vector<int> of indexes instead of a single int.

While a BST works, it has a big downside: if your vector is sorted in reverse (like your example), the BST will degenerate into a linked list, making lookups O(n) instead of O(log n). For more reliable performance, consider these options:

1. Hash Maps (std::unordered_map) #

Hash maps give average O(1) lookup time, which is faster than even a balanced BST. You can map each element value to its original index (or indexes, for duplicates):

#include <unordered_map>
#include <vector>

int main() {
    vector<int> numbers = {5,4,3,2,1};
    unordered_map<int, vector<int>> valueToIndices;
    
    // Populate the map
    for (int i = 0; i < numbers.size(); ++i) {
        valueToIndices[numbers[i]].push_back(i);
    }
    
    // Search for 4
    auto it = valueToIndices.find(4);
    if (it != valueToIndices.end()) {
        int firstIndex = it->second[0]; // Returns 1
        // If you need all indexes for duplicates, iterate through it->second
    }
    return 0;
}

2. Balanced BST (std::map) #

If you need ordered lookups (e.g., finding the smallest element greater than your target), std::map uses a red-black tree (a balanced BST) to guarantee O(log n) lookups:

#include <map>
#include <vector>

int main() {
    vector<int> numbers = {5,4,3,2,1};
    map<int, vector<int>> valueToIndices;
    
    for (int i = 0; i < numbers.size(); ++i) {
        valueToIndices[numbers[i]].push_back(i);
    }
    
    auto it = valueToIndices.find(4);
    if (it != valueToIndices.end()) {
        int firstIndex = it->second[0]; // Returns 1
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者V.Cunichin