Should I balance my AVL trees top-down or bottom-up?

Viewed 238

not particular to any language, but ill show some code in python i had

def insert(self,i):
    temp = self
    while(True):
      if i > temp.V:
        if temp.R == None:
          temp.R = node(None,None,i)
          temp = temp.R
          break
        else:
          temp = temp.R

      else:
        if temp.L == None:
          temp.L = node(None,None,i)
          temp = temp.L
          break
        else:
          temp = temp.L

    self = self.balance()

and for class node

def __init__(self,left,right,val):
    self.L = left
    self.R = right
    self.V = val

with top to bottom method both the insertion and the balancing are separate functions, which I guess would be good from like an abstraction perspective?? It also allows me to do insertion iteratively [and iteration is faster than recursion is what i have been taught]

meanwhile bottom to top method does the balancing in [presumably less] operations, but also needs to be bundled with the insertion to work. It also means i have to insert elements recursively which is more costly than iteration.

Please correct me if my reasoning is wrong, because to me both seem like decent approaches.

Also, I had this example where I think a top down approach would be preferable over a bottom up one.

I was told a top down approach will be slower than a bottom up one, but I cant find any proof for or against this.

1 Answers

The disadvantage of the top-down approach, is that you cannot rely on the balance information that is stored in an AVL node (-1, 0 or 1), since it doesn't reflect the effect of the latest insertion -- only the inserted node got up-to-date balance information which was not bubbled up (yet). So that means a call to the balance function (which doesn't take any argument) will need to scan the whole tree! So this would represent O(n) time complexity.

The bottom up approach will only have to look at (some) ancestors of the inserted node, which will get their balance information updated if needed, potentially after applying a rotation. This will have a O(logn) time complexity.

Related