CODEWITHSUNDEEP
javadata-structuresgarbage-collectionbinary-search-tree
Nickolay Kondratyev
Nickolay Kondratyev

Reputation: 5211

Deleting the whole BST in java

I am looking over implementations of BSTs in Java, and when the whole tree needs to be deleted (for example using the clear() function), it recursively goes through the whole tree assigning node references to null. I was wondering if the garbage collector would be able to collect all memory allocated for the tree if just the Root reference of the tree were set to null instead, since there wouldn't be any live references to the nodes after the Root is set to null? And if this works, would it take multiple garbage collector runs to collect the entire tree?

Upvotes: 2

Views: 206

Answers (2)

Stephen C
Stephen C

Reputation: 718886

I was wondering would the garbage collector in java be able to collect all memory allocated for the tree if just the Root reference of the tree were to be set to null without setting every single node reference to null since there wouldn't be any alive references to the nodes after the Root is set to null?

Yes. When the last live external reference to a network of nodes is removed, all of the nodes are eligible for garbage collection. This sounds like what you are describing.

And if it would be able to collect the memory of the tree would it take multiple garbage collector runs to go through each level of the tree?

In the simple case, the garbage collector can delete them all in one go. In any garbage collector that uses marking (rather than reference counts), the garbage collector does not need to traverse the network of objects that are garbage. Rather, it traverses and marks NON-garbage objects, and treats objects that it didn't mark as garbage.

In practice, sophisticated garbage collectors partition the heap into spaces (e.g. a new generation and one or more old generations) and can garbage collect (at least) some of them independently. If your tree's nodes have been migrated to an older generation space, then it could take more than one "cycle" of the GC to delete them all. However, there's not much you can do about this ... and you shouldn't care about it anyway.

Upvotes: 2

Mike Kwan
Mike Kwan

Reputation: 24447

The garbage collector will be able to reclaim the memory of the whole tree once there are no references to any of the nodes of the tree. If no references exist to the root node but an accessible reference still exists to a child node, then the tree can not be removed from memory.

Imagine how the garbage collector works. It builds a graph of all accessible memory from various roots (statics, globals, scoped variables, etc.). Any memory which is still accessible can not be reclaimed. If a single node is still accessible then anything that is accessible from it also can not be reclaimed (most implementations of nodes of BSTs have accessors for the parent node).

Upvotes: 0

Related Questions