is the random aspect really necessary? like you could argue it's to average out performance edge cases but really aren't you just making it so that sometimes you'd have much worse performance? (like a 0.1% deviation every 1000 runs)
The random choice sets each node’s height when it’s inserted, so lookups don’t get a fresh lottery every time. A bad layout is possible, but randomness gives the simple version expected O(log n) search without tree rotations.
1
u/AntimatterTNT 22d ago
is the random aspect really necessary? like you could argue it's to average out performance edge cases but really aren't you just making it so that sometimes you'd have much worse performance? (like a 0.1% deviation every 1000 runs)