A search tree built once from sorted data can be perfectly balanced, but a tree that is used does not stay that way. This simulation shows it.
Start with the keys 1 .. n inserted in the order a balanced build would choose: repeatedly take the middle of the current range, then do the same for the left half and then the right half. Then run cycles rounds; in round t, counting from 0, remove the key (t * step) % n + 1 using the symmetric successor rule and insert it straight back as an ordinary leaf.
Write deletion_drift(n, cycles, step) returning the height of the final tree, where an empty tree has height 0 and a leaf has height 1.
Examples
Input: n = 15, cycles = 0, step = 7
Output: 4
Explanation: fifteen keys inserted that way make a perfect tree of height 4.
Input: n = 15, cycles = 20, step = 7
Output: 5
Constraints
1 <= n <= 1023,0 <= cycles <= 20000,1 <= step <= 10**6- Every key removed is immediately reinserted, so the tree always holds exactly
nkeys.
Goals
- Simulate a long run of deletions and reinsertions
- Measure the height instead of assuming it stays logarithmic
- See the cost of always taking the heir from the same side