2 ms·
They were technically correct. The lookup time on a binary search tree is O(H), which is equal to O(log2n) if the tree is balanced. Tree data structures invest
by slavak 5y ago
They were technically correct. The lookup time on a binary search tree is O(H), which is equal to O(log2n) if the tree is balanced. Tree data structures invest a lot of complexity into keeping the tree balanced.
- planet-and-halo 5y agoDoesn't this only affect inserts and deletes though? I mean I get your point, but on a read you can assume that a binary tree is balanced (by definition). Or am I missing something?
- wtetzner 5y agoNo, not all binary trees are balanced binary trees.
- planet-and-halo 5y agoAh got it, thanks.