4 ms·
If you can spare some computation time when creating the trees you can simply generate recursive hashes (like git does), then you can immediately see if a given
by ThePhysicist 7y ago
If you can spare some computation time when creating the trees you can simply generate recursive hashes (like git does), then you can immediately see if a given tree exists anywhere as a subtree of a larger tree in O(1). Of course you will pay for this with O(n) time complexity and storage for creating and storing the hashes.
- pierrebai 7y agoNot really O(1), you still need to go through the big tree to find the node with teh deisred hash. You also have to check if the trees are truly identical to handle the case of hash collision.
- ThePhysicist 7y agoThe idea is that you create a hash map where the key is a tree hash and the value points to the tree in memory, so it should be O(1). Hash collision can of course happen but is extremely unlikely if you use a robust scheme like SHA256.