AVL树的初步了解
麦兜 / 2019-11-03 / 数据结构 / 阅读量 232

平衡二叉树(AVL树)

空树或者,任意左右子树高度差的绝对值不超过1,|BF(1)|<=1

平衡二叉树调整

因“破坏者”的插入导致某个结点(发现者)不平衡所以需要相对应的旋转,才能达到平衡。

右单旋转


右单旋转.png

不平衡的“发现者” 是1号,破坏平衡结点的是3号。3号在“发现者”的左子树的左边,因LL插入,需要(右单旋转)

左单旋转

左单旋转.png

“发现者” 为1号 “破坏者”为3号,3号在“发现者”的右子树的右边。因RR插入,需要(左单旋转)

LR旋转

LR.png

    “破坏者”在“发现者”的左子树的右边所以需要LR旋转(先左后右旋转)。

RL旋转

RL.png

  “破坏者”在“发现者”的右子树的左边所以需要RL旋转(先右后左旋转)。

核心代码清单

1 + 2 =
快来做第一个评论的人吧~