下图所示的树是AVL树,但是,需要在A
的左子树的左侧插入一个元素。树可能会因关键节点A
的存在而变得不平衡。
平衡因子不在-1
和1
之间的节点称为关键节点。要重新平衡树,执行LL
旋转,如下图所示。
节点B
成为根,A
和T3
作为其左右子节点。 T1
和T2
成为A
的左右子树。
示例:
将值为12
的节点插入下图所示的树中。
解决:12
将被插入25
的左侧,因此,它扰乱了AVL树的平衡。 树需要通过LL旋转旋转来重新平衡。
这里,关键节点100
将移动到其右侧,并且其左子树(B)的根将是树的新根节点。
B
的右子树,即T2
(具有根节点75
)将位于节点A
的左侧(值为100
)。
通过遵循此过程,树将被重新平衡,因此,它将是在插入12
之后生成的AVL树。