[C language algorithm] Binary search tree

Implemented binary search tree algorithm in C language

Environment used for learning

Reference material

Latest algorithm dictionary in C language (written by Haruhiko Okumura / 1991 first edition Gijutsu-Hyoronsha: 206 pages)

Binary search tree overview

Quoted from the reference materials below

Binary tree used for search. Each node has data and two pointers, all the data of the offspring connected by the left pointer left is smaller than itself, and all the data of the offspring connected by the right pointer right is larger than oneself. A binary search tree search starts at the root and follows the left or right pointer, depending on whether the object you are looking for is smaller or larger than the node. A perfectly balanced binary tree can be compared n times to find the desired one from 2 to the n-1 factorial.

Source code

postfix.c


//Binary search tree

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

//Type declaration of the key used for the search
typedef char keytype[21];

//Binary node node type declaration
typedef struct node {
    struct node *left, *right;  //Pointers to the left and right child nodes
    keytype key;                //Search key
} *nodeptr;     //Pointer to a node

struct node nil;    //Node representing the end of the tree
nodeptr root = &nil;    //Pointer to the root

//Insert into a tree(Registration)function
nodeptr insert(keytype insertkey){
    int cmp;
    nodeptr *p;     //Pointer to a node
    nodeptr q;      //Node entity

    strncpy(nil.key,insertkey,sizeof(keytype));  //Copy the argument key to the guard's key

    p = &root;  //Assign the root pointer to the pointer of the internal variable

    //Loop until the keys match
    while((cmp = strncmp(insertkey, (*p)->key, sizeof(keytype))) != 0)
    {
        //If the insert key is less than the key of the node pointed to by the pointer, move to the smaller node on the left
        //If the insert key is greater than the key of the node pointed to by the pointer, move to the larger node on the right
        if(cmp < 0){
            //Move the pointer to the left
            p = &((*p)->left);
        } 
        else{
            //Move the pointer to the right
            p = &((*p)->right);
        }
    }

    //If the key is already registered
    if(*p != &nil){
        return NULL;
    }

    //Allocate memory area for node
    if((q = malloc(sizeof(*q))) == NULL){
        printf("insert:Failed to secure memory area due to insufficient memory.\n");
        exit(EXIT_FAILURE);
    }
    
    //Copy the node key
    strncpy(q->key, insertkey, sizeof(keytype));

    q->left = &nil;
    q->right = *p;
    *p = q;

    //Returns the registered node
    return q;

}

//Delete function
//Returns 0 if it can be deleted, 1 if it fails
int delete(keytype deletekey){
    int cmp;

    nodeptr *p, *q;
    nodeptr r, s;

    strncpy(nil.key, deletekey, sizeof(keytype));   //Guardian

    p = &root;

    //Loop until the keys match
    while((cmp = strncmp(deletekey, (*p)->key, sizeof(keytype))) != 0)
    {
        //If the insert key is less than the key of the node pointed to by the pointer, move to the smaller node on the left
        //If the insert key is greater than the key of the node pointed to by the pointer, move to the larger node on the right
        if(cmp < 0){
            p = &((*p)->left);
        }
        else{
            p = &((*p)->right);
        }
    }

    //If the key is not found
    if(*p == &nil){
        return 1;
    }

    r = *p;

    if(r->right == &nil){
        *p = r->right;
    }else if(r->left == &nil){
        *p = r->right;
    } else{
        q = &(r->left);
        
        while((*q)->right != &nil){
            q = &((*q)->right);
        }

        s = *q;
        *q = s->left;
        s->left = r->left;
        s->right = r->right;
        *p = s;
    }

    //Free up space
    free(r);

    return 0;

}

//Search function
//If the key is found, it returns a pointer to the node that holds the key
//Returns NULL if not found
nodeptr search(keytype searchkey){
    int cmp;
    nodeptr p;

    strncpy(nil.key, searchkey, sizeof(keytype));
    p = root;

    while((cmp =strncmp(searchkey, p->key, sizeof(keytype))) != 0){
        if(cmp < 0){
            p = p->left;
        }else{
            p = p->right;
        }
    }
    
    if(p != &nil){
        //If found
        return p;
    }else{
        //If not found
        return NULL;
    }

}

void printtree(nodeptr p){
    static int depth = 0;

    //Show the node on the left
    if((p->left) != &nil){
        depth++;
        //Recursive call
        printtree(p->left);
        depth--;
    }

    //Display the node received as an argument
    printf("%*c%s\n", 5*depth, ' ', p->key);

    //Show the node on the right
    if(p->right != &nil){
        depth++;
        //Recursive call
        printtree(p->right);
        depth--;
    }
}

int main(void) {

    char buf[22];
    short count;

    printf( "Command Iabc:Insert abc\n"
            "       Dabc:Remove abc\n"
            "       Sabc:Search for abc\n");
    
    for(;;){
        printf("What is the order?");
        
        //Receive data from standard input for buf size
        if(scanf("%21s%*[^\n]", buf) != 1){
            break;
        }

        switch(buf[0]){
            //Insert process
            case 'I': case'i':
                //Insert function
                if(insert(&buf[1])){
                    printf("%21s%*[^\n]:Has registered\n",buf);
                }else{
                    printf("%21s%*[^\n]: Registered\n",buf);
                }

                break;

            //Delete process
            case 'D': case 'd':
                //Delete function
                if(delete(&buf[1])){
                    printf("%21s%*[^\n]: Not deleted\n",buf);
                }else{
                    printf("%21s%*[^\n]:It has been deleted\n",buf);
                }

                break;

            //Search process
            case 'S': case 's':
                //Delete function
                if(search(&buf[1])){
                    printf("%21s%*[^\n]: Registered\n",buf);
                }else{
                    printf("%21s%*[^\n]:not registered\n",buf);
                }

                break;
            default:
                printf("I can use, D,Only S\n");
                break;
        }

        if(root != &nil){
            printf("\n");
            printtree(root);
            printf("\n");
        }

        count++;
        
    }

	return EXIT_SUCCESS;
}

Execution result

stdin.txt(Any)


Iabc
Sabc
Dabc

stdout.txt(Any)


Command Iabc:Insert abc
       Dabc:Remove abc
       Sabc:Search for abc
What is the order? Has registered

 abc

What is the order?
Success #stdin #stdout 0s 4368KB
Command Iabc:Insert abc
       Dabc:Remove abc
       Sabc:Search for abc
What is the order? not registered
What is the order?
Success #stdin #stdout 0s 4516KB
Command Iabc:Insert abc
       Dabc:Remove abc
       Sabc:Search for abc
What is the order? Not deleted
What is the order?

Impressions

Recommended Posts

[C language algorithm] Binary search tree
C language ALDS1_4_B Binary Search
Algorithm in Python (ABC 146 C Binary Search
[C language algorithm] Endianness
[C language algorithm] Block movement
Binary search in Python / C ++
C language ALDS1_4_A Linear Search
Algorithm learned with Python 10th: Binary search
visualize binary search
String search algorithm
ABC146C (binary search)
[C language algorithm] Postfix notation (or reverse Polish notation)
Binary search in Python
C language ALDS1_3_B Queue
Binary search (python2.7) memo
[Python] Binary search ABC155D
Binary search with python
Binary search with Python3
Binary search tree is a relative of Hash chain !?
Binary search in Python (binary search)
Machine language embedding in C language
Heapsort made in C language
Search algorithm using word2vec [python]
[C language] readdir () vs readdir_r ()
Minimum spanning tree in C #