The path is necessary to rebalance the tree. In this particular case, a tree isn't really what one wants though; a doubly linked list would be better. Even if the tree is replaced with that, I don't think it would be too hard to make it possible to reuse the allocation and gc routines, but I suspect there currently are cases where they'll get upset if it isn't a sufficiently balanced tree (at least if you run with debug turned on).
/ Martin Stjernholm, Roxen IS
Previous text:
2003-01-30 18:41: Subject: Re: hybrid of array & list
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