2 ms·
Isn't that expected (within a constant factor of optimal depth, a.k.a. O(log N) tree height)? They're essentially building a treap, minus the in-order traversa
by KMag 6y ago
Isn't that expected (within a constant factor of optimal depth, a.k.a. O(log N) tree height)? They're essentially building a treap, minus the in-order traversal of keys restriction.
[0] https://en.wikipedia.org/wiki/Treap https://en.wikipedia.org/wiki/Treap
- eutectic 6y agoOptimal depth for union-find is O(1); every node points directly to the root. It's a very different case than building a binary search tree.