0

I have a balanced AVL tree with integer values and a segment [L, R].
I would like to remove all the nodes with values from this range and rebalance the tree, so that the remaining nodes would form a balanced AVL tree.

What would be the computational complexity of this operation?

kichatos
  • 13
  • 2
  • `(R-L)*O(logN) + K*O(logN)`? i.e. `R-L` times searching and deleting K times, where K is number of nodes found. – Giorgi Nakeuri Apr 13 '16 at 19:25
  • @GiorgiNakeuri This would be the naive approach. I'm looking for a solution with the worst-case complexity depending only on the number of elements in the tree for any given range. – kichatos Apr 13 '16 at 19:51

1 Answers1

1

Split and join in AVL trees is O(log n), when done carefully. Your operation can be done with two splits and one join, plus the cost to destruct all of the values from L to R, if you want to call their finalizers/destructors. The total cost is thus O(log n) or O(log n + k), depending on whether you call the destructors.

I won't go over split/join for AVL trees, since it's mostly just a bunch of boring case analysis, like insert and delete are. However, I did that elaboration a few years ago for red-black trees.

Community
  • 1
  • 1
jbapple
  • 3,297
  • 1
  • 24
  • 38