def
height(self): if [Link](): return(0) else: return 1 + max([Link](), [Link]())def
update_height(self): [Link] = 1 + max([Link], [Link])def slope(self): return
[Link] - [Link] def rebalance(self): if [Link]() in (-1, 0, 1): return elif [Link]()
>=
2: if [Link]() < 0: [Link]() [Link].update_height() self.update_height() [Link]
trotate() [Link].update_height() [Link].update_height() self.update_height() [Link](
) [Link].update_height() self.update_height() else: [Link]() self.update_height() elif
[Link]() <=
2: if [Link]() > 0: [Link]() [Link].update_height() self.update_height() [Link]
ate() [Link].update_height() [Link].update_height() [Link]()
class AVLTree:
# Constructor:
def __init__(self, initval=None):
[Link] = initval
if [Link]:
[Link] = AVLTree()
[Link] = AVLTree()
[Link] = 1
else:
[Link] = None
[Link] = None
[Link] = 0
return
def isempty(self):
return ([Link] == None)
def isleaf(self):
return ([Link] != None and [Link]() and [Link]())
def leftrotate(self):
v = [Link]
vr = [Link]
tl = [Link]
trl = [Link]
trr = [Link]
newleft = AVLTree(v)
[Link] = tl
[Link] = trl
[Link] = vr
[Link] = trr
[Link] = newleft
return
def rightrotate(self):
v = [Link]
vl = [Link]
tll = [Link]
tlr = [Link]
tr = [Link]
newright = AVLTree(v)
[Link] = tlr
[Link] = tr
[Link] = newright
[Link] = vl
[Link] = tll
return
def insert(self, v):
if [Link]():
[Link] = v
[Link] = AVLTree()
[Link] = AVLTree()
[Link] = 1
elif v < [Link]:
[Link](v)
else:
[Link](v)
# Update height of the current node
[Link] = max([Link], [Link]) + 1
# Calculate balance factor
balance = [Link] - [Link]
# Left heavy
if balance > 1:
if v < [Link]:
# Right rotation
left_child = [Link]
[Link] = left_child.left
left_child.left = [Link]
[Link] = left_child
[Link], [Link] = [Link], [Link]
else:
# Left-Right rotation
left_child = [Link]
[Link] = left_child.right
left_child.right = [Link]
[Link] = left_child
left_grand_child = [Link]
[Link] = left_grand_child.right
left_grand_child.right = [Link]
[Link] = left_grand_child
[Link], [Link] = [Link], [Link]
# Right heavy
if balance < -1:
if v > [Link]:
# Left rotation
right_child = [Link]
[Link] = right_child.right
right_child.right = [Link]
[Link] = right_child
[Link], [Link] = [Link], [Link]
else:
# Right-Left rotation
right_child = [Link]
[Link] = right_child.left
right_child.left = [Link]
[Link] = right_child
right_grand_child = [Link]
[Link] = right_grand_child.left
right_grand_child.left = [Link]
[Link] = right_grand_child
[Link], [Link] = [Link], [Link]
def inorder(self):
if [Link]():
return([])
else:
return([Link]() + [[Link]] + [Link]())
def preorder(self):
if [Link]():
return([])
else:
return([[Link]] + [Link]() + [Link]())
def postorder(self):
if [Link]():
return([])
else:
return([Link]() + [Link]() + [[Link]])
A = AVLTree()
nodes = eval(input())
for i in nodes:
[Link](i)
print([Link]())
print([Link]())
print([Link]())