排序树与平衡二叉树讲解---新手超级易懂 (2)

​  举个例子,像上图是否平衡二叉树的图里面,左图在没插入前”19“节点前,该树还是平衡二叉树,但是在插入”19“后,导致了”15“的左右子树失去了”平衡“,所以此时可以将”15“节点进行左旋,让”15“自身把节点出让给”17“作为”17“的左树,使得”17“节点左右子树平衡,而”15“节点没有子树,左右也平衡了。如下图,

排序树与平衡二叉树讲解---新手超级易懂

  由于在构建平衡二叉树的时候,当有新节点插入时,都会判断插入后时候平衡,这说明了插入新节点前,都是平衡的,也即高度差绝对值不会超过1。当新节点插入后,有可能会有导致树不平衡,这时候就需要进行调整,而可能出现的情况就有4种,分别称作左左,左右,右左,右右。

左左:

排序树与平衡二叉树讲解---新手超级易懂

  左左即为在原来平衡的二叉树上,在节点的左子树的左子树下,有新节点插入,导致节点的左右子树的高度差为2,如上即为”10“节点的左子树”7“,的左子树”4“,插入了节点”5“或”3“导致失衡。

​  左左调整其实比较简单,只需要对节点进行右旋即可,如下图,对节点”10“进行右旋,

  注意:如果对左右旋变换还不是很懂或不是很熟练的,可以对照着前面的那两个动图去想象,自己动手变换几次,就明白了。

排序树与平衡二叉树讲解---新手超级易懂

左右:

排序树与平衡二叉树讲解---新手超级易懂

  左右即为在原来平衡的二叉树上,在节点的左子树的右子树下,有新节点插入,导致节点的左右子树的高度差为2,如上即为”11“节点的左子树”7“,的右子树”9“,插入了节点”10“或”8“导致失衡。

  左右的调整就不能像左左一样,进行一次旋转就完成调整。我们不妨先试着让左右像左左一样对”11“节点进行右旋,结果图如下,右图的二叉树依然不平衡,而右图就是接下来要讲的右左,即左右跟右左互为镜像,左左跟右右也互为镜像。

排序树与平衡二叉树讲解---新手超级易懂

  右右跟左左一样,只需要旋转一次就能把树调整平衡,而左右跟右左也一样,都要进行旋转两次才能把树调整平衡,所以,首先上图的这种调整是错误的,正确的调整方式是,将左右进行第一次旋转,将左右先调整成左左,然后再对左左进行调整,从而使得二叉树平衡。

​  即先对上图的节点”7“进行左旋,使得二叉树变成了左左,之后再对”11“节点进行右旋,此时二叉树就调整完成,如下图,

排序树与平衡二叉树讲解---新手超级易懂

右左:

排序树与平衡二叉树讲解---新手超级易懂

​  右左即为在原来平衡的二叉树上,在节点的右子树的左子树下,有新节点插入,导致节点的左右子树的高度差为2,如上即为”11“节点的右子树”15“,的左子树”13“,插入了节点”12“或”14“导致失衡。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwzffy.html