Deleting Nodes#

One fundamental tree operation we haven’t covered yet is deleting nodes.

We saw previously a way to select sub-trees of a tree with a mask. For instance given the following tree:

p←1 7 4 1 7 6 3 7 6 1
(⍳≢p) PPV p

┌─────────┐
│    7    │
│   ┌┴───┐│
│   1    4│
│┌──┼──┐ ││
│0  3  9 2│
│   │     │
│   6     │
│  ┌┴┐    │
│  5 8    │
└─────────┘

Say we want to delete node $3$ and all of its descendants. We can mask all nodes which are node $3$ or one of its descendants using a method we’ve seen before.

⊢mask←3=p I@{⍵≠3}⍣≡⍳≢p
mask PPV p

0 0 0 1 0 1 1 0 1 0

┌─────────┐
│    0    │
│   ┌┴───┐│
│   0    0│
│┌──┼──┐ ││
│0  1  0 0│
│   │     │
│   1     │
│  ┌┴┐    │
│  1 1    │
└─────────┘

The first step will be to remove node $3$ and its descendants from the parent vector using this mask.

(~mask)/p

1 7 4 7 7 1

Like so many times before, we’re now left with parent pointers which need correcting. In the original p, a certain number of to-be-deleted nodes may have appeared before each node which was not deleted. After deleting the sub-tree, each node is therefore that many places farther back in the vector, and we need to correct the pointers to reflect that.

For instance, there are $3$ nodes which we will remove that appear before node $7$ in p, so when the nodes are removed, node $7$ will move to index $7-3=4$, and we need to update parent pointers accordingly.

index:     0 1 2 3 4 5 6 7 8 9
p:         1 7 4 1 7 6 3 7 6 1
mask:      0 0 0 1 0 1 1 0 1 0
                 ↑   ↑ ↑ ↑
  to-be-deleted ─┴───┴─┘ │
                   ┌─────┘
                   ↓
(~mask)/p: 1 7 4 7 7 1

We saw a similar situation when we were extracting trees from forests, where parent pointers were offset too far. In that instance, we found the offsets to correct by with a +\ on the mask of deleted nodes. We can use the same technique here, but for completeness, we’re going to show another way[1].

Firstly, let’s find the indices of all the nodes being deleted.

⍸mask

3 5 6 8

These indices define intervals, within which we know how many to-be-deleted nodes have appeared. For example, we know that $3$ such nodes appear before node $7$.

  1+(⍸mask)⍸7    ⍝ 3 to-be-deleted nodes appear before node 7
⍝ ││└───────┴───── in which interval does node 7 appear
⍝ └┴────────────── using ⎕IO←0 means we have to make this adjustment

3

This tells us exactly what to subtract in order to correct each parent pointer.

q←(~mask)/p          ⍝ delete unwanted nodes
  1+(⍸mask)⍸q        ⍝ deleted nodes appearing before each parent
q-1+(⍸mask)⍸q        ⍝ correcting the pointers

0 3 1 3 3 0

1 4 3 4 4 1

This correctly removes the whole sub-tree descending from node $3$.

((~mask)/⍳≢p) PPV q-1+(⍸mask)⍸q

┌─────┐
│  7  │
│ ┌┴─┐│
│ 1  4│
│┌┴┐ ││
│0 9 2│
└─────┘

We can put this all together into a tacit idiom we can easily reuse.

    (⍸mask)(⊢-1+⍸)(~mask)/p
PPV (⍸mask)(⊢-1+⍸)(~mask)/p

1 4 3 4 4 1

┌─────┐
│  ∘  │
│ ┌┴─┐│
│ ∘  ∘│
│┌┴┐ ││
│∘ ∘ ∘│
└─────┘