🎯 Mục tiêu

• Hiểu vì sao cần cây cân bằng (độ cao log n).
• Biết các phép quay trong AVL: quay trái, quay phải.

📘 Giới thiệu

Trong BST thường, nếu thêm theo thứ tự tăng dần → cây lệch hẳn sang phải. AVL Tree tự động quay lại để cân bằng chiều cao 2 nhánh (chênh lệch ≤ 1).

💻 Minh họa Python

# AVL cơ bản
class Node:
  def __init__(self,v): self.val=v;self.h=1;self.left=self.right=None
def h(n):return n.h if n else 0
def bal(n):return h(n.left)-h(n.right) if n else 0
def rotR(y):
  x=y.left;T=x.right;x.right=y;y.left=T
  y.h=max(h(y.left),h(y.right))+1
  x.h=max(h(x.left),h(x.right))+1
  return x
def rotL(x):
  y=x.right;T=y.left;y.left=x;x.right=T
  x.h=max(h(x.left),h(x.right))+1
  y.h=max(h(y.left),h(y.right))+1
  return y
def insert(node,v):
  if not node:return Node(v)
  if vnode.val: node.right=insert(node.right,v)
  else:return node
  node.h=max(h(node.left),h(node.right))+1
  b=bal(node)
  if b>1 and vnode.right.val:return rotL(node)
  if b>1 and v>node.left.val:node.left=rotL(node.left);return rotR(node)
  if b<-1 and v

# sau khi chèn 25, cây sẽ quay trái-phải tại 20 để cân bằng