算法导论之第十八章-B树_b+树 算法导论

B树就是个树，和二叉树的区别是，二叉树只能有两个子节点，所以二叉树的劣势在于深度过深了
二叉树有点分治法里的二分，而B树就有点彻底的分治法的意思了
B树的内节点(即非叶节点)上也是有值的，为关键字，关键字的值是要有顺序的(我的代码里默认升序，关键字的值只是一个整数，其实可以保存对象)
B树的关键字个数不是随意的
1)我们有一个度数用t来表示，t>=2
2)关键字的个数m，m>=t-1,m<=2t-1,根节点不受限制最小限制，如果非叶节点，子节点个数为关键字个数+1
3)当关键字的个数m=2t-1时，这就是个满节点
4)每个叶节点要有相同的深度

要满足上面这些要求，所以添加和删除节点时就不能随意
添加：
1)添加只能添加到叶节点上，如果添加之后，改节点的关键字个数未超过限制，则结束
2)如果关键字个数为2*t个，提取第t个数字，将节点分割成两个节点，第t个数插入父节点中为关键字，如果此时父节点也关键字数溢出，再进行分割，直至结束

删除：
1)如果删除的值不存在，则不进行删除
2)如果删除的值在内节点上，将最邻近改节点的叶节点关键字(即该关键字左侧节点的最右子节点的最右子节点的…最右关键字 或 右侧节点的最左子节点的最左子节点的…最左关键字,我之所以选择左侧节点左右关键字，是因为我关键字是按数组存储，删除最右比删除最左简单很多)赋值到该节点，删除该邻近关键字，此时操作和3)一致
3)如果删除之后的关键字数不小于t-1个，就结束否则执行4)
4)找兄弟节点，如果兄弟节点大于t-1个，问兄弟节点借一个关键字(不是直接借，兄弟节点的值给父节点中两人的夹位，去此处的关键字，给自己)，如果兄弟节点为t-1个关键字，执行5)
5)合并自己与兄弟节点，把两者夹位数也拿下来，组成新的节点，此时父节点会少一个关键字，判断父节点的后续操作(循环3、4、5)

附：不知道别的是用数组还是链表，查找时候没有用更快的二分查找，想着数组长度也不长，就直接顺序查找
因为书中只讲了B树没有讲B+树，所以就没B+的代码实现，有机会的话之后再实现
B+树与B树的区别：
最大区别在于，B+树所有的数据存在叶节点上，其他没有本质区别

红黑树：https://blog.csdn.net/qq_33321609/article/details/86702550
感觉红黑树最难，旋转就转死我了(数个月前写的，我现在看着都看不懂了)

效率分析
B树
取t值为30时
插入100w条数据，耗时227ms
删除0-100w数值各一次，耗时89ms
取t值为2时
插入100w条数据，耗时709ms
删除0-100w数值各一次，耗时142ms
红黑树
插入100w条数据，耗时935ms
删除0-100w数值各一次，耗时220ms
红黑树和B树t取值为2时相近
而且B树在内存使用上更少

当然，这些比较都是我的代码，所以不具有权威
这些都比数组和链表快
数组慢在于插入和删除(查询可以使用二分查找)，链表在查询时候会慢(无论插入还是删除，都要先查询在哪操作)

代码实现：
Tree类

import java.util.ArrayList;
import java.util.List;

public class Tree {

    int t = 0;
    int num = 0;
    int[] keys;
    Tree[] children;
    boolean haveCh;

    public Tree(int t) {
        this.t = t;
        keys = new int[2 * t];
        children = new Tree[2 * t + 1];
    }

    public Tree(int t, int[] keys, int sta, int end) {
        this(t);
        for (int i = sta; i <= end; i++) {
            this.keys[num++] = keys[i];
        }
    }

    public Tree(int t, int[] keys, int sta, int end, Tree[] children) {
        this(t);
        haveCh = true;
        for (int i = sta; i <= end; i++) {
            this.children[num] = children[i];
            this.keys[num++] = keys[i];
        }
        this.children[num] = children[end + 1];
    }

