Hey Y'all,
Ultimately what I'm trying to do is avoid using binary trees.
At Uni, when trees came along, I was able to quickly understand the population and the traversal of one.
Alas, for the life of me, I could never understand the balancing of a tree. Well, the balancing I understood, but the implementation of it, NOPE!
And if I want to do a proper hash map class, the best way to implement such a thing is on the back of a binary tree, a balanced binary tree!!!
So, I know how to do a binary search on an ordered array that will land me an OLog N. But then I have an ON for the array insertion, ARGH!!
If I do linked lists, I cannot implement a binary search since I have no indexes, and no way to quickly get at the middle element of a sub set of a linked list. So whatever algo i use for search, would always be ON, but I would have O1 in the insertion. ARGHHHH!!!
If only the insertion of the array could be optimized out of ON, that would be GRAND!!
Either that, or I'll have to copy/paste some binary tree balancing code that I really don't understand and for me that's a tad unacceptable!
Cheers,
Gus