Introduction

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

An example can be seen in the picture below.
A binary search tree of size 9 and depth 3

Operation

BST supports several operations, like search, insert, delete, transverse and etc.

Search

To search an element in BST, we could do it recursively or iteratively: in a top-down manner, compare with the value of current node and decide to go the left or right child of the node until we find the element or a null node (meaning the element does not exist).

Insert

Insertion is quite similar to the search operation, basically we do a search and make a new node once we encounter a null node, like the code below:

node* insert(node* node, int key) 
{ 
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key); 
  
    // If key already exists in BST,  
    // increment count and return 
    if (key == node->key) 
    { 
        (node->count)++; 
        return node; 
    } 
  
    /* Otherwise, recur down the tree */
    if (key < node->key) 
        node->left = insert(node->left, key); 
    else
        node->right = insert(node->right, key); 
  
    /* return the (unchanged) node pointer */
    return node; 
}

delete

There's a little more work for the deletion. To delete an element, we would have three cases:

  1. Deleting a node with no children: simply remove the node from the tree, in other words we replace the node with a null pointer;
  2. Deleting a node with one child: remove the node and replace it with its child;

  3. Deleting a node with two children: call the node to be deleted D. Do not delete D. Instead, choose either its in-order predecessor node or its in-order successor node as replacement node E. Copy the values of E to D. Note that the node E can only have 1 child or 0 child, so we can call again deletion operation to delete this node E. Refer to the graph below.
    BST deletion example
    In practice, when we delete the nodes with two children many times, if we always use the in-order successor or the in-order predecessor, the resulting tree would be very imbalanced. So it's better to select one or the other at different times.
    An example code would look like this:

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

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

node* deleteNode(node* root, int key) 
{ 
 // base case 
 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 key is present more than once,  
     // simply decrement count and return 
     if (root->count > 1) 
     { 
         (root->count)--; 
         return root; 
     } 
  
     // node with only one child or no child 
     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; 
     } 
  
     // node with two children: Get the inorder  
     // successor (smallest in the right subtree) 
     struct node* temp = minValueNode(root->right); 
  
     // Copy the inorder successor's  
     // content to this node 
     root->key = temp->key; 
  
     // Delete the inorder successor 
     root->right = deleteNode(root->right, 
                               temp->key); 
 } 
 return root; 
}

    Traverse

    To transverse the tree structure, there're three ways used very often: In-order, pre-order and post_order.

  4. Inorder traversal
    For example, the inorder transverse of the BST in the first image is: 1,3,4,6,7,8,10,13,14. The inorder traversal can print elements of the BST in non-decreasing order. And it's convenient to validate a BST using the inorder traversal. The basic traversal order is the following:

    1. traverse the left subtree, call Inorder(left-subtree)
    2. visit the node
    3. traverse the right subtree, call Inorder(right-subtree)

  5. PreOrder traversal
    The preorder transverse of the BST in the first image is: 8,3,1,6,4,7,10,14,13. The preorder could be used to get the prefix of an expression tree.

    1. visit the node
    2. traverse the left subtree, call Inorder(left-subtree)
    3. traverse the right subtree, call Inorder(right-subtree)

  6. Postorder traversal
    The postorder transverse of the BST in the first image is: 1,4,7,6,3,13,14,10,8. The postorder could be used to get the postfix of an expression tree.

    1. traverse the left subtree, call Inorder(left-subtree)
    2. traverse the right subtree, call Inorder(right-subtree)
    3. visit the node

Problems in LeetCode

文章目录