Время возвращает 0 в бинарном дереве поиска - PullRequest
Новая
       6

Время возвращает 0 в бинарном дереве поиска

0 голосов
/ 07 января 2019

Я хочу измерить время, необходимое для поиска x, проблема в том, что его всегда 0. Я пытался использовать разные методы расчета времени без удачи. Если я вычисляю вставку, то она работает правильно, так почему же она не работает в другом случае?

Функции работают правильно, потому что они взяты с сайта, который объясняет BST, моя задача - рассчитать и проанализировать время, необходимое для выполнения функций. 

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<windows.h>
#include <fstream>
#include <chrono>
#include <iomanip>
using namespace std;

struct node
{
    int key;
    struct node *left, *right;
};

struct node *newNode(int item)
{
    struct node *temp =  (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

struct node* insert(struct node* node, int key)
{
    if (node == NULL)
        return newNode(key);

    if (key < node->key)
        node->left  = insert(node->left, key);
    else
        node->right = insert(node->right, key);
}

struct node * minValueNode(struct node* node)
{
    struct node* current = node;


    while (current->left != NULL)
        current = current->left;

    return current;
}

struct node* search(struct node* root, int key)
{
    if (root == NULL || root->key == key)
        return root;

    if (root->key < key)
        return search(root->right, key);


    return search(root->left, key);
}


struct node* deleteNode(struct node* root, int key)
{ 
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else
    {
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        struct node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
return root;
}


int main()
{
    srand(time(NULL));
    clock_t start;
    struct node *root = NULL;

    for(int i=0; i<400000; i++)
    {
        root = insert(root,((rand()*rand())%20000));
    }

    double duration;

    start = std::clock();
    root = search(root, 19999);
    duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;

    cout << "Time: " << duration << endl;

    return 0;
}

1 Ответ

0 голосов
/ 07 января 2019

Ваша функция insert ничего не возвращает, если параметр node не равен NULL. Это неопределенное поведение, и может привести к буквально чему угодно, включая демонов, летящих из ваш нос .

Видя, что никакого segfault не происходит, может показаться, что компилятор изящно назначает NULL указателю root в main, что означает, что ваше дерево содержит не более двух элементов (а таких деревьев очень много, потерянных в памяти) , Поиск элемента в дереве двух элементов, безусловно, может занять 0 секунд. Но это просто случайное предположение - это UB, это может быть что угодно.

Вы должны включить предупреждения компилятора (для gcc, например, для флагов -Wall, -Wextra и -pedantic, предпочтительно с -Werror, чтобы превратить все предупреждения в ошибки). Такую проблему очень легко найти с помощью предупреждений компилятора.

...