使用Java实现平衡二叉树

使用Java实现平衡二叉树

二叉树是一种较为复杂的数据结构,二叉树算法在数据查询时的时间复杂度为
O(log n)(n为保存元素个数).
但是普通的二叉树在数据添加和删除时很容易出现树结构不平衡问题
,而使用平衡二叉树则不会出现这样的问题.

如何实现?

我们通过旋转完成
如:左旋转
怎么处理-进行左旋转

1.创建一个新的节点newnode(以4这个值创建)，创建一个新的节点，值等于当前根节点的值

//把新节点的左子树设置了当前节点的左子树

2.newnode.left=left

//把新节点的右子树设置为当前节点的右子树的左子树

3.newnode.right=right.left

把当前节点的值换为右子节点的值

4.value=right.value

//把当前节点的右子树设置为右子树的右子树

5.right=right.right

把当前节点的左子树设置为新节点

6.left=newnode

平衡二叉树

具体代码:

public class BalancedBinaryTree<T> {
    private int size;
    private Node root;
    @SuppressWarnings("rawtypes")
	private Comparator comparator;

    public BalancedBinaryTree() {

    }

    @SuppressWarnings("rawtypes")
	public BalancedBinaryTree(Comparator comparator) {
        this.comparator = comparator;
    }
    
    public void add(T data) {
        Node node = new Node(data);
        Node p = findNode(node);
        if (p == null) {
            this.root = node;
        } else if (p.compare(node) > 0) {
            p.left = node;
            node.parent = p;
        } else if (p.compare(node) < 0) {
            p.right = node;
            node.parent = p;
        } else {
            p.data = data;
            return;
        }
        size++;
        handleImBalance4Add(node);
    }

    public boolean remove(T data) {
        if (root == null) {
            return false;
        }
        Node node = new Node(data);
        Node res = findNode(node);
        if (node.compare(res) != 0) {
            throw new NoSuchElementException();
        }
        Node checkPoint;
        if (res.left == null && res.right == null) {
            checkPoint = removeLeafNode(res);
        } else if (res.left == null || res.right == null) {
            checkPoint = removeNodeWithOneChild(res);
        } else {
            checkPoint = removeNodeWithTwoChild(res);
        }
        if (checkPoint != null) {
            handleImbalance4Remove(checkPoint);
        }
        size--;
        return true;
    }

    public int size() {
        return size;
    }

    private void handleImbalance4Remove(Node checkPoint) {
        Node tmp = checkPoint;
        boolean leftRemoved = false;
        if (tmp.left == null && tmp.right == null) {
            tmp.factor = 0;
            if (tmp.parent != null) {
                leftRemoved = tmp.parent.left == tmp;
            }
            tmp = tmp.parent;
        } else if (tmp.factor == 0) {
            tmp.factor = tmp.left == null ? 1 : -1;
            return;
        } else {
            leftRemoved = tmp.left == null;
        }
        int f;
        while (tmp != null) {
            f = tmp.factor;

            if (leftRemoved) {
                f = f + 1;
            } else {
                f = f - 1;
            }
            tmp.factor = f;
            if (f == -2 || f == 2) {
                tmp = handleImbalance(tmp);
            } else if (f == 1 || f == -1) {
                break;
            }
            leftRemoved = tmp.parent != null && tmp.parent.left == tmp;
            tmp = tmp.parent;
        }
    }

    private Node removeNodeWithTwoChild(Node node) {
        if (node.left == null || node.right == null) {
            throw new IllegalStateException("only use of two child node removing");
        }
        Node target = findDeepestAndClosestNodeOfCurrentNode(node);
        node.data = target.data;
        Node p = null;
        if (target.left == null && target.right == null) {
            p = removeLeafNode(target);
        } else if (target.left == null || target.right == null) {
            p = removeNodeWithOneChild(target);
        } else {
            //impossible
            throw new IllegalStateException("method of findDeepestAndClosestNodeOfCurrentNode work not right!");
        }
        return p;
    }

