AVL树

定义

AVL树是一棵自平衡的二叉搜索树。

AVL树具有以下性质:

• 根的左右子树的高度之差的绝对值不能超过1
• 根的左右子树都是平衡二叉树

插入

• 插入一个节点可能会破坏AVL树的平衡,可以通过旋转操作来进行修正。
• 插入一个节点后,只有从插入节点到根节点的路径上的节点的平衡可能 被改变。我们需要找出第一个破坏了平衡条件的节点,称之为K。K的两 颗子树的高度差2。

• 不平衡的出现可能有4种情况 *

  <figure><img src="../../.gitbook/assets/image (2) (1).png" alt=""><figcaption></figcaption></figure>
  

  *

  <figure><img src="../../.gitbook/assets/image (1) (1).png" alt=""><figcaption></figcaption></figure>
  

*

  <figure><img src="../../.gitbook/assets/image (3) (1).png" alt=""><figcaption></figcaption></figure>

*

  <figure><img src="../../.gitbook/assets/image (4).png" alt=""><figcaption></figcaption></figure>