10000 1，修改StringBuilder的compareTo。 · fleapx/javaalgorithm@e00f483 · GitHub
[go: up one dir, main page]
Skip to content

Commit e00f483

Browse files
author
shengshijun
committed
1，修改StringBuilder的compareTo。
2，添加AVLTree的toString。
1 parent eaa5605 commit e00f483

File tree

7 files changed

+361
-20
lines changed

7 files changed

+361
-20
lines changed

‎src/main/java/ssj/algorithm/collections/AVLTree.java

Lines changed: 13 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
import ssj.algorithm.Queue;
55
import ssj.algorithm.SearchTree;
66
import ssj.algorithm.Stack;
7+
import ssj.algorithm.string.StringBuilder;
78

89
import java.util.ConcurrentModificationException;
910
import java.util.Iterator;
@@ -611,7 +612,13 @@ private int rightHeight(Node cur_node) {
611612

612613
@Override
613614
public String toString() {
614-
return _head.toString();
615+
ssj.algorithm.string.StringBuilder sb = new StringBuilder("AVLTree");
616+
sb.add('[');
617+
for (T ele : this) {
618+
sb.append(ele.toString()).append(", ");
619+
}
620+
sb.add(']');
621+
return sb.toString();
615622
}
616623

617624
private void checkCurrencyModify(int expect_size) {
@@ -620,6 +627,7 @@ private void checkCurrencyModify(int expect_size) {
620627
}
621628
}
622629

630+
623631
private class Node implements Comparable<Node> {
624632
private T value;
625633
private Node left;
@@ -643,8 +651,10 @@ public Node(Node left, Node parent, Node right) {
643651
@Override
644652
public String toString() {
645653
final StringBuilder sb = new StringBuilder("Node{");
646-
sb.append("height=").append(height);
647-
sb.append(", value=").append(value);
654+
sb.append("height=");
655+
sb.append(height);
656+
sb.append(", value=");
657+
sb.append(value);
648658
sb.append('}');
649659
return sb.toString();
650660
}

‎src/main/java/ssj/algorithm/collections/BTree.java

Lines changed: 269 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,107 @@
11
package ssj.algorithm.collections;
22

3+
import com.google.common.base.Preconditions;
34
import ssj.algorithm.SearchTree;
5+
import ssj.algorithm.lang.Tuple2;
46

57
import java.util.Iterator;
68

79
/**
10+
* 在B树中支持重复元素比较复杂，因此暂时不要把重复元素插入进去
811
* Created by shenshijun on 15/2/5.
912
*/
1013
public class BTree<T extends Comparable<? super T>> implements SearchTree<T> {
11-
//TODO 完成B树
14+
private static final int DEFAULT_DEGREE = 4;
15+
private int tree_degree;
16+
private BTreeNode<T> root;
17+
private int tree_size;
18+
19+
private BTree(int degree) {
20+
Preconditions.checkArgument(degree >= 2);
21+
tree_degree = degree;
22+
tree_size = 0;
23+
root = new BTreeNode<>(tree_degree);
24+
}
25+
26+
public static <T extends Comparable<? super T>> BTree<T> degreeOf(int degree) {
27+
return new BTree<>(degree);
28+
}
29+
30+
public static <T extends Comparable<? super T>> BTree<T> defaultDegree() {
31+
return new BTree<>(DEFAULT_DEGREE);
32+
}
33+
1234
@Override
1335
public void add(T ele) {
36+
Preconditions.checkNotNull(ele);
37+
38+
BTreeNode<T> leaf_node = root;
39+
for (BTreeNode<T> cur_node = root; cur_node != null && !cur_node.isValueEmpty(); ) {
40+
leaf_node = cur_node;
41+
for (int i = 1; i < cur_node.size(); i += 2) {
42+
int cmp_res = cur_node.getValue(i).compareTo(ele);
43+
//如果非空，那么是最后一个子节点
44+
if (cmp_res < 0 && i == cur_node.size() - 2) {
45+
cur_node = cur_node.getChild(i + 1);
46+
break;
47+
} else if (cmp_res >= 0) {
48+
cur_node = cur_node.getChild(i - 1);
49+
break;
50+
}
51+
}
52+
53+
if (leaf_node.isValueFull() && cur_node != null) {
54+
splitNode(leaf_node, null);
55+
}
56+
}
57+
58+
if (leaf_node.isValueFull()) {
59+
splitNode(leaf_node, ele);
60+
} else {
61+
leaf_node.appendValue(ele);
62+
}
63+
tree_size++;
64+
}
65+
66+
private Tuple2<BTreeNode<T>, BTreeNode<T>> splitNode(BTreeNode<T> node, T insert_ele) {
67+
Preconditions.checkNotNull(node);
68+
69+
BTreeNode<T> right_node = new BTreeNode<>(tree_degree);
70+
BTreeNode<T> parent_node = node.getParent();
71+
if (node == root) {
72+
parent_node = new BTreeNode<>(tree_degree);
73+
root = parent_node;
74+
}
75+
right_node.setParent(parent_node);
1476

77+
//中间节点插入父节点，子节点的中点在degree－1。因为从0开始计数，所以需要减一
78+
int mid_index = parent_node.appendValue(node.deleteValue(node.size() / 2));
79+
parent_node.setChild(mid_index - 1, node);
80+
parent_node.setChild(mid_index + 1, right_node);
81+
82+
//把一半元素移动到新到节点中
83+
for (int i = node.size() / 2; i < node.size(); i += 1) {
84+
if (i % 2 == 0) {
85+
right_node.setChild(i - node.size() / 2, node.deleteChild(i));
86+
} else {
87+
right_node.setValue(i - node.size() / 2, node.deleteValue(i));
88+
}
89+
}
90+
91+
if (insert_ele != null) {
92+
if (parent_node.getValue(mid_index).compareTo(insert_ele) > 0) {
93+
right_node.appendValue(insert_ele);
94+
} else {
95+
node.appendValue(insert_ele);
96+
}
97+
}
98+
99+
return new Tuple2<>(node, right_node);
15100
}
16101

17102
@Override
18103
public int size() {
19-
return 0;
104+
return tree_size;
20105
}
21106

22107
@Override
@@ -54,11 +139,6 @@ public T min() {
54139
return null;
55140
}
56141

57-
@Override
58-
public T kthElement(int k) {
59-
return null;
60-
}
61-
62142
@Override
63143
public boolean contains(T ele) {
64144
return false;
@@ -73,4 +153,186 @@ public boolean isBalance() {
73153
public Iterator<T> iterator() {
74154
return null;
75155
}
156+
157+
private static class BTreeNode<T extends Comparable<? super T>> {
158+
private final int DEGREE;
159+
private final int HALF_CAPACITY;
160+
private final int CAPACITY;
161+
//奇数位置上存储子节点，偶数位置上存储关键字。
162+
private Object[] values;
163+
private BTreeNode<T> parent;
164+
private int value_index = -1;
165+
166+
public BTreeNode(int degree) {
167+
this.DEGREE = degree;
168+
HALF_CAPACITY = 2 * DEGREE - 1;
169+
CAPACITY = 4 * DEGREE - 1;
170+
}
171+
172+
public BTreeNode<T> getParent() {
173+
return parent;
174+
}
175+
176+
public void setParent(BTreeNode<T> parent) {
177+
this.parent = parent;
178+
}
179+
180+
private void extend(int expect) {
181+
if (expect >= HALF_CAPACITY) {
182+
Object[] new_values = new Object[CAPACITY];
183+
if (values != null) {
184+
System.arraycopy(values, 0, new_values, 0, values.length);
185+
}
186+
values = new_values;
187+
} else if (values == null) {
188+
values = new Object[HALF_CAPACITY];
189+
}
190+
191+
}
192+
193+
@SuppressWarnings("unchecked")
194+
public BTreeNode<T> getChild(int index) {
195+
Preconditions.checkPositionIndex(index, CAPACITY);
196+
Preconditions.checkArgument(index % 2 == 0, "wrong index");
197+
198+
extend(index);
199+
return (BTreeNode<T>) values[index];
200+
}
201+
202+
@SuppressWarnings("unchecked")
203+
public T getValue(int index) {
204+
Preconditions.checkPositionIndex(index, CAPACITY);
205+
Preconditions.checkArgument(index % 2 == 1, "wrong index");
206+
207+
extend(index);
208+
return (T) values[index];
209+
}
210+
211+
public int size() {
212+
extend(1);
213+
return values.length;
214+
}
215+
216+
public boolean isValueFull() {
217+
return size() == CAPACITY && value_index == CAPACITY - 2;
218+
}
219+
220+
public boolean isValueEmpty() {
221+
return value_index < 0;
222+
}
223+
224+
public boolean isChildFull() {
225+
boolean result = true;
226+
for (int i = 0; i < size(); i += 2) {
227+
if (values[i] == null) {
228+
result = false;
229+
}
230+
}
231+
return result;
232+
}
233+
234+
public boolean isChildEmpty() {
235+
boolean result = true;
236+
for (int i = 1; i < size(); i += 2) {
237+
if (values[i] != null) {
238+
result = false;
239+
}
240+
}
241+
return result;
242+
}
243+
244+
public boolean addChild(int index, BTreeNode<T> child) {
245+
Preconditions.checkPositionIndex(index, CAPACITY);
246+
Preconditions.checkArgument(index % 2 == 0, "wrong index");
247+
extend(index);
248+
if (isChildFull()) return false;
249+
for (int i = size() - 1; i >= index; i -= 2) {
250+
if (values[i] != null) {
251+
// values[i] =
252+
}
253+
}
254+
255+
values[index] = child;
256+
return false;
257+
}
258+
259+
/**
260+
* 按照排序的顺序把元素插入数组中
261+
*
262+
* @param value
263+
* @return 插入的位置，这样好确定子节点的位置
264+
*/
265+
public int appendValue(T value) {
266+
if (isValueFull()) return -1;
267+
extend(value_index + 2);
268+
269+
int last_empty = -1;
270+
//从头开始首先压缩节点，然后再插入
271+
for (int i = 1; i < size(); i += 2) {
272+
if (getValue(i) == null && last_empty == -1) {
273+
last_empty = i;
274+
} else if (last_empty != -1 && getValue(i) != null) {
275+
values[last_empty] = values[i];
276+
values[i] = null;
277+
while (getValue(last_empty) != null) {
278+
last_empty++;
279+
}
280+
}
281+
}
282+
value_index = last_empty;
283+
//节点为空
284+
if (last_empty == 1) {
285+
values[last_empty] = value;
286+
value_index = last_empty;
287+
return last_empty;
288+
}
289+
290+
int last_pos = -1;
291+
for (int i = last_empty - 2; i > 0; i -= 2) {
292+
if (getValue(i).compareTo(value) >= 0) {
293+
last_pos = i;
294+
values[i + 2] = values[i];
295+
} else {
296+
values[i + 2] = value;
297+
return i + 2;
298+
}
299+
}
300+
301+
if (last_pos > 0) {
302+
values[last_pos] = value;
303+
}
304+
return -1;
305+
306+
}
307+
308+
309+
public void setValue(int index, T ele) {
310+
Preconditions.checkPositionIndex(index, CAPACITY);
311+
Preconditions.checkArgument(index % 2 == 1, "wrong index");
312+
extend(index);
313+
314+
values[index] = ele;
315+
}
316+
317+
public void setChild(int index, BTreeNode<T> child) {
318+
Preconditions.checkPositionIndex(index, CAPACITY);
319+
Preconditions.checkArgument(index % 2 == 0, "wrong index");
320+
extend(index);
321+
322+
values[index] = child;
323+
}
324+
325+
public T deleteValue(int index) {
326+
T result = getValue(index);
327+
setValue(index, null);
328+
return result;
329+
}
330+
331+
public BTreeNode<T> deleteChild(int index) {
332+
BTreeNode<T> result = getChild(index);
333+
setChild(index, null);
334+
return result;
335+
}
336+
337+
}
76338
}

‎src/main/java/ssj/algorithm/lang/Tuple2.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,14 @@ public String toString() {
2929
return to_string;
3030
}
3131

32+
public static <F, S> Tuple2<F, S> empty() {
33+
return new Tuple2<>(null, null);
34+
}
35+
36+
public boolean isEmpty() {
37+
return getFirst() == null && getSecond() == null;
38+
}
39+
3240
@Override
3341
public boolean equals(Object o) {
3442
if (this == o) return true;

0 commit comments

Comments
 (0)
0