Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def getHeight(root):
- if not root:
- return 0
- return root.height
- def getBalance(root):
- if not root:
- return 0
- return getHeight(root.left) - getHeight(root.right)
- def leftRotate(root):
- right_son = root.right
- T2 = right_son.left
- right_son.left = root
- root.right = T2
- root.height = 1 + max(getHeight(root.left),
- getHeight(root.right))
- right_son.height = 1 + max(getHeight(right_son.left),
- getHeight(right_son.right))
- return right_son
- def rightRotate(root):
- left_son = root.left
- T3 = left_son.right
- left_son.right = root
- root.left = T3
- root.height = 1 + max(getHeight(root.left),
- getHeight(root.right))
- root.height = 1 + max(getHeight(left_son.left),
- getHeight(left_son.right))
- return left_son
- def insert(val, root):
- if not root:
- return Node(val)
- elif val < root.val:
- root.left = insert(val, root.left)
- else:
- root.right = insert(val, root.right)
- root.height = 1 + max(getHeight(root.left),
- getHeight(root.right))
- balance = getBalance(root)
- if balance > 1 and val < root.left.val:
- return rightRotate(root)
- if balance < -1 and val > root.right.val:
- return leftRotate(root)
- if balance > 1 and val > root.left.val:
- root.left = leftRotate(root.left)
- return rightRotate(root)
- if balance < -1 and val < root.right.val:
- root.right = rightRotate(root.right)
- return leftRotate(root)
- return root
Add Comment
Please, Sign In to add comment