Java – 数据结构 – 平衡二叉树

简介

平衡二叉树的规则是,任意节点左右子树高度差不超过1,比如以下这两种情况,就是平衡二叉树,对于破坏了平衡的二叉树来说,可以通过旋转的方式使其回来平衡状态。

平衡二叉树图例一

平衡二叉树图例一

平衡二叉树图例二

平衡二叉树图例二

 

二叉树旋转

二叉树旋转是指当添加一个节点之后,该树不再是一颗平衡二叉树,旋转机制分为左旋和右旋两种。

 

左左节点

左左节点是指,当一个二叉树的根节点的左节点的左节点出现新的元素时,平衡被打破,此时我们要通过旋转使其变得平衡的过程。

解析:

2->1 因为右边没有节点,为一层

4->1 因为右边没有节点,为两层,此为旋转节点

10->1 因为左右都没有节点,为两层

旋转步骤:

1.以不平衡的点作为支点

2.把支点右旋降级,变成右子节点

3.晋升原来的左子节点

 

假设我们4其下左右都有节点时,如下图

解析:

2->1 因为右边没有节点,为一层

5->1 因为左右都没有节点,为一层

4->1 因为左右都有节点,为一层

7->1 因为左右都有节点,要看10节点

10->1 因为左右都没有节点,与1节点相差两层(4-2=2),根节点被设定为 7

旋转步骤:

1.以不平衡的点作为支点

2.就是将根节点的左侧往右拉

3.原先的左子节点变成新的父节点,并把多余的右子节点出让,给已经降级的根节点当左子节点。

 

 

 

 

左右节点

左右节点是指,当一个二叉树的根节点的左节点的右节点出现新的元素时,平衡被打破,此时我们要通过旋转使其变得平衡的过程。

解析:

5->6 因为5左边没有节点,为一层

4->6 因为4左右都有节点,为一层

7->6 因为7左右都有节点,要看10节点

10->6 因为10左右都没有节点,与6节点相隔两层,所以按道理来说,7应该是右旋的节点

 

当我们在7节点进行右旋后,我们发现了问题:

我们对7节点右旋后发现,节点2->6,依然还是相隔两层,平衡依然没有改变,所以我们不应该马上右旋,而是先局部进行左旋,再进行最后的右旋:

 

总结:先局部左旋,再整体右旋。

 

 

右左节点

右左节点是指,当一个二叉树的根节点的右节点的左节点出现新的元素时,平衡被打破,此时我们要通过旋转使其变得平衡的过程。

解析:

9->8 因为9节点没有右节点,为一层

10->8 因为10节点左右都有节点,为一层

11->8 因为11节点左右都没有节点,为一层

7->8 因为7节点左右都有节点,所以要看4节点

4->8 因为4节点左右都没有节点,所以相隔了两层,以7节点为中心

 

但与左右旋转一样,直接进行左旋,依然无法解决平衡问题

所以我们不应该马上右旋,而是先局部进行右旋,再进行最后的整体左旋:

 

总结:先局部右旋,再整体左旋。

 

右右节点

右右节点是指,当一个二叉树的根节点的右节点的右节点出现新的元素时,平衡被打破,此时我们要通过旋转使其变得平衡的过程。

解析:

11->12 因左边没有节点,可以看作和 12 有一层

10->12 因左边没有节点,可以看作和 12 有两层

4->12 因左右都没有节点,可以看作和 12 有两层

7->12 因左右都有节点,所以7的层数应从4或10开始计算,可以看作和12有两层

结果:因为存在两层相隔,打破了平衡,此时需要左旋节点使得树变得平衡。

旋转步骤:

1.确定支点,从添加的节点开始,不断的往父节点找不平衡的节点

2.以不平衡的点作为支点

3.把支点左旋降级,变成左子节点

4.晋升原来的右子节点

 

假设,我们在10节点中,还包含一个左节点的情况下,要如何左旋呢

此时

11->12 为一层

9->12 为一层

10-12 因为10下左右都有节点,所以从9处算起,为一层

4->12 因为左右都没有节点,所以到12相隔了两层(12在4层,4在2层,4-2=2),打破了平衡

左旋步骤

我们应该以 7 作为节点进行左移,把7 移下来,10移上去,原来的9节点,会接到7节点去

1.以不平衡的点作为支点

2.将根节点的右侧往左拉

3.原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点。

 

 

 

 

 

 

 

如果您喜欢本站,点击这儿不花一分钱捐赠本站

这些信息可能会帮助到你: 下载帮助 | 报毒说明 | 进站必看

修改版本安卓软件,加群提示为修改者自留,非本站信息,注意鉴别

THE END
分享
二维码
打赏
海报
Java – 数据结构 – 平衡二叉树
简介 平衡二叉树的规则是,任意节点左右子树高度差不超过1,比如以下这两种情况,就是平衡二叉树,对于破坏了平衡的二叉树来说,可以通过旋转的方式使其回来平衡状态。 平衡二叉树图例一 平衡……
<<上一篇
下一篇>>