B树的Java实现
时间: 2023-06-21 11:22:07 浏览: 74
B树是一种自平衡的搜索树,常用于数据库和文件系统等数据结构中。在Java中,我们可以使用以下方式实现B树:
1. 定义B树节点类:
```
public class BTreeNode {
public int[] keys; // 节点存储的关键字数组
public int t; // 最小度数
public BTreeNode[] children; // 子节点数组
public int n; // 节点关键字个数
public boolean leaf; // 是否为叶子节点
public BTreeNode(int t, boolean leaf) {
this.t = t;
this.leaf = leaf;
this.keys = new int[2 * t - 1];
this.children = new BTreeNode[2 * t];
this.n = 0;
}
}
```
2. 定义B树类:
```
public class BTree {
private BTreeNode root; // B树根节点
private int t; // 最小度数
public BTree(int t) {
this.t = t;
this.root = null;
}
// 插入关键字
public void insert(int key) {
if (root == null) {
root = new BTreeNode(t, true);
root.keys[0] = key;
root.n = 1;
} else {
if (root.n == 2 * t - 1) { // 根节点已满,需要分裂
BTreeNode newRoot = new BTreeNode(t, false);
newRoot.children[0] = root;
splitChild(newRoot, 0, root);
int i = 0;
if (newRoot.keys[0] < key) {
i++;
}
insertNonFull(newRoot.children[i], key);
root = newRoot;
} else {
insertNonFull(root, key);
}
}
}
// 插入关键字(非满节点)
private void insertNonFull(BTreeNode node, int key) {
int i = node.n - 1;
if (node.leaf) {
while (i >= 0 && node.keys[i] > key) {
node.keys[i + 1] = node.keys[i];
i--;
}
node.keys[i + 1] = key;
node.n++;
} else {
while (i >= 0 && node.keys[i] > key) {
i--;
}
i++;
if (node.children[i].n == 2 * t - 1) { // 子节点已满,需要分裂
splitChild(node, i, node.children[i]);
if (node.keys[i] < key) {
i++;
}
}
insertNonFull(node.children[i], key);
}
}
// 分裂子节点
private void splitChild(BTreeNode parent, int i, BTreeNode node) {
BTreeNode newNode = new BTreeNode(t, node.leaf);
newNode.n = t - 1;
for (int j = 0; j < t - 1; j++) {
newNode.keys[j] = node.keys[j + t];
}
if (!node.leaf) {
for (int j = 0; j < t; j++) {
newNode.children[j] = node.children[j + t];
}
}
node.n = t - 1;
for (int j = parent.n; j >= i + 1; j--) {
parent.children[j + 1] = parent.children[j];
}
parent.children[i + 1] = newNode;
for (int j = parent.n - 1; j >= i; j--) {
parent.keys[j + 1] = parent.keys[j];
}
parent.keys[i] = node.keys[t - 1];
parent.n++;
}
// 查找关键字
public boolean search(int key) {
return search(root, key);
}
private boolean search(BTreeNode node, int key) {
int i = 0;
while (i < node.n && key > node.keys[i]) {
i++;
}
if (i < node.n && key == node.keys[i]) {
return true;
}
if (node.leaf) {
return false;
}
return search(node.children[i], key);
}
}
```
3. 测试B树:
```
public class Test {
public static void main(String[] args) {
BTree bTree = new BTree(3);
bTree.insert(1);
bTree.insert(3);
bTree.insert(7);
bTree.insert(10);
bTree.insert(11);
bTree.insert(13);
bTree.insert(14);
bTree.insert(15);
bTree.insert(18);
bTree.insert(16);
bTree.insert(19);
bTree.insert(24);
bTree.insert(25);
bTree.insert(26);
bTree.insert(21);
bTree.insert(4);
bTree.insert(5);
bTree.insert(20);
bTree.insert(22);
bTree.insert(2);
bTree.insert(17);
bTree.insert(12);
System.out.println(bTree.search(15)); // true
System.out.println(bTree.search(27)); // false
}
}
```