From: Brian Hurt <bhurt@sp...>  20040823 22:55:09

On Mon, 23 Aug 2004, Bardur Arantsson wrote: > I have a gut feeling it might be possible if the balancing > constraints are relaxed and we look at amortized cost > instead of worstcase case cost. But if not really sure it > can be done if you always require your trees to be > balanced. Anyway, your example of delete shows that it's > different enough from existing structures to be useful. I'm actually having thoughts here. To remove any contiguous subrange of length N, you need to remove O(log N) subtrees. The key op to removing a subrange fast is the removal of subtrees fast. Consider the following situation, you have a tree that looks like: A / \ / \ B C / \ / \ ... D E / \ / \ ... ... You want to delete E and it's entire subtree. Now, normally, you'd end up with a tree like this: A / \ / \ B C / \ / ... D / \ ... Which is horribly unbalanced. Instead, what you can do is delete C as well, so you end up with a tree like: A / \ / \ B D / \ / \ ... ... You then need to balance the tree, starting at A and working up, and reinsert C. OK, it's a weight balanced tree, so the weight of B is less than 2x the weight of the original C subtree. Call C 1/2 the weight of B, worst case. Now, assume that E is 2x the weight of D this means D is 1/3rd the weight of C, or 1/6th the weight of B. But when you do a rotate right, B gives up it's right child. Assume B's right child is 1/2 the weight of it's left child, or 1/3rd the total weight of B. So after the rotate, B's left child will be 2/3rds the original weight of B, and B's right child (now A) will be 1/3 + 1/6 the weight of B, or 1/2 the weight of B. And Balancing constraints are maintained. Ah, here's where the balancing constraint can get violated. Assume B's right child is the heavy child, 2x the weight of B's left child, or 2/3rds the total weight of B. Then when we rotate, we move too many children over. No. In this case you only need to rotate B left before rotating the entire structure right to rebalance. Worst case you need to do two rotates and one reinsertion to rebalance the whole subtree. Humorously, the reinsertion is the expensive part, at O(log N). Deleting M elements from an N element tree is then O((log N) * (log M)). Another thought: appending and prepending one funcarr to another should be an O(log N) operation. I walk down the left or right subtree of the larger tree until I hit node with about the same weight as the smaller tree. I then do a join of those two trees, and rebalance as I walk back up. Inserting is a little bit more tricky, as I can't swap appending and prepending. Might still be doable cheaply.  "Usenet is like a herd of performing elephants with diarrhea  massive, difficult to redirect, aweinspiring, entertaining, and a source of mindboggling amounts of excrement when you least expect it."  Gene Spafford Brian 