ARTS 第9周

发表于

ARTS （第9周）

开篇词

学而时习之，不亦乐乎。

温故而知新。

这几天抽空看了之前写的专栏文章，发现了一些之前的遗漏和一些引申的思考，所以在此，我写出了上面2句话。

本周：

红黑树(未完成)

Algorithm 算法

红黑树部分结构和算法（删除部分暂未完善）

红黑树（Red Black Tree） 是一种自平衡二叉查找树，其实红黑树的结构并不能完全符合平衡二叉树。

因为极端情况下，红黑树的某个最长分支可能会比最短的分支长一倍，但最多也就是一倍，这不是不可接受的，并且红黑树产生变化（即新增、删除）之后的平衡操作的时间复杂度并不高，再加上二叉树本身的高效的查找，因此红黑树的性能十分稳定。

而一些完全符合平衡二叉树定义的树，在平衡操作上所花的复杂度要比红黑树大得多。

红黑树的核心思路就是

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的颜色：节点有红色和黑色，并且是可以进行改变的。

红黑树的左旋、右旋：

也就是我这里说写的rotateleft和rotateright方法。

需要把该节点的父节点指向该节点的子节点，然后把子节点的一条腿接到该节点上。

并且左旋/右旋有一个很重要的特性，就是进行旋转之后，树的结构还是符合二叉树结构的要求的。

所以，我在这里就猜想作者的最初设计思路，

应该是想设计一个红黑树这样的有两个颜色的树结构，利用左旋右旋的特性来进行调整，让树结构能够符合自己的预期。并且总结出了这类树结构的各种情况下的旋转变色操作（或者说是公式）。

具体代码如下：各个功能的注释都有写

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
/**
 * @description
 * 
 * @author lfy
 */
public class RedBlackTree {

