8000 完成B树插入并且通过测试。 · sswssx/javaalgorithm@1c1f4d0 · GitHub
[go: up one dir, main page]
Skip to content

Commit 1c1f4d0

Browse files
author
shengshijun
committed
完成B树插入并且通过测试。
1 parent e00f483 commit 1c1f4d0

File tree

2 files changed

+103
-112
lines changed

2 files changed

+103
-112
lines changed

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

Lines changed: 99 additions & 109 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,9 @@
33
import com.google.common.base.Preconditions;
44
import ssj.algorithm.SearchTree;
55
import ssj.algorithm.lang.Tuple2;
6+
import ssj.algorithm.string.StringBuilder;
67

8+
import java.util.Arrays;
79
import java.util.Iterator;
810

911
/**
@@ -21,6 +23,7 @@ private BTree(int degree) {
2123
tree_degree = degree;
2224
tree_size = 0;
2325
root = new BTreeNode<>(tree_degree);
26+
root.setLeaf(true);
2427
}
2528

2629
public static <T extends Comparable<? super T>> BTree<T> degreeOf(int degree) {
@@ -36,23 +39,13 @@ public void add(T ele) {
3639
Preconditions.checkNotNull(ele);
3740

3841
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-
}
42+
while (!leaf_node.isLeaf()) {
43+
BTreeNode<T> tmp = leaf_node.searchChild(ele);
5244

53-
if (leaf_node.isValueFull() && cur_node != null) {
45+
if (leaf_node.isValueFull()) {
5446
splitNode(leaf_node, null);
5547
}
48+
leaf_node = tmp;
5649
}
5750

5851
if (leaf_node.isValueFull()) {
@@ -73,26 +66,22 @@ private Tuple2<BTreeNode<T>, BTreeNode<T>> splitNode(BTreeNode<T> node, T insert
7366
root = parent_node;
7467
}
7568
right_node.setParent(parent_node);
69+
node.setParent(parent_node);
7670

77-
//中间节点插入父节点，子节点的中点在degree－1。因为从0开始计数，所以需要减一
78-
int mid_index = parent_node.appendValue(node.deleteValue(node.size() / 2));
71+
// System.out.println("parent : " + parent_node);
72+
// System.out.println("insert ele : " + insert_ele);
73+
// System.out.println("middle node : " + node.getValue(node.size() / 2));
74+
int mid_index = parent_node.appendValue(node.getValue(node.size() / 2));
75+
// System.out.println("middle index : " + mid_index);
7976
parent_node.setChild(mid_index - 1, node);
8077
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-
}
78+
node.splitNode(right_node);
9079

9180
if (insert_ele != null) {
9281
if (parent_node.getValue(mid_index).compareTo(insert_ele) > 0) {
93-
right_node.appendValue(insert_ele);
94-
} else {
9582
node.appendValue(insert_ele);
83+
} else {
84+
right_node.appendValue(insert_ele);
9685
}
9786
}
9887

@@ -162,13 +151,22 @@ private static class BTreeNode<T extends Comparable<? super T>> {
162151
private Object[] values;
163152
private BTreeNode<T> parent;
164153
private int value_index = -1;
154+
private boolean isLeaf;
165155

166156
public BTreeNode(int degree) {
167157
this.DEGREE = degree;
168158
HALF_CAPACITY = 2 * DEGREE - 1;
169159
CAPACITY = 4 * DEGREE - 1;
170160
}
171161

162+
public boolean isLeaf() {
163+
return isLeaf;
164+
}
165+
166+
public void setLeaf(boolean isLeaf) {
167+
this.isLeaf = isLeaf;
168+
}
169+
172170
public BTreeNode<T> getParent() {
173171
return parent;
174172
}
@@ -187,7 +185,15 @@ private void extend(int expect) {
187185
} else if (values == null) {
188186
values = new Object[HALF_CAPACITY];
189187
}
188+
}
190189

190+
private void fullLeaf(int index) {
191+
if (values[index] == null && !isLeaf()) {
192+
BTreeNode<T> new_child = new BTreeNode<>(DEGREE);
193+
new_child.setParent(this);
194+
new_child.setLeaf(true);
195+
values[index] = new_child;
196+
}
191197
}
192198

193199
@SuppressWarnings("unchecked")
@@ -208,54 +214,23 @@ public T getValue(int index) {
208214
return (T) values[index];
209215
}
210216

211-
public int size() {
217+
public int capacity() {
212218
extend(1);
213219
return values.length;
214220
}
215221

222+
public int size() {
223+
return (value_index + 2);
224+
}
225+
216226
public boolean isValueFull() {
217-
return size() == CAPACITY && value_index == CAPACITY - 2;
227+
return capacity() == CAPACITY && value_index == CAPACITY - 2;
218228
}
219229

220230
public boolean isValueEmpty() {
221231
return value_index < 0;
222232
}
223233

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-
259234
/**
260235
* 按照排序的顺序把元素插入数组中
261236
*
@@ -266,54 +241,21 @@ public int appendValue(T value) {
266241
if (isValueFull()) return -1;
267242
extend(value_index + 2);
268243

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;
244+
int insert_index = value_index + 2;
245+
for (int i = value_index; i >= 1 && getValue(i).compareTo(value) >= 0; i -= 2, insert_index -= 2) {
246+
if (value_index == i) {
247+
values[i + 3] = values[i + 1];
298248
}
249+
values[i + 2] = values[i];
250+
values[i + 1] = values[i - 1];
299251
}
252+
values[insert_index] = value;
253+
value_index += 2;
300254

301-
if (last_pos > 0) {
302-
values[last_pos] = value;
303-
}
304-
return -1;
305-
255+
return insert_index;
306256
}
307257

308258

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< E377 code class="diff-text syntax-highlighted-line deletion">-
317259
public void setChild(int index, BTreeNode<T> child) {
318260
Preconditions.checkPositionIndex(index, CAPACITY);
319261
Preconditions.checkArgument(index % 2 == 0, "wrong index");
@@ -322,9 +264,10 @@ public void setChild(int index, BTreeNode<T> child) {
322264
values[index] = child;
323265
}
324266

325-
public T deleteValue(int index) {
326-
T result = getValue(index);
327-
setValue(index, null);
267+
public T popValue() {
268+
T result = getValue(value_index);
269+
values[value_index] = null;
270+
value_index -= 2;
328271
return result;
329272
}
330273

@@ -334,5 +277,52 @@ public BTreeNode<T> deleteChild(int index) {
334277
return result;
335278
}
336279

280+
public BTreeNode<T> searchChild(T value) {
281+
for (int i = 1; i < size(); i += 2) {
282+
int cmp_res = getValue(i).compareTo(value);
283+
//如果非空，那么是最后一个子节点
284+
if (cmp_res < 0 && i == size() - 2) {
285+
fullLeaf(i + 1);
286+
return getChild(i + 1);
287+
} else if (cmp_res >= 0) {
288+
fullLeaf(i - 1);
289+
return getChild(i - 1);
290+
}
291+
}
292+
return null;
293+
}
294+
295+
/**
296+
* 把一半元素移动到新到节点中
297+
*
298+
* @param other
299+
*/
300+
public void splitNode(BTreeNode<T> other) {
301+
Preconditions.checkNotNull(other);
302+
other.extend(HALF_CAPACITY);
303+
System.arraycopy(values, CAPACITY / 2 + 1, other.values, 0, CAPACITY / 2);
304+
Arrays.fill(values, CAPACITY / 2, CAPACITY, null);
305+
value_index = CAPACITY / 2 - 2;
306+
other.value_index = CAPACITY / 2 - 2;
307+
other.setLeaf(isLeaf());
308+
for (int i = 0; i < other.size(); i += 2) {
309+
if (other.getChild(i) != null) {
310+
other.getChild(i).setParent(other);
311+
}
312+
}
313+
}
314+
315+
@Override
316+
public String toString() {
317+
ssj.algorithm.string.StringBuilder sb = new StringBuilder("[");
318+
for (int i = 1; i < size(); i += 2) {
319+
sb.append(getValue(i));
320+
if (i != size() - 2) {
321+
sb.append(",");
322+
}
323+
}
324+
sb.append("]");
325+
return sb.toString();
326+
}
337327
}
338328
}

‎src/test/java/ssj/algorithm/collections/BTreeTest.java

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,9 +12,10 @@ public class BTreeTest {
1212
@Test
1313
public void testBasic() {
1414
BTree<Integer> tree = BTree.degreeOf(2);
15-
int[] data = MathUtil.randUniqueInt(0, 100, 4);
16-
// int[] data = new int[]{34,9};
17-
System.out.println();
15+
// int[] data = new int[]{55, 34, 0, 21, 8, 47, 29, 26, 5, 60, 94, 58, 31, 24, 10, 79, 11, 57, 32, 36, 53, 2, 70, 6, 83, 49, 28, 96, 75, 35, 56, 77, 98, 80, 59, 85, 30, 4, 51, 72};
16+
// int[] data = new int[]{55, 34, 0, 21, 8, 47, 29, 26,5, 60, 94,58};
17+
int[] data = MathUtil.randUniqueInt(0, 100000, 400);
18+
System.out.println(Arrays.toString(data));
1819
for (int i : data) {
1920
tree.add(i);
2021
}

0 commit comments

Comments
 (0)
0