Self Balancing Trees| Balanced Trees
Task(medium)
An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
We define balance factor for each node as :
balanceFactor = height(left subtree) - height(right subtree)
The balance factor of any node of an AVL tree is in the integer range [-1,+1]. If after any modification in the tree, the balance factor becomes less than −1 or greater than +1, the subtree rooted at this node is unbalanced, and a rotation is needed.
You are given a pointer to the root of an AVL tree. You need to insert a value into this tree and perform the necessary rotations to ensure that it remains balanced.
Input Format
You are given a function,
node *insert(node * root,int new_val)
{
}
'node' is defined as:
struct node
{
int val; //value
struct node* left; //left child
struct node* right; //right child
int ht; //height of the node
} node;
You only need to complete the function.
Note: All the values in the tree will be distinct. Height of a Null node is -1 and the height of the leaf node is 0.
Output Format
Insert the new value into the tree and return a pointer to the root of the tree. Ensure that the tree remains balanced.
Sample Input
3
/ \
2 4
\
5
The value to be inserted is 6.
Sample Output
3
/ \
2 5
/ \
4 6
SOLUTION 1
import sys
lines = []
for line in sys.stdin:
if 'Exit' == line.rstrip():
break
lines.append(line.split('\n')[0])
nol = lines[0]
treeInput = [int(x) for x in lines[1].split(' ')]
toIns = lines[2]
# print(nol)
# print(treeInput)
# print(toIns)
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1 # Initially, new nodes have height 1
class AVLTree:
def __init__(self):
self.root = None
# Insertion operation - Add your code here
def insert(self,data):
self.root=insertnew(self.root,data)
# Traversals
def inorder(self, node):
if node is not None:
self.inorder(node.left)
print(f"{node.data}(BF={getBalance(node)})", end=" ")
self.inorder(node.right)
def postorder(self, node):
if node is not None:
print(f"{node.data}(BF={getBalance(node)})", end=" ")
self.postorder(node.left)
self.postorder(node.right)
# Function to print BF at each node
def print_balance(self):
self.inorder(self.root)
print("")
self.postorder(self.root)
def insertnew(root,data):
if root is None:
return Node(data)
if root.data<data:
root.right=insertnew(root.right,data)
if root.data>data:
root.left=insertnew(root.left,data)
root.height=1+max(getheight(root.left),getheight(root.right))
# left left case
if getBalance(root)>1 and data<root.left.data:
return rotateright(root)
# right right case
if getBalance(root)<-1 and data>root.right.data:
return rotateleft(root
# left right case
if getBalance(root)>1 and root.left.data<data:
root.left=rotateleft(root.left)
return rotateright(root)
# right left case
if getBalance(root)<-1 and root.right.data>data:
root.right=rotateright(root.right)
return rotateleft(root)
return root
def getheight(root):
if root is None:
return 0
return root.height
def getBalance(root):
if root is None:
return 0
return (getheight(root.left)-getheight(root.right))
def rotateleft(root):
y=root.right
T2=y.left
# perform rotation
y.left=root
root.right=T2
root.height=1+max(getheight(root.left),getheight(root.right))
y.height=1+max(getheight(y.left),getheight(y.right))
return y
def rotateright(root):
y=root.left
T3=y.right
# perform rotation
y.right=root
root.left=T3
root.height=1+max(getheight(root.left),getheight(root.right))
y.height=1+max(getheight(y.left),getheight(y.right))
return y
tree = AVLTree()
for x in treeInput:
tree.insert(x)
tree.insert(int(toIns))
tree.print_balance()
