Функция поиска козла отпущения

Question

Я вставил 30000 случайных чисел в дерево козла отпущения. У меня есть счетчик для отслеживания сравнений моих вставок и поисков. Я пытался найти число 3337, оно не было найдено, но трекер сказал, что для того, чтобы сделать это предположение, достаточно далеко от 6 миллионов сравнений, что довольно далеко от сложности 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;
}

Добавьте counters по своему усмотрению.