undefined | Better HN

story

0 pointsKMag5y ago0 comments

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

0 comments

eutectic5y ago

Optimal 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.

j / k navigate · click thread line to collapse

0 comments

eutectic5y ago

Optimal 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.

j / k navigate · click thread line to collapse