Repository navigation
Expand file tree
/
Copy pathBTreeNode.java
More file actions
155 lines (112 loc) · 4.01 KB
/
Copy pathBTreeNode.java
File metadata and controls
155 lines (112 loc) · 4.01 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
enum TreeNodeType {
InnerNode,
LeafNode
}
abstract class BTreeNode<TKey extends Comparable<TKey>> {
protected Object[] keys;
protected int keyCount;
protected BTreeNode<TKey> parentNode;
protected BTreeNode<TKey> leftSibling;
protected BTreeNode<TKey> rightSibling;
protected BTreeNode() {
this.keyCount = 0;
this.parentNode = null;
this.leftSibling = null;
this.rightSibling = null;
}
public int getKeyCount() {
return this.keyCount;
}
@SuppressWarnings("unchecked")
public TKey getKey(int index) {
return (TKey)this.keys[index];
}
public void setKey(int index, TKey key) {
this.keys[index] = key;
}
public BTreeNode<TKey> getParent() {
return this.parentNode;
}
public void setParent(BTreeNode<TKey> parent) {
this.parentNode = parent;
}
public abstract TreeNodeType getNodeType();
/**
* Search a key on current node, if found the key then return its position,
* otherwise return -1 for a leaf node,
* return the child node index which should contain the key for a internal node.
*/
public abstract int search(TKey key);
/* The codes below are used to support insertion operation */
public boolean isOverflow() {
return this.getKeyCount() == this.keys.length;
}
public BTreeNode<TKey> dealOverflow() {
int midIndex = this.getKeyCount() / 2;
TKey upKey = this.getKey(midIndex);
BTreeNode<TKey> newRNode = this.split();
if (this.getParent() == null) {
this.setParent(new BTreeInnerNode<TKey>());
}
newRNode.setParent(this.getParent());
// maintain links of sibling nodes
newRNode.setLeftSibling(this);
newRNode.setRightSibling(this.rightSibling);
if (this.getRightSibling() != null)
this.getRightSibling().setLeftSibling(newRNode);
this.setRightSibling(newRNode);
// push up a key to parent internal node
return this.getParent().pushUpKey(upKey, this, newRNode);
}
protected abstract BTreeNode<TKey> split();
protected abstract BTreeNode<TKey> pushUpKey(TKey key, BTreeNode<TKey> leftChild, BTreeNode<TKey> rightNode);
/* The codes below are used to support deletion operation */
public boolean isUnderflow() {
return this.getKeyCount() < (this.keys.length / 2);
}
public boolean canLendAKey() {
return this.getKeyCount() > (this.keys.length / 2);
}
public BTreeNode<TKey> getLeftSibling() {
if (this.leftSibling != null && this.leftSibling.getParent() == this.getParent())
return this.leftSibling;
return null;
}
public void setLeftSibling(BTreeNode<TKey> sibling) {
this.leftSibling = sibling;
}
public BTreeNode<TKey> getRightSibling() {
if (this.rightSibling != null && this.rightSibling.getParent() == this.getParent())
return this.rightSibling;
return null;
}
public void setRightSibling(BTreeNode<TKey> silbling) {
this.rightSibling = silbling;
}
public BTreeNode<TKey> dealUnderflow() {
if (this.getParent() == null)
return null;
// try to borrow a key from sibling
BTreeNode<TKey> leftSibling = this.getLeftSibling();
if (leftSibling != null && leftSibling.canLendAKey()) {
this.getParent().processChildrenTransfer(this, leftSibling, leftSibling.getKeyCount() - 1);
return null;
}
BTreeNode<TKey> rightSibling = this.getRightSibling();
if (rightSibling != null && rightSibling.canLendAKey()) {
this.getParent().processChildrenTransfer(this, rightSibling, 0);
return null;
}
// Can not borrow a key from any sibling, then do fusion with sibling
if (leftSibling != null) {
return this.getParent().processChildrenFusion(leftSibling, this);
}
else {
return this.getParent().processChildrenFusion(this, rightSibling);
}
}
protected abstract void processChildrenTransfer(BTreeNode<TKey> borrower, BTreeNode<TKey> lender, int borrowIndex);
protected abstract BTreeNode<TKey> processChildrenFusion(BTreeNode<TKey> leftChild, BTreeNode<TKey> rightChild);
protected abstract void fusionWithSibling(TKey sinkKey, BTreeNode<TKey> rightSibling);
protected abstract TKey transferFromSibling(TKey sinkKey, BTreeNode<TKey> sibling, int borrowIndex);
}