1. Concept
   1. Properties
   2. Structure
2. Code
   1. Basic Operations

Concept

Binary Search Tree (BST), also known as a binary sort tree or binary ordered tree, is either an empty tree or a binary tree with the following properties:

• If its left subtree is not empty, then all the nodes on the left subtree have values less than the root node’s value.
• If its right subtree is not empty, then all the nodes on the right subtree have values greater than the root node’s value.
• Both its left and right subtrees are also binary search trees.

As a classical data structure, binary search trees offer fast insertion and deletion operations, along with efficient searching capabilities. Hence, they find wide applications, such as in file systems and database systems for efficient sorting and retrieval operations.

Properties

Binary search trees possess the following properties:

• If the left subtree is non-empty, all the node values on the left subtree are less than the root node’s value.
• If the right subtree is non-empty, all the node values on the right subtree are greater than the root node’s value.
• Both the left and right subtrees are binary search trees.

Structure

A BST is constructed using binary trees. In addition to key and positional data, each node also contains attributes lchild and rchild. If a child node does not exist, the corresponding attribute value is null.

typedef struct Node {
    int data;                               // Data
    struct Node *lchild, *rchild;  			// Left and Right Child
} * BST, BSTNode;

Code

Basic Operations

The construction and destruction of a BST are similar to those of a regular binary tree. Here, we focus on additional operations like search, insertion, and deletion compared to regular binary trees.

The find() function searches whether a node with a known data value exists in the tree and returns the node. The code is as follows:

BST find(BST tree, int data){
    BST p = tree;
    while(p) {
        if (p->data == data) return p;
        if (data < p->data) {
            p = p->lchild;
        } else {
            p = p->rchild;
        }
    }
    return NULL;
}

The insert() function inserts a node into the tree. All nodes in a BST are inserted as leaf nodes. Hence, after creating node , we find the appropriate parent node and insert there. The code is as follows:

bool insert(BST& tree, int data) {
    BST p = tree, f;
    while(p) {
        if (p->data == data) return false;
        f = p;                  // Record f as the parent node of p
        if (data < p->data) {
            p = p->lchild;
        } else {
            p = p->rchild;
        }
    }                           // Check if data is already in the tree

    p = (BST) malloc(sizeof(BSTNode));
    p->lchild = p->rchild = NULL;
    p->data = data;             // Create node

    if(!tree) tree = p;
    else if(data < f->data) f->lchild = p;
    else f->rchild = p;
    return true;
}

After deleting a node in a binary search tree, its sorting order must still be maintained. Therefore, deletion is divided into three cases:

• If the node to be deleted has no left child, replace it with its right child.
• If the node to be deleted has no right child, replace it with its left child.
• If the node to be deleted has both left and right children, replace it with either the maximum node in its left subtree or the minimum node in its right subtree.

The code is as follows:

bool delete(BST& tree, int data) {
    if(!tree) return false;
    BST p = tree, f;
    while(p) {
        if (p->data == data) break;
        f = p;                  // Record f as the parent node of p
        if (data < p->data) {
            p = p->lchild;
        } else {
            p = p->rchild;
        }
    }                           // Find the position of data
    if(!p)  return false;       // If not found, return false
    if(!p->lchild) {            // Case 1
        if(tree == p) tree = p->rchild;
        else if(f->lchild == p) f->lchild = p->rchild;
        else if(f->rchild == p) f->rchild = p->rchild;
        free(p);
    }
    else if(!p->rchild){        // Case 2
        if(tree == p) tree = p->lchild;
        else if(f->lchild == p) f->lchild = p->lchild;
        else if(f->rchild == p) f->rchild = p->lchild;
        free(p);
    }
    else{                       // Case 3
        BST tmp = p->lchild, fl = p;
        while(tmp->rchild) fl = tmp,tmp = tmp->rchild;
        p->data = tmp->data;
        if(fl->lchild == tmp) fl->lchild = NULL;
        else if(fl->rchild == tmp) fl->rchild = tmp->lchild;
        free(tmp);
    }
    return true;
}