Timeline for Binary Search Tree - My own version of delete function
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2022 at 7:29 | vote | accept | Muhammad Ahmad | ||
| Mar 10, 2022 at 15:08 | comment | added | FMc |
@MuhammadAhmad Iteration vs recursion has no effect on the Big-O characteristics of search(): even if you're iterating, you still benefit from the divide-and-conquer structure of the underlying tree. Also remember than a simple BST like this one might behave more like O(N) (with both recursion and iteration) if the tree becomes unbalanced -- hence the existence of things like red-black trees. Using a simple array/list plus binary-search comes with it own costs: you have to maintain the array in a sorted state after every insert.
|
|
| Mar 10, 2022 at 5:36 | comment | added | Muhammad Ahmad | I have a question if I use iteration instead of recursion, don't you think the Big O notation will become O=(n) for searching, inserting, and deleting. You are also right that I can hit the maximum recursion limit but if I use iteration then it kinda kills the point of making a binary tree in the first place, why not make an array or list and then apply binary search over it? | |
| Mar 3, 2022 at 22:18 | history | edited | Toby Speight | CC BY-SA 4.0 |
Spelling/grammar
|
| Mar 3, 2022 at 21:42 | history | answered | FMc | CC BY-SA 4.0 |