Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Node Representation for Deletion

For deletion each node also stores a parent pointer, so a node ref has ref.left, ref.right, ref.data and ref.parent. Deletion must keep the BST property that insertion also keeps.

BSTreplace: One or No Child

BSTreplace(root, ref) removes a node ref that has at most one child:

  • if ref is the root, its child becomes the new root, stop
  • if ref is neither root nor leaf, its only child takes its place as the child of ref.parent, stop
  • if ref is a leaf, set the matching child pointer of ref.parent to None, stop

def BSTreplace(root, ref):               # ref has one or no child
    if ref.left is None:
        child = ref.right
    else:
        child = ref.left
    if ref == root:                      # deleting the root
        if child is not None:
            child.parent = None
        return child                     # child is the new root
    if ref.parent.left == ref:           # is ref a left child?
        ref.parent.left = child
    else:
        ref.parent.right = child
    if child is not None:
        child.parent = ref.parent        # keep the parent pointer right
    return root

Since child is None for a leaf, the same code covers the leaf case: the parent simply gets a None child.

Example: One Child, Not Root

Deleting , whose only child is : becomes the right child of and its parent pointer is updated to . In short, a node with one child is replaced by that child.

Two Children

A node with two children cannot simply be cut out. Instead:

  • step 1: find the successor succ, the minimum value in the right subtree, by going right once and then left until there is no left child
  • step 2: copy its value into the node to delete, ref.data = succ.data
  • step 3: delete succ with BSTreplace, which works because succ has no left child
def BSTdelete_two_children(root, ref):
    succ = ref.right
    while succ.left is not None:         # step 1
        succ = succ.left
    ref.data = succ.data                 # step 2
    return BSTreplace(root, succ)        # step 3

Example: Delete 5

The right subtree of is rooted at . Going left from reaches and then , which has no left child, so succ is .

The value is replaced by , and the old node is removed with BSTreplace, so its child moves up.

Choosing the minimum of the right subtree is a convention. The maximum of the left subtree would work equally well, which is why the definitions sheet says these implementation choices are not part of the BST definition.