    public AddReNode add(int value) {
        if (!haveCh) {
            //如果没有子节点
            int i = 0;
            for (; i < num; i++) {
                if (keys[i] >= value) {
                    for (int j = num; j > i; j--) {
                        keys[j] = keys[j - 1];
                    }
                    break;
                }
            }
            keys[i] = value;
            num++;
            //如果关键字个数过多
            if (num == 2 * t) {
                //把节点分成两个节点
                AddReNode addReNode = new AddReNode();
                addReNode.key = keys[t];
                addReNode.trees[0] = new Tree(t, keys, 0, t - 1);
                addReNode.trees[1] = new Tree(t, keys, t + 1, 2 * t - 1);
                this.keys[0] = keys[t];
                this.children[0] = addReNode.trees[0];
                this.children[1] = addReNode.trees[1];
                this.num = 1;
                this.haveCh = true;
                return addReNode;
            } else {
                return null;
            }
        } else {
            //如果有子节点
            int i = 0;
            for (; i < num; i++) {
                if (keys[i] >= value) {
                    break;
                }
            }
            //在子节点上添加
            AddReNode addReNode = children[i].add(value);
            if (addReNode != null) {
                //如果子节点添加后分裂
                for (int j = num; j > i; j--) {
                    keys[j] = keys[j - 1];
                    children[j + 1] = children[j];
                }
                keys[i] = addReNode.key;
                children[i] = addReNode.trees[0];
                children[i + 1] = addReNode.trees[1];
                num++;
                //分裂
                if (num == 2 * t) {
                    AddReNode nddReNode = new AddReNode();
                    nddReNode.key = keys[t];
                    nddReNode.trees[0] = new Tree(t, keys, 0, t - 1, children);
                    nddReNode.trees[1] = new Tree(t, keys, t + 1, 2 * t - 1, children);
                    this.keys[0] = keys[t];
                    this.children[0] = nddReNode.trees[0];
                    this.children[1] = nddReNode.trees[1];
                    this.num = 1;
                    this.haveCh = true;
                    return nddReNode;
                }
            }
            return null;
        }
    }

    //删除
    public boolean delete(int value) {
        int all = num;
        int i = 0;
        for (; i < num; i++) {
            if (value < keys[i]) {
                if (haveCh) {
                    boolean b = children[i].delete(value);
                    if (b) {
                        //找右兄弟
                        this.removeRight(i);
                    }
                }
                break;
            }
            if (value == keys[i]) {
                if (!haveCh) {
                    for (int j = i; j < num - 1; j++) {
                        keys[j] = keys[j + 1];
                    }
                    num--;
                    break;
                }
                Tree leftRight = getRight(children[i]);
                keys[i] = leftRight.keys[leftRight.num - 1];
                boolean b = children[i].removeRight();
                if (b) {
                    //确保有有兄弟，所以找由兄弟
                    this.removeRight(i);
                }
                break;
            }
        }
        //说明前面一直没有删，那就再去判断最右一个child
        if (i == all) {
            if (haveCh) {
                boolean b = children[num].delete(value);
                if (b) {
                    //找最右节点的左兄弟
                    this.removeTopLeft();
                }
            }
        }
        return num < t - 1;
    }

    //如果节点数不够，和右节点合并或者借
    private void removeRight(int key) {
        if (children[key + 1].num == t - 1) {
            //不够，合并
            children[key].num += 1 + t - 1;
            children[key].keys[t - 2] = keys[key];
            for (int j = 0; j < t - 1; j++) {
                children[key].keys[t - 1 + j] = children[key + 1].keys[j];
                children[key].children[t - 1 + j] = children[key + 1].children[j];
            }
            children[key].children[2 * t - 2] = children[key + 1].children[t - 1];
            //后面的要移过来
            for (int j = key; j < num - 1; j++) {
                keys[j] = keys[j + 1];
                children[j+1] = children[j + 2];
            }
            num--;
        } else {
            //如果右侧的兄弟节点够，就借
            children[key].num++;
            children[key].keys[children[key].num - 1] = keys[key];
            children[key].children[children[key].num] = children[key + 1].children[0];
            keys[key] = children[key + 1].keys[0];
            children[key + 1].removeLeft();
        }
    }

    //删除最右的关键字
    private boolean removeRight() {
        if (haveCh) {
            boolean b = children[num].removeRight();
            if (b) {
                //因为没有右兄弟，所以找左兄弟
                this.removeTopLeft();
            }
        } else {
            num--;
        }
        return num < t - 1;
    }

    //虽然叫TopLeft，其实是删除最右的节点，如果节点数不够，和其左节点合并
    private void removeTopLeft() {

        if (children[num - 1].num == t - 1) {
            //如果兄弟节点恰好是最少值，就进行合并
            children[num - 1].num += 1 + t - 2;
            children[num - 1].keys[t - 1] = keys[num - 1];
            for (int i = 0; i < t - 2; i++) {
                children[num - 1].keys[t + i] = children[num].keys[i];
                children[num - 1].children[t + i] = children[num].children[i];
            }
            children[num - 1].children[2 * t - 2] = children[num].children[t - 2];
            num--;
        } else {
            //问兄弟节点借一个
            children[num - 1].num--;
            int newChN = children[num - 1].num;
            children[num].addLeft(keys[num - 1], children[num - 1].children[newChN + 1]);
            keys[num - 1] = children[num - 1].keys[newChN];
        }
    }

