Content deleted Content added
Improve formatting |
Tag: Reverted |
||
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]].
'''Complexity Analysis'''
'''1. Search, Insertion & Deletion'''
'''Time Complexity:''' 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 ===
| |||