c++ - 替罪羊搜索功能

Question

我在替罪羊树中插入了 30000 个随机数。我有一个计数器来跟踪我的插入和搜索所做的比较。我试图搜索数字 3337，但没有找到，但跟踪器说需要将近 600 万次比较才能做出与 O(logn) 复杂度相去甚远的假设。 这是我的搜索功能

/* Functions to search for an element */
        bool search(int val)
        {
            return search(root, val);
        }

        /* Function to search for an element recursively */
        bool search(SGTNode *r, int val)
        {
            bool found = false;
            while ((r != NULL) && !found)
            {
                cnt++;
                cnt++;
                int rval = r->value;
                if (val < rval){
                    cnt++;
                    r = r->left;
                }
                else if (val > rval){
                    cnt++;
                    cnt++;
                    r = r->right;
                }
                else
                {
                    cnt++;
                    cnt++;
                    found = true;
                    break;
                }
                found = search(r, val);
            }
            cnt++;
            cnt++;
            return found;
        }

我 100% 确定在调用搜索之前 cnt 计数器为 0。如果您需要我的更多代码，请随时询问。

Answer 1

看起来您正在将递归和迭代方法混合到二进制搜索中。所以选择一个:

迭代方法(选我):

bool search(SGTNode *r, int val)
{
    while (r)
    {
        int rval = r->value;
        if (val < rval)
            r = r->left;
        else if (val > rval)
            r = r->right;
        else
            return true;
    }
    return false;
}

递归方法(不要选我，我只是看起来更好看):

bool search(SGTNode *r, int val)
{
    if(!r) // End the recursion if an element is not found
        return false;

    int rval = r->value;
    if (val < rval)
        return search(r->left,val);
    else if (val > rval)
        return search(r->right)
    else // Ends the recursion if an element is found
        return true;
}

根据需要添加计数器。