# Binary search tree: remove

## Contents

## General Information

**Algorithmic Problem:** Sorted sequence:remove

**Type of algorithm:** loop

**Auxiliary data:** A pointer of type "pointer to binary search tree node of type ."

## Abstract view

**Invariant** After interations:

- The pointer points to a tree node on height level .
- The key is in range of , but .

**Variant:** increased by .

**Break Condition:** One of the following two conditions is fulfilled:

- It is .key and either .left = void or .left.key .
- It is .key and either .right = void or .right.key = .

**Remark:** For example, the height of the subtree rooted at the node to which points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.

## Induction basis

**Abstract view:**

- If the root contains , remove this occurrence of .
- Otherwise, initialize so as to point to the root.

**Implementation:**

- If root.key :
- If root.left = void, set root := root.right.
- Otherwise, if root.right = void, set root := root.left.
- Otherwise, call method remove node with pointer root.
- Terminate the algorithm and return
**true**.

- Otherwise set root.

**Proof:** Obvious.

## Induction step

**Abstract View:**

- If the next node where to go does not exist or contains , terminate the algorithm (and in the latter case, remove that node appropriately).
- Otherwise, descend to that node.

**Implementation:**

- If .key:
- If .left = void, terminate the algorithm and return
**false**. - Otherwise if .left.key :
- If .left.left = void, set .left := p.left.right.
- Otherwise, if .left.right = void, set .left := p.left.left.
- Otherwise, call method remove node with pointer .left.
- Terminate the algorithm and return
**true**.

- Otherwise (that is, .left void and .left.key ), set .left.

- If .left = void, terminate the algorithm and return
- Otherwise (that is, .key):
- If .right = void, terminate the algorithm and return
**false**. - Otherwise, if .right.key :
- If .right.left = void, set .right .right.right.
- Otherwise, if .right.right = void, set .right .right.left.
- Otherwise, call method remove node with pointer .right.
- Terminate the algorithm and return
**true**.

- Otherwise (that is, .right void and .right.key ), set .right.

- If .right = void, terminate the algorithm and return

**Correctness:** Nothing to show.

## Pseudocode

TREE-DELETE(T,z)

- if left[z] = NULL or right[z] = NULL
- then y = z
- else y = TREE-SUCCESSOR(z)

- if left[y] ≠ NULL
- then x = left[y]
- else x = right[y]

- if x ≠ NULL
- then p[x] = p [y]

- if p[y] = NULL
- then root[T] = x
- else if y = left[p[y]]
- then left[p[y]] = x
- else right[p[y]] = x

- if y ≠ z
- then key[z] = key[y]
- copy y's satellite data into z

- then key[z] = key[y]
- return y

## Complexity

**Statement:** The complexity is in in the worst case, where is the length of the sequence, the height of the tree, and the complexity of the comparison.

**Proof:** Obvious.