BINARY SEARCH TREE 2

Binary Search Trees (BST) Deletion

Introduction to Deletion in a BST

  • Deletion in binary search trees can be accomplished in various ways depending on the structure of the tree and the node being deleted.

    • Three primary scenarios for deletion:

      1. No children (leaf node)

      2. One child

      3. Two children

Simple Deletion via Tombstones

  • To delete a value associated with a key (e.g., key I):

    • Change the node's value to null (tombstone approach) to signify deletion without restructuring the tree.

    • Consequence:

      • Can lead to longer search times (up to O(2 log n)) due to the presence of tombstones.

Traversals and Successor/Predecessor Concepts

  • In-order traversal of a BST organizes keys in sorted order.

    • Example sorted order from a sample traversal: 25, 31, 34, 35, 46, 47, 48, 50, 57, 60, 65, 91.

  • Successors and Predecessors:

    • Successor of 57 is 60, predecessor is 50.

    • To find the predecessor of a node:

      • Go to the left subtree and find the largest value there (rightmost node).

    • To find the successor:

      • Go to the right subtree and find the smallest value (leftmost node).

Finding Min/Max in a Subtree

  • Minimum Value:

    • Start from the root and go all the way left until reaching a null node.

  • Maximum Value:

    • Start from the root and go all the way right until reaching a null node.

Deletion Procedures for Different Cases

  1. Deleting a Node with No Children:

    • Simply set the parent's child pointer to null.

  2. Deleting a Node with One Child:

    • Connect the parent directly to the child of the node to be deleted.

  3. Deleting a Node with Two Children:

    • Find the successor or predecessor (minimum of the right subtree or maximum of the left subtree respectively).

    • Replace the node to be deleted with this successor or predecessor.

    • Delete the successor/predecessor node thereafter.

Example of Deletion Code Flow

  • Illustrative pseudocode for deleting minimum in BST:

    function deleteMin(node):
    if node.left is null:
        return node.right
    node.left = deleteMin(node.left)
    return node

  • In recursive deletion:

    • Check if node is null (base case).

    • For traversing left or right based on comparison to find the target node, and make the necessary child adjustments based on the three deletion cases.

Execution of Deletion Algorithm

  • Recursive deletion leverages stack operations for backtracking:

    • Replace links during traversal as you return.

    • Maintain the structure of the BST while removing targeted elements.

Time Complexity of Deletion

  • The average time complexity for deletion in a balanced BST is O(log n), but can degrade to O(n) in worst-case scenarios (e.g., for skewed trees).

Conclusion on BST Deletions

  • Understanding the structure and behavior of BSTs is crucial for implementing effective deletion algorithms.

  • Next steps involve exploring balanced search trees (e.g., 2-3 trees) to mitigate inefficiencies from linear time complexities.