Deletion in a Binary search tree

Deletion in a Binary search tree

Suppose T is a binary search tree, and an ITEM of information is given. This section gives an algorithm which deletes ITEM from the tree T. The deletion algorithm first find the location of the node N which contains ITEM and also the location of the parent node P(N). The way N is deleted from the tree depends primarily on the number of children of node N. There are three cases:

Case 1: N has no children. Then N is deleted from T by simply replacing the location of N in the parent node P(N) by the null pointer.

Case 2: N has exactly one child. Then N is deleted from T by simply replacing the location of N in P(N) by the location of the only child of N.

Case 3: N has two children. Let S(N) denotes the inorder successor of N. Then N is deleted from T by first deleting S(N) from T and then replacing node N in T by the node S(N).

---

(I) Algorithm:

---

When the node has no child or one child: CASEA (INFO, LEFT, RIGHT, ROOT, PAR, LOC)

This procedure deletes the node N at location LOC, where N does not have two children. The pointer PAR gives the location of the parent of N, or else PAR = NULL indicates that N is the root node. The pointer CHILD gives the location of the only child of N, or else CHILD = NULL indicates that N has no children.

1. [Initialize CHILD.]
If  LEFT[LOC] = NULL and RIGHT[LOC] = NULL, then:
      Set CHILD := NULL.
Else if:
      LEFT[LOC] != NULL, then:
      Set CHILD := LEFT[LOC].
Else:
      Set CHILD := RIGHT[LOC].
[End of If structure.]

2. If  PAR != NULL, then:
      If LOC = LEFT[PAR], then:
            Set LEFT[PAR] := CHILD.
      Else:
            Set RIGHT[PAR] := CHILD.
      [End of Inner If.]
Else:
      Set ROOT := CHILD.
[End of Outer If.]

3. Return.

---

(II) Algorithm:

When the node has two children: CASEB (INFO, LEFT, RIGHT, ROOT, LOC, PAR) 

This algorithm will delete the node N at location LOC, where N has two children. The pointer PAR gives the location of the parent of N, or else PAR = NULL indicates that N is the root node. The pointer SUC gives the location of the inorder successor of N, and PARSUC gives the location of the parent of the inorder successor.
1. [Find inorder successor and its parent in SUC & PARSUC respectively.]
      a) Set PTR := RIGHT[LOC] and SAVE := LOC.
      b) Repeat while LEFT[PTR] != NULL;
      Set SAVE := PTR and PTR := LEFT[PTR].
[End of loop.]

c) Set SUC := PTR and PARSUC := SAVE.
2. [Delete inorder successor.]
Call CASEA(INFO, LEFT, RIGHT, ROOT, SUC, PARSUC).

3. [Replace node N by its inorder successor.]
a) If PAR != NULL, then:
If LOC = LEFT[PAR], then:
Set LEFT[PAR] := SUC.
Else:
Set RIGHT[PAR] := SUC.
[End of Inner If.]
Else:
Set ROOT := SUC.
[End of Outer If.]
b) Set LEFT[SUC] := LEFT[LOC] and
RIGHT[SUC] := RIGHT[LOC].

4. Return.

---

(III) Algorithm:

---

DEL(INFO, LEFT, RIGHT, ROOT, AVAIL, ITEM, LOC)
A binary search tree T is in memory and an ITEM of information is given. This algorithm deletes ITEM from the tree.

1. [Find the locations of ITEM and its parent.]
Call FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC, PAR).

2. [ITEM in tree]
If LOC = NULL, then: Write: ITEM not in tree, and Exit.

3. [Delete node containing ITEM.]
If LEFT[LOC] != NULL and RIGHT[LOC] != NULL, then:
Call CASEB(INFO, LEFT, RIGHT, ROOT, LOC, PAR).
Else:
Call CASEA(INFO, LEFT, RIGHT, ROOT, PAR, LOC).
[End of If structure.]

4. [Return deleted node to the AVAIL list.]
Set RIGHT[LOC] := AVAIL and AVAIL := LOC. 5. Exit.