Question 12.1.5: Write a procedure that deletes an element t from a set repr......
Write a procedure that deletes an element t from a set represented as an ordered tree. (If the element is not in the set, nothing should be done.)
| if root = null then begin
{the tree is empty, there is nothing to do} end else begin x := root; if t < val [x] then begin father := x; direction := l; end else begin {t > val [x]} father := x; direction := r; end; end; ..delete the node x with a known father and direction end; end; |
The deletion of a vertex uses the procedure
| procedure make_free (i: integer); begin left [i] := free; end |
which adds the number i to the free list. While deleting a vertex, we should distinguish between four cases depending on whether the vertex has a left/right son or not.
| if (left [x] = null) and (right [x] = null) then begin
{x is a leaf, no sons) root := null; end else if direction = l then begin left [father] := null; end else begin {direction = r) right [fathers := null; end; {when x is deleted, right[x] occupies its place) root := right [x]; end else if direction = l then begin left [fathers := right [x]; end else begin {direction = r) end; end else if (left [x] <> null) and (right [xl=null) then begin …the symmetrical code end else begin {left [x] <> null, right [x] <> null) ..delete a vertex with two sons end ; |
The deletion of a vertex with two sons is the most difficult case. Here we should exchange it with an immediately following vertex (in the sense of label ordering).
| y := right [x]; father := x; direction := r; {now father and direction refer to vertex y) while left [y] <> null do begin father := y; direction := l; end |
| {val[y] is minimal element of the set larger than val[x], y has no left son} val [x] := val [y]; ..delete the vertex y (we already know how to do that for a vertex without the left son) |