1
\$\begingroup\$

I tested creating 1 billion (1,000,000,000) nodes and lookups are fast. You can ask for a node by node_id.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
    int node_id;
    int data;
    char *name;
    struct node *left;
    struct node *right;
} node;


node *newNode(int data, char *name, int node_id) {
    node *new_node = malloc(sizeof(node));
    new_node->data = data;
    new_node->name = name;
    new_node->node_id = node_id;
    new_node->right = new_node->left = NULL;
    return new_node;
}

node *insert_node(node *root, int data, int node_id, char *name) {
    if (root == NULL)
        return newNode(data, name, node_id);
    else {
        node *cur;
        if (node_id < root->node_id) {
            cur = insert_node(root->left, data, node_id, name);
            root->left = cur;
        } else if (node_id > root->node_id) {
            cur = insert_node(root->right, data, node_id, name);
            root->right = cur;
        }
    }
    return root;
}


node *find_node_data(node *root, int node_id) {
    if (root == NULL)
        return NULL;
    else if (root->node_id == node_id)
        return root;
    else if (root->node_id > node_id)
        return find_node_data(root->left, node_id);
    else
        return find_node_data(root->right, node_id);
}

void print(node *np) {
    if (np) {
        print(np->left);
        printf("(%d, %d, %s)", np->node_id, np->data, np->name);
        print(np->right);
    }
}

int main() {
    int T = 1000000000; //test case 1000000000 nodes
    int data, node_id;
    //printf("Input number of nodes:");
    //scanf("%d", &T);
    node *root = NULL;
    srand(time(NULL));
    while (T-- > 0) {
        //printf("Input data. %d:", T);
        //scanf("%d %d", &data, &node_id);
        int r = rand() % 1000000000;
        int r2 = rand() % 1000000000;
        root = insert_node(root, r, r2, "Rosencrantz");
    }
    //print(root);
    printf("\n");
    printf("Find data at node:");
    scanf("%d", &T);
    printf("node data %d %s", find_node_data(root, T)->data, find_node_data(root, T)->name);
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ What is your question? \$\endgroup\$ – Olivier Jacot-Descombes Nov 16 '17 at 21:31
  • 2
    \$\begingroup\$ @OlivierJacot-Descombes At this exchange, there is always an implicit question: "Please review". \$\endgroup\$ – vnp Nov 16 '17 at 23:34
3
\$\begingroup\$
  • node *cur is not necessary. A idiom is

    if (node_id < root->node_id) {
        root->left = insert_node(root->left, data, node_id, name);
    
  • find_node_data is unnecessarily recursive. The compiler may understand that it is a tail recursion, and optimize it out, but it always better to be explicit:

        while (root) {
            if (root->node_id == node_id) {
                break;
            }
            root = root->node_id > node_id? root->left: root->right;
        }
        return root;
    

    Note the insertion may also be made iterative, although much less elegant.

  • The line

    printf("node data %d %s", find_node_data(root, T)->data, find_node_data(root, T)->name);
    

    looks really strange. Why do you call find_node_data twice, and why don't you call print, which you are already defined?

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.