So here's the question: If it's a big long chain, then it's essentially a linked list. So why is it O(n) if the structure is called a tree, but O(1) if the structure is called a linked list?
I was doing some more digging, I noticed that Wikipedia now has this interesting detail for insertion in the middle table on the linked list page:
For a singly linked list, isn't the search time going to be O(n)?
I guess the other way I can phrase my question is, why does the big O for a tree insertion include the operations needed to search for the insertion point and the pointer swaps while the big O for a linked only counts the pointer swaps, but not the search for the insertion point?
Any insight would help as to why this subject matter is taught this way would be helpful.
BTW, one of the links from Wikipedia article was a great read: Number crunching: Why you should never, ever, EVER use linked-list in your code again
This post has been edited by Skydiver: 09 August 2012 - 01:47 PM