# Difference between revisions of "TADM2E 3.14"

2. Insert: same as add, only now we have to add a new node too. To guaranty $O(n \log n)$ times we can use any balanced tree types, but the balancing step we have to take care of the sub tree sums. For example in AVL trees balancing operations are tree rotations. If P is the left child of Q, and we are doing a right rotation rooted at Q, than the left sub tree of P remains the same, while the left sub tree of Q will now be the original left sub tree of Q minus the left sub tree of P and P itself. The case of a left rotation is similar. Hence the left sub tree sum values can be maintained in $O(1)$ during rotation operations.