DEV Community

Discussion on: No More Tears, No More Knots: Arena-Allocated Trees in Rust

View post
Collapse
 
u_dev profile image
u_dev •

This is awesome
One thing i would like to understand is, the ideal look up time for a tree is O(logn) but that doesnt seem to be followed here since you are iterating all the nodes in the vector.

for node in &self.arena {
            if node.val == val {
                return node.idx;
            }
        }
Enter fullscreen mode Exit fullscreen mode

this seems to take O(n) time. Is this a known tradeoff?