-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathLLRB.java
More file actions
108 lines (90 loc) · 2.78 KB
/
LLRB.java
File metadata and controls
108 lines (90 loc) · 2.78 KB
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
package Heap;
public class LLRB<T extends Comparable<? super T>> {
public static boolean RED = true;
public static boolean BLACK = false;
public class Node {
public Node left;
public Node right;
public T key;
public boolean color;
public Node(T key, Node left, Node right, boolean color) {
this.key = key;
this.left = left;
this.right = right;
this.color = color;
}
public Node rotateLeft() {
return build(right.key, build(key, left, right.left, RED), right.right, color);
}
public Node rotateRight() {
return build(left.key, left.left, build(key, left.right, right, RED), color);
}
public void sand() {
color = RED;
left.color = BLACK;
right.color = BLACK;
}
public Node balance() {
if (isRed(right) && !isRed(left)) {
return rotateLeft().balance();
}
if (isRed(left) && isRed(left.left)) {
return rotateRight();
}
return this;
}
}
public Node build(T key, Node left, Node right, boolean color) {
return new Node(key, left, right, color);
}
public Node build(T key) {
return new Node(key, null, null, RED);
}
public Node put(Node p, T x) {
if (p == null) {
return build(x);
}
if (isRed(p.left) && isRed(p.right)) {
p.sand();
}
if (p.key.compareTo(x) > 0) {
return build(p.key, put(p.left, x), p.right, p.color).balance();
} else {
return build(p.key, p.left, put(p.right, x), p.color).balance();
}
}
public boolean isRed(Node p) {
return (p != null) && p.color == RED;
}
public void printNice(Node root, int level) {
if (root == null) {
return;
}
printNice(root.right, level + 1);
if (level != 0) {
for (int i = 0; i < level - 1; i++) {
System.out.print("| ");
}
if (isRed(root)) {
System.out.println("|===" + root.key);
} else {
System.out.println("|---" + root.key);
}
} else {
System.out.println(root.key);
}
printNice(root.left, level + 1);
}
public static void main(String[] args) {
LLRB<Integer> app = new LLRB<>();
LLRB.Node root = app.build(2);
root = app.put(root, 4);
root = app.put(root, 1);
root = app.put(root, 3);
root = app.put(root, 5);
root = app.put(root, 6);
root = app.put(root, 8);
root = app.put(root, 9);
app.printNice(root, 1);
}
}