class TreeNode:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
class AVLTree:
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert(self.root, val)
def _insert(self, node, val):
if not node:
return TreeNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
else:
return node
# 计算节点的平衡因子
balance = self._get_balance(node)
# LL型不平衡
if balance > 1 and val < node.left.val:
return self._rotate_right(node)
# RR型不平衡
if balance < -1 and val > node.right.val:
return self._rotate_left(node)
# LR型不平衡
if balance > 1 and val > node.left.val:
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
# RL型不平衡
if balance < -1 and val < node.right.val:
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
def _get_height(self, node):
if not node:
return -1
return 1 + max(self._get_height(node.left), self._get_height(node.right))
def _get_balance