    private Node removeNodeWithOneChild(Node node) {
        Node parent = node.parent;
        Node child;
        if (node.left == null && node.right != null) {
            child = node.right;
        } else if (node.right == null && node.left != null) {
            child = node.left;
        } else {
            throw new IllegalStateException("only use of one child node removing");
        }
        child.parent = parent;
        if (parent == null) {
            root = child;
        } else if (parent.left == node) {
            parent.left = child;
        } else {
            parent.right = child;
        }
        return child;
    }

    private Node removeLeafNode(Node node) {
        if (node.left != null || node.right != null) {
            throw new IllegalStateException("only use of leaf child node removing");
        }
        Node parent = node.parent;
        if (parent != null) {
            if (parent.left == node) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else {
            root = null;
        }
        return parent;
    }

    private Node findDeepestAndClosestNodeOfCurrentNode(Node node) {
        Node left = node.left;
        Node right = node.right;
        int i = 0, j = 0;
        Node targetLeft = left, targetRight = right;
        boolean bottom = false;
        for (; ; i++) {
            if (left.right != null) {
                left = left.right;
            } else {
                if (!bottom) {
                    targetLeft = left;
                    bottom = true;
                }
                if (left.left != null) {
                    left = left.left;
                } else {
                    break;
                }
            }
        }
        bottom = false;
        for (; ; j++) {
            if (right.left != null) {
                right = right.left;
            } else {
                if (!bottom) {
                    targetRight = right;
                    bottom = true;
                }
                if (right.right != null) {
                    right = right.right;
                } else {
                    break;
                }
            }
        }
        if (i >= j) {
            return targetLeft;
        } else {
            return targetRight;
        }
    }

    private void handleImBalance4Add(Node checkPoint) {
        Node tmp = checkPoint;
        Node p = tmp.parent;
        boolean tmpLeftFlag;
        int k;
        while (p != null) {
            tmpLeftFlag = p.left == tmp;
            if (tmpLeftFlag) {
                k = p.factor - 1;
            } else {
                k = p.factor + 1;
            }
            p.factor = k;
            if (k == 2 || k == -2) {
                handleImbalance(p);
                break;
            } else if (k == 0) {
                break;
            }
            tmp = p;
            p = p.parent;
        }
    }

    private Node handleImbalance(Node node) {
        Node res;
        int rotateType;
        int k = 0;
        if (node.factor == -2 && node.left.factor == -1) {
            res = RRR(node);
            rotateType = 1;
        } else if (node.factor == 2 && node.right.factor == 1) {
            res = LLR(node);
            rotateType = 2;
        } else if (node.factor == -2 && node.left.factor == 1) {
            k = node.left.right.factor;
            res = LRR(node);
            rotateType = 3;
        } else if (node.factor == 2 && node.right.factor == -1) {
            k = node.right.left.factor;
            res = RLR(node);
            rotateType = 4;
        } else {
            throw new RuntimeException("平衡因子计算错误");
        }
        handleFactorAfterReBalance(res, rotateType, k);
        return res;
    }

    private void handleFactorAfterReBalance(Node node, int rotateType, int originFactor) {
        node.factor = 0;
        if (rotateType == 1) {
            node.right.factor = 0;
        } else if (rotateType == 2) {
            node.left.factor = 0;
        } else if (rotateType == 3 || rotateType == 4) {
            if (originFactor == 1) {
                node.left.factor = -1;
                node.right.factor = 0;
            } else if (originFactor == -1) {
                node.left.factor = 0;
                node.right.factor = 1;
            } else {
                node.left.factor = 0;
                node.right.factor = 0;
            }
        }
    }

    private Node RRR(Node node) {
        Node parent = node.parent;
        Node child = node.left;
        child.parent = parent;
        node.parent = child;
        node.left = child.right;
        if (node.left != null) {
            node.left.parent = node;
        }
        child.right = node;
        if (parent == null) {
            root = child;
        } else if (parent.right == node) {
            parent.right = child;
        } else {
            parent.left = child;
        }
        return child;
    }

    private Node LLR(Node node) {
        Node parent = node.parent;
        Node child = node.right;
        child.parent = parent;
        node.parent = child;
        node.right = child.left;
        if (node.right != null) {
            node.right.parent = node;
        }
        child.left = node;
        if (parent == null) {
            root = child;
        } else if (parent.left == node) {
            parent.left = child;
        } else {
            parent.right = child;
        }
        return child;
    }

    private Node LRR(Node node) {
        LLR(node.left);
        return RRR(node);
    }

    private Node RLR(Node node) {
        RRR(node.right);
        return LLR(node);
    }

    private Node findNode(Node node) {
        Node p = null;
        Node tmp = root;
        while (tmp != null) {
            p = tmp;
            if (tmp.compare(node) > 0) {
                tmp = tmp.left;
            } else if (tmp.compare(node) < 0) {
                tmp = tmp.right;
            } else {
                break;
            }
        }
        return p;
    }

    private void traverse(Node node, Consumer<Node> consumer) {
        if (node == null) {
            return;
        }
        Deque<Node> nodeDeque = new ArrayDeque<>();
        node.height = 1;
        nodeDeque.add(node);
        while (nodeDeque.size() > 0) {
            Node first = nodeDeque.pollFirst();
            consumer.accept(first);
            Node right = first.right;
            if (right != null) {
                right.height = first.height + 1;
                nodeDeque.addFirst(right);
            }
            Node left = first.left;
            if (left != null) {
                left.height = first.height + 1;
                nodeDeque.addFirst(left);
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        traverse(root, n -> {
            for (int i = 0; i < n.height; i++) {
                res.append("----------");
            }
            res.append(':');
            res.append(n.data);
            res.append('(');
            res.append(n.factor);
            res.append(')');
            res.append('\n');
        });
        return res.toString();
    }

    private int getMaxHeight(Node node){
        int[] height = new int[1];
        traverse(node,n->{
            if(n.left == null && n.right == null && n.height > height[0]){
                height[0] = n.height;
            }
        });
        return height[0];
    }
    
    //查询
	public boolean contains(Comparable<T> data) {
		if (this.size == 0) {									// 没有数据
			return false ;										// 结束查询
		}
		return this.root.containsNode(data) ; 					// Node类查询
	}

    class Node {
        private Node parent;
        private Node left;
        private Node right;
        private int factor;
        private int height;
        private T data;

        public Node(T data) {
            Objects.requireNonNull(data);
            this.data = data;
        }

        public int compare(Node target) {
            if (comparator != null) {
                return comparator.compare(this.data, target.data);
            } else {
                return ((Comparable) this.data).compareTo(target.data);
            }
        }

        @Override
        public String toString() {
            return data.toString();
        }
        public boolean containsNode(Comparable<T> data) {
			if (data.compareTo((T) this.data) == 0) {			// 数据匹配
				return true; 									// 查找到了
			} else if (data.compareTo((T) this.data) < 0) { 	// 左子节点查询
				if (this.left != null) {						// 左子节点存在
					return this.left.containsNode(data);		// 递归调用
				} else {										// 没有左子节点
					return false;								// 无法找到
				}
			} else { 											// 右子节点查询
				if (this.right != null) {						// 右子节点存在
					return this.right.containsNode(data);		// 递归调用
				} else {										// 没有右子节点
					return false;								// 无法找到
				}
			}
		}
    }

    static BalancedBinaryTree<Integer> buildTestTree() {
        BalancedBinaryTree<Integer> binaryTree = new BalancedBinaryTree();
        binaryTree.add(8);
        binaryTree.add(3);
        binaryTree.add(13);
        binaryTree.add(1);
        binaryTree.add(5);
        binaryTree.add(10);
        binaryTree.add(16);
        binaryTree.add(2);
        binaryTree.add(4);
        binaryTree.add(7);
        binaryTree.add(9);
        binaryTree.add(12);
        binaryTree.add(15);
        binaryTree.add(18);
        binaryTree.add(6);
        binaryTree.add(11);
        binaryTree.add(14);
        binaryTree.add(17);
        binaryTree.add(19);
        binaryTree.add(20);
        return binaryTree;
    }
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
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458

实例:

public class Binary {
	public static void main(String args[]) {
		 BalancedBinaryTree<Integer> bbt = new BalancedBinaryTree<>();
	     bbt.add(100);
	     bbt.add(10);
	     bbt.add(40);
	     bbt.add(34);
	     bbt.add(210);
	     System.out.println(bbt);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

使用自定义数据结构

那我们实现自己类信息的排列呢?
很简单,只需将类加入Comparable接口就可以了
如

public class Emp implements Comparable<Emp>{
	private String ename ;
	private String job ;
	private Double salary ;
	private Integer age ;
	private Date hiredate ; 
	private String dept ;
	public String getEname() {
		return ename;
	}
	public void setEname(String ename) {
		this.ename = ename;
	}
	public String getJob() {
		return job;
	}
	public void setJob(String job) {
		this.job = job;
	}
	public Double getSalary() {
		return salary;
	}
	public void setSalary(Double salary) {
		this.salary = salary;
	}
	public Integer getAge() {
		return age;
	}
	public void setAge(Integer age) {
		this.age = age;
	}
	public Date getHiredate() {
		return hiredate;
	}
	public void setHiredate(Date hiredate) {
		this.hiredate = hiredate;
	}
	public String getDept() {
		return dept;
	}
	public void setDept(String dept) {
		this.dept = dept;
	}
	@Override
	public int compareTo(Emp emp) {
		return this.age - emp.age;
	}
@Override
	public String toString() {
		return "Emp [ename=" + ename + ", job=" + job + ", salary=" + salary + ", age=" + age + ", hiredate=" + hiredate
				+ ", dept=" + dept + "]";
	}
}
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

主类(我这里使用了自己做的一个属性自动配置工具):

public class Binary {
	public static void main(String args[]) {
	     System.out.println("使用自定义数据");
	     BalancedBinaryTree<Emp> b = new BalancedBinaryTree<>();
	     String value = "ename:Smith|job:Clerk|salary:8960.00|age:30|hiredate:2003-10-15|"
					+ "dept.dname:财务部|dept.loc:MLDN|dept.company.name:SMD" ;
	     String value2 = "ename:231213|job:Clerk|salary:8960.00|age:24|hiredate:2003-10-15|"
					+ "dept.dname:财务部|dept.loc:MLDN|dept.company.name:SMD" ;
		Emp emp = ClassInstanceFactory.create(Emp.class, value) ;	// 工具类自动设置
		Emp emp2 = ClassInstanceFactory.create(Emp.class, value2) ;	// 工具类自动设置
		String value3 = "ename:23|job:Clerk|salary:8960.00|age:43|hiredate:2003-10-15|"
						+ "dept.dname:财务部|dept.loc:MLDN|dept.company.name:Alibaba" ;
		Emp emp3 = ClassInstanceFactory.create(Emp.class, value3) ;	// 工具类自动设置
		String value4 = "ename:23|job:Clerk|salary:8960.00|age:43|hiredate:2003-10-15|"
				+ "dept.dname:财务部|dept.loc:MLDN|dept.company.name:Alibaba" ;
		Emp emp4 = ClassInstanceFactory.create(Emp.class, value4) ;	// 工具类自动设置
		b.add(emp);
		b.add(emp2);
		b.add(emp3);
	    System.out.println(b);
	    System.out.println(b.contains(emp4));//寻找存不存在和emp4一个属性的对象
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

如果感觉有用就请给我点个免费的赞吧❥(^_-)