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.原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点。
共有 0 条评论