	public static void main(String[] args) {
		RedBlackTree rb = new RedBlackTree();
		// rb.adds(10, 40, 30, 60, 90, 70, 20, 50, 80);
		rb.adds(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
		//重写了tostring 
		System.out.println(rb.root);
	}

	public void adds(int... vs) {
		for (int i : vs) {
			add(i);
		}
	}

	// 红黑色
	private enum Color {
		Red, Black
	}

	// 节点
	private class Node {
		// 颜色 ：默认红色
		private Color color;
		// 值
		private int val;
		// 父节点
		private Node parent;
		// 左节点
		private Node left;
		// 右节点
		private Node right;

		private Node() {
			// 红
			color = RED;
		}

		@Override
		public String toString() {
			return "{'color':'" + color + "', 'val':'" + val + "', 'left':" + left + ", 'right':" + right + "}";
		}

	}

	// 静态常量 红色和黑色
	private static final Color RED = Color.Red;
	private static final Color BLACK = Color.Black;
	// 根节点
	private Node root;
	// 大小
	private int size;

	/**
	 * 新增
	 * 
	 * @author lfy
	 * @param v
	 */
	public void add(int v) {
		Node n = new Node();
		n.val = v;
		// 根节点
		if (root == null) {
			root = n;
			root.color = BLACK;
			return;
		}
		// 重复不考虑
		if (exists(v)) {
			return;
		}
		// 非根节点
		// 根节点开始查找
		Node target = root;
		// 应该插入的是左节点还是右节点 true为左 right为右
		boolean isLeft = true;
		// 应该插入的节点的父节点
		Node p = null;
		// 查找节点
		while (target != null) {
			p = target;
			isLeft = v < target.val;
			if (isLeft) {
				target = target.left;
			} else {
				target = target.right;
			}
		}
		// 判断是左节点还是右节点
		if (isLeft) {
			p.left = n;
			n.parent = p;
		} else {
			p.right = n;
			n.parent = p;
		}
		// 调整
		fix1(n);
		size++;
	}

	/**
	 * 调整 第一版
	 * 
	 * @author lfy
	 * @param n
	 */
	private void fix1(Node n) {
		// 父节点是黑的 什么都不用做
		if (n.parent == null) {
			root = n;
			root.color = BLACK;
			return;
		}
		if (getColor(n.parent) == BLACK) {
			return;
		}
		Node p = n.parent;
		// 如果父节点是红的 祖父节点必定是黑的且非空的
		// 父节点是左节点还是右节点
		boolean isLeft = p.parent.left == p;
		// 叔叔节点
		Node u = isLeft ? p.parent.right : p.parent.left;
		// 叔叔节点是红的时候
		if (getColor(u) == RED) {
			// 叔叔节点也是红的时候
			changeColor(p, u, p.parent);
			// 祖父节点是红的时候 重新调整
			if (getColor(p.parent) == RED) {
				fix1(p.parent);
			}

			// 叔叔节点是黑色的 父节点是左节点
		} else if (isLeft) {
			// 当前节点是右节点 转成三点一线的形式（当前节点、父节点、祖父节点）
			if (n.parent.right == n) {
				// 关注节点改成原本的父节点 即现在的三点一线的三点里最下面的一点
				n = n.parent;
				rotateLeft(n);
			}
			if (n.parent.parent == null) {
				changeColor(n.parent);
			} else {
				Node pp = n.parent.parent;
				// 三点一线的情况下
				// 转变父节点和祖父节点颜色
				changeColor(n.parent, pp);
				// 右旋祖父节点 调整平衡性
				rotateRight(n.parent.parent);

				// 因为祖父节点变成了了红色 所以重新走一次
				fix1(pp);
			}
			// 叔叔节点是黑色的 父节点是右节点
		} else {
			// 当前节点是左节点 转成三点一线的形式（当前节点、父节点、祖父节点）
			if (n.parent.left == n) {
				n = n.parent;
				// 关注节点改成原本的父节点 即现在的三点一线的三点里最下面的一点
				rotateRight(n);
			}
			if (n.parent.parent == null) {
				changeColor(n.parent);
			} else {
				Node pp = n.parent.parent;
				// 转变父节点和祖父节点颜色
				changeColor(n.parent, pp);

				// 左旋祖父节点 调整平衡性
				rotateLeft(pp);
				// 因为祖父节点变成了了红色 所以重新走一次
				fix1(pp);
			}
		}

	}

	/**
	 * 左旋
	 * 
	 * @author lfy
	 * @param v
	 */
	private void rotateLeft(Node n) {

		if (n != null) {
			///////////////////////
			// 写完之后看了网络上的写法
			// 这里其实可以不写父属性了 可以少创建一个变量
			// 在右旋中做了这个更改
			//////////////////////
			// 父节点
			Node p = n.parent;
			// 右节点的左节点 即要左旋的另一个对象
			Node s = n.right;
			// 将子节点的左节点 赋值为关注节点的右节点
			n.right = s.left;
			if (s.left != null) {
				s.left.parent = n;
			}
			// 将子节点的左节点赋值为关注节点
			s.left = n;
			// 子节点的父节点修改为关注节点的父节点
			s.parent = p;
			// 关注节点的父节点修改为子节点
			n.parent = s;// --
			// 重新整理父节点的和子节点的关系
			if (p == null) {
				// 没有父节点 重设根节点
				root = s;
			} else if (p.left == n) {
				p.left = s;
			} else {
				p.right = s;
			}
		}
	};

	/**
	 * 右旋
	 * 
	 * @author lfy
	 * @param v
	 */
	private void rotateRight(Node n) {
		if (n != null) {
			// ps：写完之后看了网络上的写法 这里就不写父属性了 可以少创建一个变量
			// 父节点
			// Node p = n.parent;
			// 子节点
			Node s = n.left;
			// 将子节点的右节点给关注节点 改为关注节点的左节点
			n.left = s.right;
			if (s.right != null) {
				s.right.parent = n;
			}
			// 设置子节点的右节点为父节点
			s.right = n;
			// 重设子节点的父节点 修改为关注节点的父节点
			s.parent = n.parent;
			// 重设父节点的子节点属性
			if (n.parent == null) {
				root = s;
			} else if (n.parent.left == n) {
				n.parent.left = s;
			} else {
				n.parent.right = s;
			}
			// 重设关注节点的父节点
			n.parent = s;
		}
	};

	/**
	 * 获取节点颜色
	 * 
	 * @author lfy
	 * @param v
	 */
	private Color getColor(Node n) {
		if (n == null)
			return BLACK;
		return n.color;
	};

	/**
	 * 转换颜色
	 * 
	 * @author lfy
	 * @param n
	 */
	private void changeColor(Node... n) {
		// 遍历
		for (int i = 0; i < n.length; i++) {
			if (n[i].color == RED) {
				n[i].color = BLACK;
			} else {
				n[i].color = RED;
			}
		}
	};

	/**
	 * 二分查找 是否存在
	 * 
	 * @author lfy
	 * @return
	 */
	public boolean exists(int v) {
		Node n = root;
		while (n != null) {
			if (v < n.val) {
				n = n.left;
			} else if (v > n.val) {
				n = n.right;
			} else {
				return true;
			}

		}
		return false;
	}

	

	public int getSize() {
		return size;
	}
	
}

Review 英文文章

https://ambari.apache.org/

Ambari的介绍。

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的25-26篇（红黑树）

学习了红黑树的结构，但这篇专栏对于红黑树的描写比较简略，因此我去另外找了别的文章看。

出处：《数据结构与算法之美》（作者：王争）

https://time.geekbang.org/column/intro/126

【算法】红黑树（二叉树）

https://blog.csdn.net/lsr40/article/details/85230703

这篇文章作者一共写了5篇，在这里都有列出来。

红黑树之删除节点

https://www.cnblogs.com/qingergege/p/7351659.html

这篇文章我做了个小总结
一、删除红色的叶子节点D 直接删除D就好 然后找继承节点 不存在继承节点则不需要更多操作
PS:删除的红色节点只有左子树或只有右子树 红黑树中根本不存在这种情况

二、删除的黑色节点仅有左子树或者仅有右子树(子孩子必定为红)
删除黑色的叶子节点D
用D的孩子（左或右）替换D，
将D孩子的颜色改成黑色即可
（因为路径上少了一个黑节点，所已将红节点变成黑节点以保持红黑树的性质）。

三、删除黑色的叶子节点D
情况1：待删除节点D的兄弟节点S为红色
将父亲节点和兄弟节点的颜色互换，也就是p变成红色，S变成黑色，父亲节点右旋（或者左旋，删除节点是左节点还是右节点）

情况2：兄弟节点S为黑色，且远侄子节点为红色。
D为左孩子对的情况，这时D的远侄子节点为S的右孩子
父节点、另一个侄子节点则不关心（不影响最后的结构）（即红黑都可以）
删除节点D之后，D的子节点（可能为NULL节点）的路径的黑色节点个数就会减1，
但是我们看到S的孩子中有红色的节点，如果我们能把这棵红色的节点移动到左侧，并把它改成黑色，那么就满足要求了，
将父节点和兄弟的颜色对调，然后对右旋的操作，最后把SR节点变成黑色，并删除D即可。
D为右孩子对的情况，这时D的远侄子节点为S的左孩子，操作类似而相反。

情况3：兄弟节点S为黑色，远侄子节点为黑色，近侄子节点为红色
D为左孩子的情况，此时近侄子节点为S的左孩子
将S右旋，并将S和近侄子的颜色互换，这个时候就变成了情况4或者5。
D为右孩子的情况，此时近侄子节点为S的左孩子
将S左旋，并将S和近侄子的颜色互换，这个时候就变成了情况4或者5。

情况4：父亲节点p为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色的情况。

如果删除D，那经过P到D的子节点NULL的路径上黑色就少了一个，这个时候我们可以把P变成黑色，这样删除D后经过D子节点（NULL节点）路径上的黑色节点就和原来一样了。但是这样会导致经过S的子节点（NULL节点）的路径上的黑色节点数增加一个，所以这个时候可以再将S节点变成红色，这样路径上的黑色节点数就和原来一样啦！

所以做法是，将父亲节点P改成黑色，将兄弟节点S改成红色，然后删除D即可。

情况5：父亲节点p，兄弟节点s和兄弟节点的两个孩子（只能为NULL节点）都为黑色的情况
方法是将兄弟节点S的颜色改成红色，这样删除D后P的左右两支的黑节点数就相等了，但是经过P的路径上的黑色节点数会少1，这个时候，我们再以P为起始点，继续根据情况进行平衡操作（这句话的意思就是把P当成D（只是不要再删除P了），再看是那种情况，再进行对应的调整，这样一直向上，直到新的起始点为根节点）。结果如下图：

Share 分享

为什么HTTPS比HTTP更安全?

https://blog.csdn.net/howgod/article/details/89596638