Binary search trees
Binary search tree basic operations such as access, search, insertion, and deletion take between O(n) and O(log(n)) time. Being both values the worst and the average scenarios. At the end, these times are going to depend on the height of the tree itself.
For example, for a complete binary search tree with n nodes, these operations could take O(log(n)) time. But if a tree with the same number of nodes n is built like a linked list (just 1 child per node), having more levels/depth for the same n nodes, then the operations are going to take O(n) time.
In order to make basic operations such as insertion or search, we need to scan nodes from the root to the leaves. Because of this, we can infer that the height of the tree (the distance ...
Get Swift Data Structure and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
