CODEWITHSUNDEEP
algorithmdata-structurestree
kakkarot
kakkarot

Reputation: 508

What is the exact definition of a Weight balanced tree?

There are many definitions given for a weight balanced tree. I got confused which one to follow and it is difficult to understand the definitions given.

A node is balanced if weight[n.left] ≥ weight[n] and weight[n.right] ≥ weight[n]

Number of nodes in the left and right sub tree must be equal

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree.

Can somebody explain me which is the correct one?

Upvotes: 2

Views: 4706

Answers (1)

rst
rst

Reputation: 2724

As I learnt it, the balance p() of a node n in a wbt is given by 

p(n) = s(n.l)/s(n) = 1 - s(n.r)/s(n)

where s is the number of descendant leaves. You can now start to rebalance the tree by using rotation and double-rotation operations. Now, if you have a even number of leaves, then the statement is true that for each node, the number of subnodes in the left and in the right node is equal. That holds only for balanced wbt. That is not always possible, if you have 6 leaves, how do you balance that so that that statement holds?

Rebalancing reduces the height of a wbt.

Example: you have a wbt with one million leaves in the left node and a couple ones in the right node. You can now start to rotate the leaves so that the number of leaves in the left sub tree is

at least half and at most twice the number of nodes in the right sub tree

One statement is:

The tree is of bounded balance a if for every node

a <= p(n) <= 1-a

Upvotes: 2

Related Questions