2 ms·
One way to maintain leaves efficiently (amortised O(1) time and space to add/remove) is to keep 2 extra vectors that "point at each other": L[] is a vector cont
by akoboldfrying 3y ago
One way to maintain leaves efficiently (amortised O(1) time and space to add/remove) is to keep 2 extra vectors that "point at each other": L[] is a vector containing the indices of all leaves, and LP[] is a vector such that LP[i] stores the index within L[] of the value i if i is a leaf, and -1 otherwise. That is, for i a non-leaf, LP[i] == -1, while for i a leaf, L[LP[i]] == i.
To find the indices of all leaves: That's just L[].
To add a leaf i: Append i to L[], and set LP[i] to L.length - 1.
To remove a leaf i in constant time:
j = L[L.length - 1]
L[LP[i]] = j
LP[j] = i
LP[i] = -1.
DropLastElement(L[])