平衡二叉树-AVL树(LL、RR、LR、RL旋转)

时间:2023-07-16 11:04:14

平衡二叉树的定义:

  任意的左右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,二叉平衡树前提是一个二叉排序树。

平衡二叉树的插入:

  二叉平衡树在插入或删除一个结点时,先检查该操作是否导致了树的不平衡,若是,则在该路径上查找最小的不平衡树,调节其平衡。

  4种平衡调整如下(结点的数字仅作标记作用):

  ①LL:右单旋转

  平衡二叉树-AVL树(LL、RR、LR、RL旋转)

  ②RR:左单旋转

  平衡二叉树-AVL树(LL、RR、LR、RL旋转)

  ③LR平衡旋转:先左后右

  平衡二叉树-AVL树(LL、RR、LR、RL旋转)

  ④RL平衡旋转:先右后左

  平衡二叉树-AVL树(LL、RR、LR、RL旋转)

平衡二叉树查找:平衡二叉树查找过程等同于二叉排序树相同,因此平衡二叉树查找长度不超过数的长度,及其平均查找长度为O(log2n)。