潜析AVL树–AVL树的双旋转

潜析AVL树–AVL树的双旋转 接上篇博文:简析AVL树–AVL树的概念及单旋转 AVL树如何恢复平衡之双旋转 首先假设我们有一颗已经处于平衡的AVL树: 上篇博文已经解决了LL和RR两种情况的平衡恢复解决方案—-单旋转。这篇博文来看双旋转情形。这时候我们插入结点7,我们可以发现这时这棵树并没有失去平衡: 但是,如果我们继续插入结点8,这棵树就会再次处于失衡状态: 我们首先可以发现结点9左右子树高度差2—这是第一个失衡的结点。 然后我们可以发现结点6左右子树高度差2—这是第二个失衡的结点。 最后发现根节点3也失衡了—它的左右子树高度同样差2。 我们首先从离插入的结点8最近的结点9开始处理