R
R
Rabinzon2015-01-01 13:37:24
Python
Rabinzon, 2015-01-01 13:37:24

How to recalculate heights in avl tree?

When adding a new node, I calculate the heights like this:

def setHg(self,current):
      current.height += 1
      if(current.parent != None):
         self.setHg(current.parent)

After the turn, I do not know how to correctly recalculate the height.
for example
(root: 1, height: 3) -> (2, h: 2) -> (3, h: 1)

twisted
(1, h: 3) <- (root : 2, h: 2) -> (3, h: 1)

Stuck on this. Help me please.

Answer the question

In order to leave comments, you need to log in

1 answer(s)
D
Duha666, 2015-01-01
@Duha666

So recalculate the height on each type of turn separately.
Using the small left example from the wiki:
The height of a is now max(L, C) + 1, where max is the height.
Height b - max(a, R)

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question