how do I calculate balance factor in AVL trees.

Thread Starter

Werapon Pat

Joined Jan 14, 2018
35
At first,I though I would make another method in class tree which will traverse to all node in the binary tree and calculate the balance factor and put
it into the variable. but I think this solution would not be efficiency because It needs to do this every time that I add another node into the tree.
do you have any solutions to recommend me. thanks a lot

i'm using python, here is my code.
Code:
class node:
    def __init__(self,n=None,l=None,r=None,v=0):
        self.data = n
        self.right = r
        self.left = l
        self.balance_factor = v
class tree:
    def __init__(self):
        self.root = None
    def add_node(self,v):
        if self.root == None:
            self.root = node(v)
        else:
            q = self.root
            while q:
                if v > q.data:
                    if q.right == None:
                        q.right = node(v)
                        break
                    else:
                        q=q.right
                else:
                    if q.left == None:
                        q.left = node(v)
                        break
                    else:
                        q=q.left
                print('is working')
    def inorder(self,q):
        if q == None:
            return
        self.inorder(q.left)
        print(q.data)
        self.inorder(q.right)
q = tree()
while True:
    i = input()
    if i=='1':
        g = int(input())
        q.add_node(g)
    else:
        break
q.inorder(q.root)
 

WBahn

Joined Mar 31, 2012
32,929
Calculating it each time would completely destroy the advantages of using an AVL tree in the first place.

Instead, add a variable to each node which stores the height of the tree rooted at that node. Then, whenever you need to know the balance factor of a node you simply use the definition of balance factor and the heights of its children. Whenever you modify the tree, you update the height of the nodes that are modified and since balancing the tree involves moving from the point of modification upward to the root, you will update the heights of all of the effected nodes in the process.
 
Top