Cây tìm kiếm nhị phân
Các phép toán trên BST > Xóa (Deletion)

Xét các trường hợp sau
Xóa một lá: Vì lá không có con nên chỉ cần giải phóng nó khỏi cây.
Xóa nút có một con: Xóa và thay thế nó bằng con duy nhất của nó.
Xóa một nút có hai con: Xóa nút đó và thay thế nó bằng nút có khóa lớn nhất trong các khóa nhỏ hơn khóa của nó (được gọi là "nút tiền nhiệm" -nút cực phải của cây con trái) hoặc nút có khóa nhỏ nhất trong các khóa lớn hơn nó (được gọi là "nút kế vị" - nút cực trái của cây con phải)
Cũng có thể tìm nút tiền nhiệm hoặc nút kế vị đổi chỗ nó với nút cần xóa và sau đó xóa nó. Vì các nút kiểu này có ít hơn hai con nên việc xóa nó được quy về hai trường hợp trước.
Sau đây là mã C++
void DeleteNode(struct node*& node) {
    if (node->left == NULL) { 
    
        struct node* temp = node;
        node = node->right;
        delete temp;
    } else if (node->right == NULL) {
     
        struct node* temp = node;
        node = node->left;
        delete temp;
       
    } else {
        // In-Order predecessor(right most child of left subtree) 
        // Node has two children - get max of left subtree

        struct node** temp = &(node->left); // get left node of the original node

        // find the right most child of the subtree of the left node
        while ((*temp)->right != NULL) {
            temp = &((*temp)->right);
        }
         
        // copy the value from the right most child of left subtree to the original node
        node->value = (*temp)->value;

        // then delete the right most child of left subtree since it's value is
        // now in the original node
        DeleteNode(*temp);
    }
}
Mã python:
def findMin(self):
    '''
    Finds the smallest element that is a child of *self*
    '''
    current_node = self
    while current_node.left_child:
        current_node = current_node.left_child
    return current_node

def replace_node_in_parent(self, new_value=None):
    '''
    Removes the reference to *self* from *self.parent* and replaces it with *new_value*.
    '''
    if self == self.parent.left_child:
        self.parent.left_child = new_value
    else:
        self.parent.right_child = new_value
    if new_value:
        new_value.parent = self.parent

def binary_tree_delete(self, key):
    if key < self.key:
        self.left_child.binary_tree_delete(key)
    elif key > self.key:
        self.right_child.binary_tree_delete(key)
    else: # delete the key here
        if self.left_child and self.right_child: # if both children are present
            # get the smallest node that's bigger than *self*
            successor = self.right_child.findMin()
            self.key = successor.key
            # if *successor* has a child, replace it with that
            # at this point, it can only have a *right_child*
            # if it has no children, *right_child* will be "None"
            successor.replace_node_in_parent(successor.right_child)
        elif self.left_child or self.right_child:   # if the node has only one child
            if self.left_child:
                self.replace_node_in_parent(self.left_child)
            else:
                self.replace_node_in_parent(self.right_child)
        else: # this node has no children
            self.replace_node_in_parent(None)