-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathRedBlackTree.java
More file actions
158 lines (119 loc) · 4.28 KB
/
RedBlackTree.java
File metadata and controls
158 lines (119 loc) · 4.28 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
//And Nathanael said unto him, Can there any good thing come out of Nazareth? Philip saith unto him, Come and see. (John 1:46)
package com.javarush.task.task36.task3604;
public class RedBlackTree {
private static final Node EMPTY = new Node(0);
static {
EMPTY.left = EMPTY;
EMPTY.right = EMPTY;
}
protected Node current;
private Node parent;
private Node grand;
private Node great;
private Node header;
public RedBlackTree() {
header = new Node(Integer.MIN_VALUE);
header.left = EMPTY;
header.right = EMPTY;
}
public boolean isEmpty() {
return header.right == EMPTY;
} // changed .left -> .right
public void clear() {
header.right = EMPTY;
}
public void insert(int item) {
current = grand = parent = header;
EMPTY.element = item;
while (current.element != item) {
great = grand;
grand = parent;
parent = current;
current = item > current.element ? current.right : current.left;
if (current.left.color == Color.RED) { // cut + && current.right.color == Color.BLACK) {
reorient(item);
}
}
if (current != EMPTY) {
return;
}
current = new Node(item, EMPTY, EMPTY);
if (item < parent.element) {
parent.left = current;
} else {
parent.right = current;
}
reorient(item);
}
protected void reorient(int item) {
current.color = Color.RED;
current.left.color = Color.BLACK;
current.right.color = Color.BLACK;
if (parent.color == Color.RED) {
grand.color = Color.RED;
if (item < grand.element != item < parent.element) {
parent = rotate(item, grand);
}
current = rotate(item, great);
current.color = Color.BLACK;
}
header.right.color = Color.BLACK;
}
private Node rotate(int item, Node parent) {
if (item < parent.element) {
Node node = parent.left;
Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
parent.left = resultNode;
return parent.left;
} else {
Node node = parent.right;
Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
parent.right = resultNode;
return parent.right;
}
}
private Node rotateWithLeftNode(Node element) {
Node left = element.left;
element.left = left.right;
left.right = element;
return left;
}
private Node rotateWithRightNode(Node element) {
Node right = element.right; // refactored left -> right, right -> left;
element.right = right.left;
right.left = element;
return right;
}
public static enum Color {
BLACK,
RED
}
public static class Node {
private int element;
private Node left;
private Node right;
private Color color;
public Node(int element) {
this(element, null, null);
}
public Node(int element, Node left, Node right) {
this.left = left;
this.right = right;
this.element = element;
this.color = Color.BLACK;
}
}
}
/*
Разбираемся в красно-черном дереве
Дана реализация красно-черного дерева.
Некоторые методы сломаны. Разберись в коде и исправь ошибки.
Метод main не участвует в тестировании.
Все модификаторы правильные.
Имена переменных и методов не изменяйте.
Требования:
1. Исправь ошибку в методе isEmpty в классе RedBlackTree.
2. Исправь ошибку в методе rotateWithRightNode в классе RedBlackTree.
3. Исправь ошибку в методе insert в классе RedBlackTree.
4. Класс RedBlackTree должен реализовывать красно-черное дерево.
*/