Repository navigation
Expand file tree
/
Copy pathRedBlackTree.java
More file actions
126 lines (105 loc) · 3.19 KB
/
Copy pathRedBlackTree.java
File metadata and controls
126 lines (105 loc) · 3.19 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
package com.javarush.task.task36.task3604;
public class RedBlackTree {
private static final Node EMPTY = new Node(0);
protected Node current;
private Node parent;
private Node grand;
private Node great;
private Node header;
static {
EMPTY.left = EMPTY;
EMPTY.right = EMPTY;
}
public RedBlackTree() {
header = new Node(Integer.MIN_VALUE);
header.left = EMPTY;
header.right = EMPTY;
}
public boolean isEmpty() {
return header.right == EMPTY;
}
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.left : current.right;
if (current.left.color == Color.RED && current.right.color == Color.RED) {
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;
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;
}
}
}