Removing Data

Removing data in BST is a quite complex algorithm compare to other methods.

There are 3 scenarios for removing data in BST:

  • Find the node to be deleted.
    • If the node doesn't exist, exit.
  • Leaf (terminal) node.
    • Delete and remove parent's pointer to deleted node.
  • Non-leaf node.
    • Find the child to replace the deleted node.

We will focus on the third scenario, if the deletion occured on non-leaf node.

Basically, it has 3 scenarios within.

  1. Removed node has no right child -> Remove(8)

    1. Left child replaces the removed.

      1. Find node to removed.

      2. Has no right child.

      3. Promote left child.

  2. Removed right child nas no left. -> Remove(6)

    1. Right child replaces the removed.

      1. Find node to remove.

      2. Node right has no left.

      3. Promote right child.

  3. Removed right child has left child -> Remove(6)

    1. Right child's left-most child replaces removed.

      1. Find node to remove.

      2. Node right has left.

      3. Find right's left-most child.

      4. Promote left-most child.

results matching ""

    No results matching ""