    //问左兄弟借来的节点
    private void addLeft(int key, Tree node) {
        num++;
        children[num] = children[num - 1];
        for (int i = num - 1; i >= 1; i--) {
            keys[i] = keys[i - 1];
            children[i] = children[i - 1];
        }
        keys[0] = key;
        children[0] = node;
    }

    //把最左的节点借给左兄弟
    private void removeLeft() {
        for (int i = 0; i < num - 1; i++) {
            keys[i] = keys[i + 1];
            children[i] = children[i + 1];
        }
        num--;
        children[num] = children[num + 1];
    }

    //获取最右的(因为使用数组，从右侧删除，方便)
    private Tree getRight(Tree tree) {
        if (tree.haveCh) {
            return getRight(tree.children[tree.num]);
        }
        return tree;
    }

    //获取所有节点
    public static List<Integer> show(Tree tree) {
        List<Integer> ans = new ArrayList<>();
        if (tree == null) {
            return ans;
        }
        if (tree.haveCh) {
            for (int i = 0; i < tree.num; i++) {
                ans.addAll(show(tree.children[i]));
                ans.add(tree.keys[i]);
            }
            ans.addAll(show(tree.children[tree.num]));
        } else {
            for (int i = 0; i < tree.num; i++) {
                ans.add(tree.keys[i]);
            }
        }
        return ans;
    }

    //校验关键字的数目
    public static void checkTree(Tree tree, boolean ifTop) {
        if (tree.num > 2 * tree.t - 1) {
            System.out.println("存在关键字过多");
        }
        if (!ifTop) {
            if (tree.num < tree.t - 1) {
                System.out.println("存在关键字过少");
            }
        }
    }

    //树的深度
    public static int deep(Tree tree) {
        if (tree.haveCh) {
            return 1 + deep(tree.children[0]);
        }
        return 1;
    }

    class AddReNode {
        int key;
        Tree[] trees = new Tree[2];
    }
}
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
285
286

Test类

public class Test {

    public static void main(String[] args) {
        Tree tree = new Tree(30);
        Random random = new Random();
        for (int i = 0; i < 1000000; i++) {
            int v = random.nextInt(1000000);
            tree.add(v);
        }
        System.out.println("插入结束");
        List<Integer> ans = Tree.show(tree);
        //System.out.println(ans);
        System.out.println(Tree.deep(tree));
        System.out.println(ans.size());
        for (int i = 1; i < ans.size(); i++) {
            if (ans.get(i) < ans.get(i - 1)) {
                System.out.println("顺序有误");
            }
        }
        Tree.checkTree(tree, true);
        System.out.println("开始删除");
        //int len = ans.size();
        for (int i = 0; i < 1000000; i++) {
            tree.delete(i);
            if (tree.num == 0) {
                tree = tree.children[0];
            }
            /*ans = Tree.show(tree);
            int dl = len-ans.size();
            if(dl>1){
                System.out.println("删除个数超过1");
            }
            len = ans.size();
            for (int j = 1; j < ans.size(); j++) {
                if (ans.get(j) < ans.get(j - 1)) {
                    System.out.println("顺序有误");
                }
            }*/
        }

        System.out.println(Tree.deep(tree));
        ans = Tree.show(tree);
        System.out.println(ans.size());
        for (int i = 1; i < ans.size(); i++) {
            if (ans.get(i) < ans.get(i - 1)) {
                System.out.println("顺序有误");
            }
        }
        Tree.checkTree(tree, true);

        /*int deep = Tree.deep(tree);
        while(Tree.deep(tree)==deep){
            for (int i = 0; i < 1000000; i++) {
                tree.delete(i);
                if (tree.num == 0) {
                    tree = tree.children[0];
                }
            }
            System.out.println(Tree.deep(tree));
            ans = Tree.show(tree);
            System.out.println(ans.size());
        }
        deep = Tree.deep(tree);
        while(Tree.deep(tree)==deep){
            for (int i = 0; i < 1000000; i++) {
                tree.delete(i);
                if (tree.num == 0) {
                    tree = tree.children[0];
                }
            }
            System.out.println(Tree.deep(tree));
            ans = Tree.show(tree);
            System.out.println(ans.size());
        }
        deep = Tree.deep(tree);
        while(Tree.deep(tree)==deep){
            for (int i = 0; i < 1000000; i++) {
                tree.delete(i);
                if (tree.num == 0) {
                    tree = tree.children[0];
                }
            }
            System.out.println(Tree.deep(tree));
            ans = Tree.show(tree);
            System.out.println(ans.size());
        }
        ans = Tree.show(tree);
        System.out.println(ans);*/
    }
}
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