数据结构-b树

import java.util.Arrays;

/**
 * @author ddq
 */
@SuppressWarnings("all")
public class BTree {
    private class Node {
        private int[] keys;
        private int size;
        private Node[] children;

        private boolean isLeaf;

        private Node(int capacity) {
            keys = new int[capacity];
            children = new Node[capacity + 1];
        }

        private Node() {
            this(2);
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOf(keys, size));
        }
    }

    private Node root;

    //btree中最小的度
    private int minBranch;

    //btree每个节点允许最小的key数量
    private int minKeyThreshold;

    //btree每个节点允许最大的key数量
    private int maxKeyThreshold;

    private static enum MOVE_TYPE {
        MOVE_TO_LEFT, MOVE_TO_RIGHT;
    }

    public BTree(int minBranch) {
        this.minBranch = minBranch;
        this.minKeyThreshold = minBranch - 1;
        this.maxKeyThreshold = 2 * minBranch - 1;
        this.root = new Node(maxKeyThreshold);
        this.root.isLeaf = true;
    }

    public BTree() {
        this(2);
    }

    public boolean contains(int key) {
        return doContains(root, key);
    }

    private boolean doContains(Node node, int key) {
        int i = 0;
        while (i < node.size) {
            if (key == node.keys[i]) return true;
            if (key < node.keys[i]) break;
            i++;
        }
        if (node.isLeaf) return false;
        return doContains(node.children[i], key);
    }

    private void doPut(Node parent, Node node, int key, int index) {
        int i = 0;
        while (i < node.size) {
            if (key == node.keys[i]) return;
            if (key < node.keys[i]) break;
            i++;
        }
        //如果是叶子节点则直接添加
        if (node.isLeaf) addKey(node, key);
        else doPut(node, node.children[i], key, i);
        split(parent, node, index);
    }

    private void split(Node parent, Node node, int index) {
        if (node.size < maxKeyThreshold) return;
        //一会儿准备往父节点移动的数据
        int mid = node.keys[minBranch - 1];
        //原节点，为了更好的区分，故取别名left
        Node left = node;
        //新节点，为了更好的区分，故取别名right
        Node right = createNewNode(maxKeyThreshold, left.isLeaf);
        shareKeys(left, minBranch, right, 0, left.size - minBranch);
        shareChildren(left, minBranch, right, 0, minBranch);
        parent = checkParent(parent);
        addKey(parent, mid);
        addChild(parent, left, index);
        addChild(parent, right, index + 1);
    }

    private Node createNewNode(int capacity, boolean isLeaf) {
        Node node = new Node(capacity);
        node.isLeaf = isLeaf;
        return node;
    }

    private void addChild(Node parent, Node child, int index) {
        System.arraycopy(parent.children, index, parent.children, index + 1, parent.size - index);
        parent.children[index] = child;
    }

    private Node checkParent(Node parent) {
        if (parent != null) return parent;
        parent = new Node(maxKeyThreshold);
        this.root = parent;
        return parent;
    }

    private void addKey(Node node, int key) {
        int i = 0;
        while (i < node.size) {
            if (key == node.keys[i]) return;
            if (key < node.keys[i]) break;
            i++;
        }
        System.arraycopy(node.keys, i, node.keys, i + 1, node.size - i);
        node.keys[i] = key;
        node.size++;
    }

    private void shareKeys(Node src, int srcPos, Node dest, int destPos, int length) {
        System.arraycopy(src.keys, srcPos, dest.keys, destPos, length);
        dest.size = length;
        src.size = src.size - dest.size - 1;
    }

    private void shareChildren(Node src, int srcPos, Node dest, int destPos, int length) {
        if (src.isLeaf || dest.isLeaf) return;
        System.arraycopy(src.children, srcPos, dest.children, destPos, length);
    }

    public void put(int key) {
        doPut(null, root, key, 0);
    }

    public void remove(int key) {
        doRemove(null, root, key, 0);
    }

    private void doRemove(Node parent, Node node, int key, int index) {
        /**
         * 需要判断当前是否是叶子节点
         * 叶子节点，直接删除
         * 非叶子节点，将后续节点替换到当前节点，然后对后继节点进行递归删除
         * */
        int i = 0;
        if (node.isLeaf) {
            //叶子节点，直接删除
            while (i < node.size) {
                if (key < node.keys[i]) return;
                if (key == node.keys[i]) break;
                i++;
            }
            if (node.size <= i) return;
            removeKeyOfIndex(node, i);
            node.size--;
        } else {
            //非叶子节点，将后续节点替换到当前节点，然后对后继节点进行递归删除
            while (i < node.size) {
                if (key <= node.keys[i]) break;
                i++;
            }
            if (key == node.keys[i]) {
                Node tmp = node.children[i + 1];
                while (tmp.children[0] != null) tmp = tmp.children[0];
                node.keys[i] = tmp.keys[0];
                doRemove(node, node.children[i + 1], tmp.keys[0], i + 1);
            } else {
                doRemove(node, node.children[i], key, i);
            }
        }
        balance(parent, node, index);
    }

    //在对keys进行删减的时候可能会导致 keys数量
    private void balance(Node parent, Node node, int index) {
        if (node.size >= minKeyThreshold) return;
        if (parent == null) {
            this.root = node.children[0];
            return;
        }

        Node leftBrother = index >= 1 ? parent.children[index - 1] : null;
        Node rightBrother = index < parent.size ? parent.children[index + 1] : null;
        if (leftBrother != null && leftBrother.size > minKeyThreshold) {
            //将父节点最后一个key移除并将移除的返回值添加到node
            addKey(node, removeKeyOfIndex(parent, index - 1));
            parent.size--;
            //将左兄弟的最后一个key移除并将移除的返回值添加到parent
            addKey(parent, removeKeyOfIndex(leftBrother, leftBrother.size - 1));
            if (!node.isLeaf) addChild(node, removeChildOfIndex(leftBrother, leftBrother.size), 0);
            leftBrother.size--;

            return;
        }
        if (rightBrother != null && rightBrother.size > minKeyThreshold) {
            //将父节点最后一个key移除并将移除的返回值添加到node
            addKey(node, removeKeyOfIndex(parent, index));
            parent.size--;
            //将右兄弟的第一个key移除并将移除的返回值添加到parent
            addKey(parent, removeKeyOfIndex(rightBrother, 0));
            if (!node.isLeaf) addChild(node, removeChildOfIndex(rightBrother, 0), node.size);
            rightBrother.size--;
            return;
        }
        //如果左兄弟不为null则往左兄弟进行合并
        if (leftBrother != null) {
            //1.先将自己去除掉
            removeChildOfIndex(parent, index);
            //node实际上有效的孩子数为当前node的长度+1，当前的node也就是下一次递归的parent，实际上在下一次递归的时候，当前node的size就已经减1了故孩子数是  size+1 => 现size+1
            int validRightChildSize = node.isLeaf ? 0 : node.size + 1;
            //左兄弟实际上有效的孩子数
            int validLeftChildSize = leftBrother.isLeaf ? 0 : leftBrother.size + 1;
            //2.将父节点index-1位置的key给去除掉且将去除的返回值往左兄弟中添加
            addKey(leftBrother, removeKeyOfIndex(parent, index - 1));
            parent.size--;
            //3.将第1步得到的返回值（包括keys和children）往左兄弟进行合并
            moveToTarget(leftBrother, validLeftChildSize, node, validRightChildSize, MOVE_TYPE.MOVE_TO_LEFT);
            return;
        }
        //如果左兄弟为null则自己向右兄弟合并
        if (rightBrother != null) {
            //1.先将自己去除掉
            removeChildOfIndex(parent, index);
            //node实际上有效的孩子数为当前node的长度+1，当前的node也就是下一次递归的parent，实际上在下一次递归的时候，当前node的size就已经减1了故孩子数是  size+1 => 现size+1
            int validLeftChildSize = node.isLeaf ? 0 : node.size + 1;
            //右兄弟实际上有效的孩子数
            int validRightChildSize = rightBrother.isLeaf ? 0 : rightBrother.size + 1;
            //2.将父节点index-1位置的key给去除掉且将去除的返回值往左兄弟中添加
            addKey(rightBrother, removeKeyOfIndex(parent, index));
            parent.size--;
            moveToTarget(rightBrother, validRightChildSize, node, validLeftChildSize, MOVE_TYPE.MOVE_TO_RIGHT);
            return;
        }

    }

    //将keys和children往target进行合并
    private void moveToTarget(Node dest, int validDestChildSize, Node src, int validSrcChildSize, MOVE_TYPE moveType) {
        //首先进行keys的拷贝
        if (moveType == MOVE_TYPE.MOVE_TO_RIGHT) {
            System.arraycopy(dest.keys, 0, dest.keys, src.size, dest.size);
            System.arraycopy(src.keys, 0, dest.keys, 0, src.size);
            if (!src.isLeaf && !dest.isLeaf) {
                System.arraycopy(dest.children, 0, dest.children, validSrcChildSize, validDestChildSize);
                System.arraycopy(src.children, 0, dest.children, 0, validSrcChildSize);
            }
        } else {
            System.arraycopy(src.keys, 0, dest.keys, dest.size, src.size);
            if (!src.isLeaf && !dest.isLeaf) {
                System.arraycopy(src.children, 0, dest.children, validDestChildSize, validSrcChildSize);
            }
        }
        //如果有效的子节点数量为0，则将该dest置为叶子节点
        if (validDestChildSize + validSrcChildSize == 0) dest.isLeaf = true;
    }

    private Node removeChildOfIndex(Node node, int index) {
        Node removed = node.children[index];
        System.arraycopy(node.children, index + 1, node.children, index, node.size - index);
        node.children[node.size] = null;
        return removed;
    }

    //删除node指定下标的key
    private int removeKeyOfIndex(Node node, int index) {
        int removed = node.keys[index];
        System.arraycopy(node.keys, index + 1, node.keys, index, node.size - index - 1);
        return removed;
    }
}



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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284