forked from rangken/AlgorithmStudy
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRedBlackTree.java
More file actions
163 lines (151 loc) · 5.77 KB
/
Copy pathRedBlackTree.java
File metadata and controls
163 lines (151 loc) · 5.77 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
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
public class RedBlackTree<E extends Comparable<E>> extends BinarySearchTree<E> implements ITree<E>, BinaryTree.INodeCreator<E>{
protected static final boolean BLACK = false;
protected static final boolean RED = true;
public RedBlackTree() {
this.creator = this;
}
@Override
public boolean add(E data){
RedBlackNode<E> nodeAdded = null;
boolean added = false;
if(root == null){
root = this.creator.createNewNode(data, null);
((RedBlackNode<E>) root).color = BLACK;
root.left = this.creator.createNewNode(null, root);
((RedBlackNode<E>) root.left).color = BLACK;
root.right = this.creator.createNewNode(null, root);
((RedBlackNode<E>) root.right).color = BLACK;
nodeAdded = (RedBlackNode<E>) root;
added = true;
}else{
Node<E> node = root;
while (node != null) {
if (node.element == null) {
node.element = data;
((RedBlackNode<E>) node).color = RED;
node.left = this.creator.createNewNode(null, node);
((RedBlackNode<E>) node.left).color = BLACK;
node.right = this.creator.createNewNode(null, node);
((RedBlackNode<E>) node.right).color = BLACK;
nodeAdded = (RedBlackNode<E>) node;
added = true;
break;
}else if (data.compareTo(node.element) <= 0) {
node = node.left;
} else {
node = node.right;
}
}
}
if (added == true) {
balanceAfterInsert(nodeAdded);
}
return true;
}
private void balanceAfterInsert(RedBlackNode<E> node) {
RedBlackNode<E> parent = (RedBlackNode<E>) node.parent;
if (parent == null) {
// 1.현재노드의 루트
node.color = BLACK;
return;
}
if (parent.color == BLACK) {
// 2. 현재노드의 부모가 블랙 => 문제없다.
return;
}
RedBlackNode<E> grandParent = node.getGrandParent();
RedBlackNode<E> uncle = node.getUncle();
if (parent.color == RED && uncle.color == RED) {
// 3. 부모와 삼춘이 모두 RED => 두사람 모두 블랙이되고 할머니를 레드로
parent.color = BLACK;
uncle.color = BLACK;
if (grandParent != null) {
grandParent.color = RED;
balanceAfterInsert(grandParent);
}
} else {
if (parent.color == RED && uncle.color == BLACK) {
// 4. 부모는 레드 삼촌은 블랙
// 부모의 오른쪽에 있는 노드라면, 엄마가 할머니의 왼쪽에 있다면
if (node.equals(parent.right) && parent.equals(grandParent.left)) {
// right-left
rotateLeft(parent);
node = (RedBlackNode<E>) node.left;
grandParent = node.getGrandParent();
parent = (RedBlackNode<E>) node.parent;
uncle = node.getUncle();
} else if (node.equals(parent.left) && parent.equals(grandParent.right)) {
// left-right
rotateRight(parent);
node = (RedBlackNode<E>) node.right;
grandParent = node.getGrandParent();
parent = (RedBlackNode<E>) node.parent;
uncle = node.getUncle();
}
}
if (parent.color == RED && uncle.color == BLACK) {
// 5. 부모가 레드 삼촌이 블랙
parent.color = BLACK;
grandParent.color = RED;
if (node.equals(parent.left) && parent.equals(grandParent.left)) {
// left-left
rotateRight(grandParent);
} else if (node.equals(parent.right) && parent.equals(grandParent.right)) {
// right-right
rotateLeft(grandParent);
}
}
}
}
@Override
public Node<E> createNewNode(E element, Node<E> parent) {
return (new RedBlackNode<E>(element, parent, BLACK));
}
protected static class RedBlackNode<E extends Comparable<E>> extends Node<E> {
protected boolean color = BLACK;
protected RedBlackNode(E element, Node<E> parent,boolean color) {
super(element, parent);
this.color = color;
}
protected RedBlackNode<E> getGrandParent() {
if (parent == null || parent.parent == null) return null;
return (RedBlackNode<E>) parent.parent;
}
protected RedBlackNode<E> getUncle() {
RedBlackNode<E> grandParent = getGrandParent();
if (grandParent == null) return null;
if (grandParent.left != null && grandParent.left.equals(parent)) {
// 부모에가 할머니에 왼쪽에 있다면 => 삼촌은 오른쪽
return (RedBlackNode<E>) grandParent.right;
} else if (grandParent.right != null && grandParent.right.equals(parent)) {
// 부모에가 할머니에 오른쪽에 있다면 => 삼촌은 왼쪽
return (RedBlackNode<E>) grandParent.left;
}
return null;
}
protected RedBlackNode<E> getSibling() {
if (parent == null) return null;
if (parent.left.equals(this)) {
// 내가 부모의 왼쪽이라면 형재자매는 오른쪽
return (RedBlackNode<E>) parent.right;
} else if (parent.right.equals(this)) {
// 내가 부모의 오른쪽이라면 형재자매는 왼쪽
return (RedBlackNode<E>) parent.left;
} else {
System.err.println("opps no sibling");
}
return null;
}
protected boolean isLeaf() {
// RedBlack 에서는 자식 모두 null 이면 leat
if (left != null) return false;
if (right != null) return false;
return true;
}
@Override
public String toString(){
String colorStr = color == BLACK ? "BLACK" : "RED";
return "element : " + element +" : COLOR : " + colorStr;
}
}
}