Live a balanced life… or less.

General Properties

  • 比红黑树更加平衡(意味着更短的查找时间)
  • 使用“平衡因子”来维持树的平衡(红黑树:涂色)

Balance Factor?

  • equals height(rchild) - height(lchild)
  • 根据AVL树的要求,它的值应该为{-1,0,1} 中的一种
  • 实际上不需要保存每个节点对应子树高度值,只需要在每次操作之后更新它

Operations!

Needless to describe.

Insertion

可以直接按照一般二叉树执行插入。

插入后,由新插入的节点一路向上更新平衡因子并做旋转以平衡二叉树。

Deletion

hmmm, mostly the same as Insertion.

But instead of increasing height, now decreasing.

Rotation & Rebalancing

插入/删除操作递归返回时,需要更新平衡因子并将不平衡的部分进行旋转,以重新使树达到平衡状态。

在一个节点完成更新后,总共会出现四种需要旋转的情况:

  1. rchild递归返回,且rchildlchild不是heavy的(即 balance factor>=0
  2. lchild递归返回,且lchildrchild不是heavy的(即balance factor<=0
  3. rchild递归返回,且rchildlchildheavy
  4. lchild递归返回,且lchildrchildheavy

情况 (1) (2) 仅需要一次旋转操作(SimpleLeftRotate() & SimpleRightRotate())

情况 (3) (4) 需要两次旋转操作:RightLeftRotate() & LeftRightRotate()

SimpleLeftRotate

  • rchild成为新的根结点
  • rchildlchild成为原来根结点的rchild
  • 原来根结点成为rchildlchild

SimpleRightRotate

  • lchild成为新的根结点
  • lchildrchild成为原来根结点的lchild
  • 原来根结点成为lchildrchild

RightLeftRotate

  1. 对根的rchildSimpleRightRotate
  2. 对根做SimpleLeftRotate

LeftRightRotate

  1. 对根的lchildSimpleLeftRotate
  2. 对根做SimpleRightRotate