Binary search tree: remove

Binary Search Tree
Remove

Sorted sequence

Openlearnware
See Chapter 5

General Information

Algorithmic Problem: Sorted sequence:remove

Type of algorithm: loop

Auxiliary data: A pointer [math]\displaystyle{ p }[/math] of type "pointer to binary search tree node of type [math]\displaystyle{ \mathcal{K} }[/math]."

Abstract view

Invariant After [math]\displaystyle{ i \geq 0 }[/math] interations:

1. The pointer [math]\displaystyle{ p }[/math] points to a tree node [math]\displaystyle{ v }[/math] on height level [math]\displaystyle{ i }[/math].
2. The key [math]\displaystyle{ K }[/math] is in range of [math]\displaystyle{ p }[/math], but [math]\displaystyle{ p.key \neq K }[/math].

Variant: [math]\displaystyle{ i }[/math] increased by [math]\displaystyle{ 1 }[/math].

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

1. It is [math]\displaystyle{ K \lt p }[/math].key and either [math]\displaystyle{ p }[/math].left = void or [math]\displaystyle{ p }[/math].left.key [math]\displaystyle{ = K }[/math].
2. It is [math]\displaystyle{ K \gt p }[/math].key and either [math]\displaystyle{ p }[/math].right = void or [math]\displaystyle{ p }[/math].right.key = [math]\displaystyle{ K }[/math].

Remark: For example, the height of the subtree rooted at the node to which [math]\displaystyle{ p }[/math] points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.

Induction basis

Abstract view:

1. If the root contains [math]\displaystyle{ K }[/math], remove this occurrence of [math]\displaystyle{ K }[/math].
2. Otherwise, initialize [math]\displaystyle{ p }[/math] so as to point to the root.

Implementation:

1. If root.key [math]\displaystyle{ = K }[/math]:
   1. If root.left = void, set root := root.right.
   2. Otherwise, if root.right = void, set root := root.left.
   3. Otherwise, call method remove node with pointer root.
   4. Terminate the algorithm and return true.

1. Otherwise set [math]\displaystyle{ p := }[/math] root.

Proof: Obvious.

Induction step

Abstract View:

1. If the next node where to go does not exist or contains [math]\displaystyle{ K }[/math], terminate the algorithm (and in the latter case, remove that node appropriately).
2. Otherwise, descend to that node.

Implementation:

1. If [math]\displaystyle{ K \lt p }[/math].key:
   1. If [math]\displaystyle{ p }[/math].left = void, terminate the algorithm and return false.
   2. Otherwise if [math]\displaystyle{ p }[/math].left.key [math]\displaystyle{ = K }[/math]:
      1. If [math]\displaystyle{ p }[/math].left.left = void, set [math]\displaystyle{ p }[/math].left := p.left.right.
      2. Otherwise, if [math]\displaystyle{ p }[/math].left.right = void, set [math]\displaystyle{ p }[/math].left := p.left.left.
      3. Otherwise, call method remove node with pointer [math]\displaystyle{ p }[/math].left.
      4. Terminate the algorithm and return true.
   3. Otherwise (that is, [math]\displaystyle{ p }[/math].left [math]\displaystyle{ \neq }[/math] void and [math]\displaystyle{ p }[/math].left.key [math]\displaystyle{ \neq K }[/math]), set [math]\displaystyle{ p := p }[/math].left.
2. Otherwise (that is, [math]\displaystyle{ K \gt p }[/math].key):
   1. If [math]\displaystyle{ p }[/math].right = void, terminate the algorithm and return false.
   2. Otherwise, if [math]\displaystyle{ p }[/math].right.key [math]\displaystyle{ = K }[/math]:
      1. If [math]\displaystyle{ p }[/math].right.left = void, set [math]\displaystyle{ p }[/math].right [math]\displaystyle{ =p }[/math].right.right.
      2. Otherwise, if [math]\displaystyle{ p }[/math].right.right = void, set [math]\displaystyle{ p }[/math].right [math]\displaystyle{ = p }[/math].right.left.
      3. Otherwise, call method remove node with pointer [math]\displaystyle{ p }[/math].right.
      4. Terminate the algorithm and return true.
   3. Otherwise (that is, [math]\displaystyle{ p }[/math].right [math]\displaystyle{ \neq }[/math] void and [math]\displaystyle{ p }[/math].right.key [math]\displaystyle{ \neq K }[/math]), set [math]\displaystyle{ p:= p }[/math].right.

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

return y

Complexity

Statement: The complexity is in [math]\displaystyle{ \mathcal{O}(T\cdot h)\subseteq\mathcal{O}(T\cdot n) }[/math] in the worst case, where [math]\displaystyle{ n }[/math] is the length of the sequence, [math]\displaystyle{ h }[/math] the height of the tree, and [math]\displaystyle{ T }[/math] the complexity of the comparison.

Proof: Obvious.