Persistent data structure: Difference between revisions

Revision as of 22:58, 18 April 2024

Revision as of 03:01, 19 April 2024

Line 136:

Notice two points: first, the original tree (<code>xs</code>) persists. Second, many common nodes are shared between the old tree and the new tree. Such persistence and sharing is difficult to manage without some form of [[Garbage collection (computer science)|garbage collection]] (GC) to automatically free up nodes which have no live references, and this is why GC is a feature commonly found in [[Functional programming|functional programming languages]].

'''Time Complexity Analysis: Search, Insertion & Deletion'''

In the best scenario (balanced tree), the time complexity would be O(log n) because the height of a balanced binary search tree is O(log n).

In unbalanced trees, the height could potentially grow to O(n), which would result in a worst-case time complexity of O(n).

=== Persistent hash array mapped trie ===