算法 #

平衡二叉树（AVL） #

定义：一个二叉搜索树，任意节点的左右子树高度差不超过1。

搜索效率：O(log(n))

平衡因子（BF） #

定义：左右子树高度差，BF>1表示左右不平衡。

BF>1 情况下的构型与对应旋转操作：

• LL型：右旋
• LR型：先左旋再右旋
• RR型：左旋
• RL型：先右旋再左旋

右旋操作示意图 #

B
   / \
  A   Z
 / \
X   Y

旋转后：

  A
 / \
X   B
   / \
  Y   Z