Libraryless. Click here for Pure Java version (13098L/89K).
1 | // see: https://en.wikipedia.org/wiki/Order_statistic_tree |
2 | // based on: https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html |
3 | final sclass LogNArray<Value> extends RandomAccessAbstractList<Value> { |
4 | |
5 | // A symbol table implemented using a left-leaning red-black BST. |
6 | // This is the 2-3 version. |
7 | |
8 | private static final boolean RED = true; |
9 | private static final boolean BLACK = false; |
10 | |
11 | private Node<Value> root; // root of the BST |
12 | |
13 | // BST helper node data type |
14 | private final sclass Node<Value> { |
15 | private Value val; // associated data |
16 | private Node<Value> left, right; // links to left and right subtrees |
17 | private int sizeAndColor; // subtree count + color (highest bit) |
18 | |
19 | *() {} |
20 | |
21 | *(Value val, boolean color, int size) { |
22 | this.val = val; |
23 | sizeAndColor = size | (color ? 0x80000000 : 0); |
24 | } |
25 | |
26 | int size() { ret sizeAndColor & 0x7FFFFFFF; } |
27 | bool color() { ret sizeAndColor < 0; } |
28 | |
29 | void setSize(int size) { sizeAndColor = sizeAndColor & 0x80000000 | size; } |
30 | void setColor(bool color) { sizeAndColor = size() | (color ? 0x80000000 : 0); } |
31 | } |
32 | |
33 | // is node x red; false if x is null ? |
34 | private boolean isRed(Node<Value> x) { |
35 | if (x == null) return false; |
36 | return x.color() == RED; |
37 | } |
38 | |
39 | // number of node in subtree rooted at x; 0 if x is null |
40 | private int size(Node<Value> x) { |
41 | if (x == null) return 0; |
42 | return x.size(); |
43 | } |
44 | |
45 | |
46 | public int size() { |
47 | return size(root); |
48 | } |
49 | |
50 | public boolean isEmpty() { |
51 | return root == null; |
52 | } |
53 | |
54 | |
55 | public void add(int idx, Value val) { |
56 | if (idx < 0 || idx > size()) throw new IndexOutOfBoundsException(idx + " / " + size()); |
57 | |
58 | root = add(root, idx, val); |
59 | root.setColor(BLACK); |
60 | ifdef LogNArray_debug assertTrue(check()); endifdef |
61 | } |
62 | |
63 | // insert the value pair in index k of subtree rooted at h |
64 | private Node<Value> add(Node<Value> h, int k, Value val) { |
65 | if (h == null) ret new Node(val, RED, 1); |
66 | |
67 | int t = size(h.left); |
68 | if (k < t) |
69 | // replace / fit in left child |
70 | h.left = add(h.left, k, val); |
71 | else if (k == t) { |
72 | // move value to right child, replace value |
73 | h.right = add(h.right, 0, h.val); |
74 | h.val = val; |
75 | } else |
76 | // replace / fit in right child |
77 | h.right = add(h.right, k-t-1, val); |
78 | |
79 | // fix-up any right-leaning links |
80 | if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); |
81 | if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); |
82 | if (isRed(h.left) && isRed(h.right)) flipColors(h); |
83 | h.setSize(size(h.left) + size(h.right) + 1); |
84 | |
85 | ifdef LogNArray_debug |
86 | print("LogNArray.add: Node " + h.val + " new size: " + h.size()); |
87 | endifdef |
88 | |
89 | ret h; |
90 | } |
91 | |
92 | public Value remove(int idx) { |
93 | Value oldValue = get(idx); |
94 | |
95 | // if both children of root are black, set root to red |
96 | if (!isRed(root.left) && !isRed(root.right)) |
97 | root.setColor(RED); |
98 | |
99 | root = remove(root, idx); |
100 | if (root != null) root.setColor(BLACK); |
101 | |
102 | ifdef LogNArray_debug assertTrue(check()); endifdef |
103 | |
104 | ret oldValue; |
105 | } |
106 | |
107 | private Node<Value> remove(Node<Value> h, int k) { |
108 | int t = size(h.left); |
109 | if (k < t) { // remove from left child |
110 | if (!isRed(h.left) && !isRed(h.left.left)) |
111 | h = moveRedLeft(h); |
112 | h.left = remove(h.left, k); |
113 | } else { // remove from center or right child |
114 | if (isRed(h.left)) { |
115 | h = rotateRight(h); |
116 | t = size(h.left); |
117 | } |
118 | if (h.right == null) null; // drop whole node |
119 | if (!isRed(h.right) && !isRed(h.right.left)) { |
120 | h = moveRedRight(h); |
121 | t = size(h.left); |
122 | } |
123 | if (k == t) { // replace center value with min of right child |
124 | h.val = nodeAtIndex(h.right, 0).val; |
125 | h.right = remove(h.right, 0); |
126 | } |
127 | else h.right = remove(h.right, k-t-1); |
128 | } |
129 | ret balance(h); |
130 | } |
131 | |
132 | // make a left-leaning link lean to the right |
133 | private Node<Value> rotateRight(Node<Value> h) { |
134 | // assert (h != null) && isRed(h.left); |
135 | Node<Value> x = h.left; |
136 | h.left = x.right; |
137 | x.right = h; |
138 | x.setColor(x.right.color()); |
139 | x.right.setColor(RED); |
140 | x.setSize(h.size()); |
141 | h.setSize(size(h.left) + size(h.right) + 1); |
142 | return x; |
143 | } |
144 | |
145 | // make a right-leaning link lean to the left |
146 | private Node<Value> rotateLeft(Node<Value> h) { |
147 | // assert (h != null) && isRed(h.right); |
148 | Node<Value> x = h.right; |
149 | h.right = x.left; |
150 | x.left = h; |
151 | x.setColor(x.left.color()); |
152 | x.left.setColor(RED); |
153 | x.setSize(h.size()); |
154 | h.setSize(size(h.left) + size(h.right) + 1); |
155 | return x; |
156 | } |
157 | |
158 | // flip the colors of a node and its two children |
159 | private void flipColors(Node<Value> h) { |
160 | // h must have opposite color of its two children |
161 | // assert (h != null) && (h.left != null) && (h.right != null); |
162 | // assert (!isRed(h) && isRed(h.left) && isRed(h.right)) |
163 | // || (isRed(h) && !isRed(h.left) && !isRed(h.right)); |
164 | h.setColor(!h.color()); |
165 | h.left.setColor(!h.left.color()); |
166 | h.right.setColor(!h.right.color()); |
167 | } |
168 | |
169 | // Assuming that h is red and both h.left and h.left.left |
170 | // are black, make h.left or one of its children red. |
171 | private Node<Value> moveRedLeft(Node<Value> h) { |
172 | // assert (h != null); |
173 | // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left); |
174 | |
175 | flipColors(h); |
176 | if (isRed(h.right.left)) { |
177 | h.right = rotateRight(h.right); |
178 | h = rotateLeft(h); |
179 | flipColors(h); |
180 | } |
181 | return h; |
182 | } |
183 | |
184 | // Assuming that h is red and both h.right and h.right.left |
185 | // are black, make h.right or one of its children red. |
186 | private Node<Value> moveRedRight(Node<Value> h) { |
187 | // assert (h != null); |
188 | // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left); |
189 | flipColors(h); |
190 | if (isRed(h.left.left)) { |
191 | h = rotateRight(h); |
192 | flipColors(h); |
193 | } |
194 | return h; |
195 | } |
196 | |
197 | // restore red-black tree invariant |
198 | private Node<Value> balance(Node<Value> h) { |
199 | // assert (h != null); |
200 | |
201 | if (isRed(h.right)) h = rotateLeft(h); |
202 | if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); |
203 | if (isRed(h.left) && isRed(h.right)) flipColors(h); |
204 | |
205 | h.setSize(size(h.left) + size(h.right) + 1); |
206 | return h; |
207 | } |
208 | |
209 | |
210 | /** |
211 | * Returns the height of the BST (for debugging). |
212 | * @return the height of the BST (a 1-node tree has height 0) |
213 | */ |
214 | public int height() { |
215 | return height(root); |
216 | } |
217 | |
218 | private int height(Node<Value> x) { |
219 | if (x == null) return -1; |
220 | return 1 + Math.max(height(x.left), height(x.right)); |
221 | } |
222 | |
223 | public Value get(int k) { |
224 | ret nodeAtIndex(k).val; |
225 | } |
226 | |
227 | public Value set(int k, Value val) { |
228 | Node<Value> n = nodeAtIndex(k); |
229 | Value oldValue = n.val; |
230 | n.val = val; |
231 | ret oldValue; |
232 | } |
233 | |
234 | public Node<Value> nodeAtIndex(int k) { |
235 | if (k < 0 || k >= size()) { |
236 | throw new IndexOutOfBoundsException(k + " / " + size()); |
237 | } |
238 | ret nodeAtIndex(root, k); |
239 | } |
240 | |
241 | // the key of rank k in the subtree rooted at x |
242 | private Node<Value> nodeAtIndex(Node<Value> x, int k) { |
243 | // assert x != null; |
244 | // assert k >= 0 && k < size(x); |
245 | int t = size(x.left); |
246 | if (t > k) return nodeAtIndex(x.left, k); |
247 | else if (t < k) return nodeAtIndex(x.right, k-t-1); |
248 | else return x; |
249 | } |
250 | |
251 | private boolean check() { |
252 | if (!isSizeConsistent()) println("Subtree counts not consistent"); |
253 | if (!is23()) println("Not a 2-3 tree"); |
254 | if (!isBalanced()) println("Not balanced"); |
255 | return isSizeConsistent() && is23() && isBalanced(); |
256 | } |
257 | |
258 | // are the size fields correct? |
259 | private boolean isSizeConsistent() { return isSizeConsistent(root); } |
260 | private boolean isSizeConsistent(Node<Value> x) { |
261 | if (x == null) return true; |
262 | if (x.size() != size(x.left) + size(x.right) + 1) return false; |
263 | return isSizeConsistent(x.left) && isSizeConsistent(x.right); |
264 | } |
265 | |
266 | // Does the tree have no red right links, and at most one (left) |
267 | // red links in a row on any path? |
268 | private boolean is23() { return is23(root); } |
269 | private boolean is23(Node<Value> x) { |
270 | if (x == null) return true; |
271 | if (isRed(x.right)) return false; |
272 | if (x != root && isRed(x) && isRed(x.left)) |
273 | return false; |
274 | return is23(x.left) && is23(x.right); |
275 | } |
276 | |
277 | // do all paths from root to leaf have same number of black edges? |
278 | private boolean isBalanced() { |
279 | int black = 0; // number of black links on path from root to min |
280 | Node<Value> x = root; |
281 | while (x != null) { |
282 | if (!isRed(x)) black++; |
283 | x = x.left; |
284 | } |
285 | return isBalanced(root, black); |
286 | } |
287 | |
288 | // does every path from the root to a leaf have the given number of black links? |
289 | private boolean isBalanced(Node<Value> x, int black) { |
290 | if (x == null) return black == 0; |
291 | if (!isRed(x)) black--; |
292 | return isBalanced(x.left, black) && isBalanced(x.right, black); |
293 | } |
294 | |
295 | public void clear() { root = null; } |
296 | } |
Began life as a copy of #1024413
download show line numbers debug dex old transpilations
Travelled to 6 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt
No comments. add comment
Snippet ID: | #1024427 |
Snippet name: | LogNArray v4 [more compact version hiding color flag in size field, OK, makes a difference only without CompressedOOPS] |
Eternal ID of this version: | #1024427/5 |
Text MD5: | 7a6bd3c6c460a8f6ee733c7d57945723 |
Transpilation MD5: | aa4975d0aa40ab6ea6ebe05193febd96 |
Author: | stefan |
Category: | javax |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2019-08-12 14:36:36 |
Source code size: | 9376 bytes / 296 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 205 / 461 |
Version history: | 4 change(s) |
Referenced in: | [show references] |