平衡二叉树思路分析及实现(图解+代码同步实现)_二叉平衡排序树的需求分析

平衡二叉树思路分析及实现(图解+代码同步)

解剖

​ 需要明确的一点是 平衡二叉树本质就是二叉排序树只是它比二叉排序树多了一个性质:

任意节点左右子树的高度的绝对值之差 < = 1

​ 这是平衡的基础,必须记住! 下面是针对两大类(4种情况)下 插入节点导致不平衡的时所进行的平衡调整代码实现

---

图解

• 右单旋转 当前节点的左子树高度 - 右子数高度 > 1 且没有其他情况

​ 说明: 当插入节点3的时候 发生不平衡 ,根据特点需要进行右单旋转:

• 左单旋转 当前节点的右子树高度 - 左子树高度 且没有其他情况

注: 插入节点6 导致右子树不平衡 进行左旋转

• 左右双旋转 除了包括右单旋转的特点外, 且当前节点的左节点的左子树高度 < 当前节点的左节点 的右子树高度(即 当前节点的左节点是左单旋转的情况)

注: 插入节点 7 导致不平衡 同时 当前节点8 的左节点5 右子树比左子树高(注意这里不需要强调绝对值差<=1) 进行左右旋转

• 右左双旋转

注: 插入节点6 导致不平衡 对当前节点2的右节点7进行右旋转 然后对当前节点进行左旋转

代码

注: 由于平衡二叉树和二叉排序树的结构相同 所以我这里采用的代码就是上一期二叉排序树, 故建议先阅读我上一期的二叉排序树再来看这一篇

public class TreeNode implements Comparable<TreeNode>{

	//节点的权
	public int value;
	//左右节点
	public TreeNode left;
	public TreeNode right;
	
	public TreeNode(int value) {
		this.value = value;
	}
	
	public void setLeft(TreeNode left) {
		this.left = left;
	}
	
	public void setRight(TreeNode right) {
		this.right = right;
	}
	
	
	/**
	 * 返回当前节点高度
	 * @return
	 */
	public int height() {
		return Math.max(left == null ? 0 :left.height(), 
				right == null ? 0 : right.height()) + 1;
	}
	
	/**
	 * 获取指定节点高度
	 * @param node
	 * @return
	 */
	public int height(TreeNode node) {
		if (node == null)
			return 0;
		return node.height();
	}
	
	/**
	 * 插入一个节点
	 * @param node
	 */
	public void insert(TreeNode node) {
		if(node == null) return;
		int result = node.compareTo(this);
		
		if(result < 0) {
			 if(this.left == null){
				this.left = node;
			 } else {
				 this.left.insert(node);
			}
		} else {
			 if(this.right == null){
					this.right = node;
				 } else {
					 this.right.insert(node);
			}
		}
		
		//每次插入一个节点看看当前节点是否平衡  
		//左子树比右子数高  导致的不平衡  --->  右旋转   也叫左左插入
		if (height(this.left) - height(this.right) > 1) {
			//右旋转分为  单旋转    左右双旋转  
			if (height(this.left.left) - height(this.left.right) < 0) {
				//当前节点的左子节点进行  左旋转  注意此处不一定是不平衡导致的旋转  而是整体上这没有办法进行简单的单旋转 故需要这个中间操作
				this.left.leftSpin();
				rightSpin();
			} else {
				rightSpin();
			}
			
		//右子数比左子树高 导致的不平衡 --> 左旋转 也叫右右插入
		} else if (height(this.right) - height(this.left) > 1) {
			//左旋转也分为  单旋转 和右左双旋转
			if(height(this.right.right) - height(this.right.left) < 0 ) {
				//中间操作
				this.right.rightSpin();
				leftSpin();
			} else {
				leftSpin();
			}
		}
	
	}
	
	/**
	 * 左旋转 : 右旋转的逆过程
	 */
	private void leftSpin() {
		TreeNode node = new TreeNode(this.value);
		node.left = this.left;
		node.right = this.right.left;
		this.value = this.right.value;
		this.right = this.right.right;
		this.left = node;
	}

	
	/**
	 * 右旋转
	 */
	private void rightSpin() {
		//创建一个节点, 值等于当前节点值  因为当前节点是不平衡的
		TreeNode node = new TreeNode(this.value);
		//让创建的节点的右子树指向 当前节点的右子树
		node.right = this.right;
		//将创建节点的左子树指向 当前节点的左子树的右子树
		//if(this.left.right != null)
		node.left = this.left.right;
		//将当前节点的值 替换为 其左节点的值
		this.value = this.left.value;
		//干掉当前节点的左节点(注意不是左子树)
		this.left = this.left.left;
		//让当前节点的右子树 指向那个创建好的节点
		this.right = node;
	}

	@Override
	public int compareTo(TreeNode o) {
		if(o == null) throw new NullPointerException("比较的节点为空!");
		return this.value - o.value;
    }	
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

测试

注:这里提供不同情况的数据 方便大家进行测试 插入节点的次序可以调整 只要符合你想要测试的情况即可

public static void main(String[] args) {
		BinarySortTree tree = new BinarySortTree();
	
		//左旋转: int[] arr = new int[] {2, 1, 4,3,5,6};
		//左右双旋转: int[] arr = new int[] {8, 9 , 5 , 4 ,6,7};
		//右左双旋转: int[] arr = new int[] {5, 3, 6 , 2, 7, 4};
		//右旋转: 
		int[] arr = new int[]{6, 7, 5, 4, 3};
		for (int i = 0; i < arr.length; i++) {
			tree.insert(new TreeNode(arr[i]));
		}
		
		System.out.println(tree.root.height(tree.root));
		//tree.insert(new TreeNode(16));
	/*	tree.insert(new TreeNode(1));
		tree.insert(new TreeNode(0));
		tree.insert(new TreeNode(-1));*/
		System.out.println(tree.root.value);
		
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

总结

​ 二叉平衡树关键在于平衡的调整策略, 把握代码中两个方法leftSpin()和rightSpin()再加上我上一篇的二叉排序树 基本可以搞定二叉排序树
 最近手撸数据结构有点上瘾, 继续肝, 敬请期待哦…