No, to insert or remove an element you need to find its parents, all the way to the root node in the worst case. My multiset implementation doesn't store parent pointers, so this is instead done by recording the path on a stack when a node is found. It works fine as long as there's a good order function, which I consider to be the normal case.
If the order function doesn't order some values (or all in this case) then it can only be used to find the right set of unordered elements. Within that set the implementation has to do a linear search while the stack is kept updated appropriately.
/ Martin Stjernholm, Roxen IS
Previous text:
2003-01-30 18:21: Subject: Re: hybrid of array & list
Isn't inserting O(1) or at worst O(log n) if you have a pointer to the element you want to insert it after (or before)?
Finding element n is O(n), of course.
/ Mirar