对b树相信大家都有一定的了解了，那你们知道b树该如何创建吗?下面快跟小编一起了解了解吧。
b树概念
一棵B树是有着下面几点性质的有根树:
a、每个节点中x有以下域：
1)num,当前存储在节点x的关键字个数,关键字以非降序存放，所以key[i]<=key[i+1]<=……key[n]。
2)isleaf,一个bool值，假如，x为叶子节点，那么，isleaf为true。
3)所有节点当中，包括num+1个指向其子女的指针p[0],p[1],……p[num]。
假如，x为叶子，p就为NULL。
(d)每个节点包括num个关键字key[0],key[1],……key[num-1]。
各关键字key[i]对存储在各子树中的关键字范围加以分隔： k1<=key[1]<=k2<=key[2]……
b、在b树当中，它的每个叶节点有着相同的深度。
c、在b树当中，它的每一个节点包含的关键字有上下界。
在这些界当中，能够用一个叫做b树的最小度数的固定整数M>=2来表示。
所有非根节点的个数n必须满足M-1<=n<=2M-1。
根节点要至少包括一个关键字。
假如，一个节点是满的，那么，它恰好有2M-1个关键字。
b树的创建
实例
创建一个空的b树：
/**********************************************************
函数功能：创建节点
输入：无
输出：新节点
**********************************************************/
BtreeNode * BtreeCreate()
{
BtreeNode * node = (BtreeNode * ) malloc(sizeof(BtreeNode));
if (NULL == node)
return NULL;
node - > isleaf = true;
node - > num = 0;
for (int i = 0; i < 2 * M; i++)
node - > p[i] = NULL;
for (int i = 0; i < 2 * M - 1; i++)
node - > key[i] = 0;
return node;
}java中实现b树操作：
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
public class BTreeextends Comparable >
{
private static final int DEFAULT_T = 2;
private BTNode root;
// 最小度数
private int t;
// 非根节点的最少关键字个数
private int minKeyNum;
// 非根节点的最大关键字个数
private int maxKeyNum;
private class BTNode
{
// 关键字个数
public int n = 0;
public List keys = new ArrayList(maxKeyNum);
public List children = new ArrayList(maxKeyNum + 1);
public boolean isLeaf = true;
public void insertKey(int index, E key)
{
keys.add(index, key);
n++;
if (keys.size() > maxKeyNum)
{
keys.remove(maxKeyNum);
}
}
public E removeKey(int index)
{
E key = keys.remove(index);
n--;
return key;
}
public void insertChild(int index, BTNode child)
{
children.add(index, child);
if (children.size() > maxKeyNum + 1)
{
children.remove(maxKeyNum + 1);
}
}
public BTNode removeChild(int index)
{
BTNode child = children.remove(index);
return child;
}
}
public BTree()
{
this(DEFAULT_T);
}
public BTree(int degree)
{
if (degree < 2)
{
t = DEFAULT_T;
}
this.t = degree;
this.minKeyNum = degree - 1;
this.maxKeyNum = 2 * degree - 1;
BTNode node = new BTNode();
this.root = node;
}
private void sliptChild(BTNode x, int index)
{
// 新增结点
BTNode z = new BTNode();
BTNode y = x.children.get(index);
z.isLeaf = y.isLeaf;
for (int j = 0; j < minKeyNum; j++)
{
z.insertKey(j, y.keys.get(j + t));
}
if (!y.isLeaf)
{
for (int j = 0; j < t; j++)
{
z.insertChild(j, y.children.get(j + t));
}
}
z.n = minKeyNum;
y.n = minKeyNum;
x.insertChild(index + 1, z);
x.insertKey(index, y.keys.get(minKeyNum));
}
private void insertNoFull(BTNode x, E key)
{
int i = x.n - 1;
if (x.isLeaf)
{
while (i >= 0 && key.compareTo(x.keys.get(i)) < 0)
i--;
x.insertKey(i + 1, key);
}
else
{
while (i >= 0 && key.compareTo(x.keys.get(i)) < 0)
i--;
i = i + 1;
if (x.children.get(i)
.n == maxKeyNum)
{
sliptChild(x, i);
if (key.compareTo(x.keys.get(i)) > 0)
i = i + 1;
}
insertNoFull(x.children.get(i), key);
}
}
public void insert(E key)
{
BTNode r = root;
if (root.n == maxKeyNum)
{
BTNode newRoot = new BTNode();
root = newRoot;
newRoot.isLeaf = false;
newRoot.insertChild(0, r);
sliptChild(newRoot, 0);
insertNoFull(newRoot, key);
}
else
insertNoFull(r, key);
}
public void delete(E key)
{
delete(root, key);
}
private void delete(BTNode x, E key)
{
// 该过程需要保证，对非根节点执行删除操作时，其关键字个数至少为t。
int n = x.n;
assert n >= t || x == root;
int i = 0;
while (i < n && key.compareTo(x.keys.get(i)) > 0)
i++;
if (i < n && key.equals(x.keys.get(i)))
{
if (x.isLeaf)
{
// 1 如果当前结点是叶子结点，直接删除关键字
x.removeKey(i);
}
else
{
BTNode y = x.children.get(i);
BTNode z = x.children.get(i + 1);
if (y.n >= t)
{
// 2.a
E preKey = deleteMaxKey(y);
x.keys.set(i, preKey);
}
else if (z.n >= t)
{
// 2.b
E nextKey = deleteMinKey(z);
x.keys.set(i, nextKey);
}
else
{
// 2.c
int ySize = y.n;
int zSize = z.n;
y.insertKey(ySize, key);
ySize++;
boolean isChildLeaf = y.isLeaf;
for (int j = 0; j < zSize; j++)
{
y.insertKey(ySize, z.keys.get(j));
if (!isChildLeaf)
{
y.insertChild(ySize, z.children.get(j));
}
ySize++;
}
if (!isChildLeaf)
{
y.insertChild(ySize, z.children.get(zSize - 1));
}
x.removeKey(i);
x.removeChild(i + 1);
if (x.n == 0)
{
root = y;
}
delete(y, key);
}
}
}
else if (x.isLeaf)
{
// 没有找到该关键字，直接返回
return;
}
else
{
BTNode child = x.children.get(i);
boolean isChildLeaf = child.isLeaf;
if (child.n >= t)
{
delete(child, key);
}
else if (i > 0 && x.children.get(i - 1)
.n >= t)
{
// 3.a 左兄弟满足条件
BTNode leftBrother = x.children.get(i - 1);
int leftBrotherKeyNum = leftBrother.n;
E leftBrotherLastKey = leftBrother.keys.get(leftBrotherKeyNum - 1);
child.insertKey(0, x.keys.get(i - 1));
x.keys.set(i - 1, leftBrotherLastKey);
if (!isChildLeaf)
{
BTNode leftBrotherLastChild = leftBrother.children.get(leftBrotherKeyNum);
child.insertChild(0, leftBrotherLastChild);
leftBrother.removeChild(leftBrotherKeyNum);
}
leftBrother.removeKey(leftBrotherKeyNum - 1);
delete(child, key);
}
else if (i < x.n && x.children.get(i + 1)
.n >= t)
{
// 3.a 右兄弟满足条件
BTNode rightBrother = x.children.get(i + 1);
E rightBrotherFirstKey = rightBrother.keys.get(0);
int childKeyNum = child.n;
child.insertKey(childKeyNum, x.keys.get(i));
x.keys.set(i, rightBrotherFirstKey);
if (!isChildLeaf)
{
BTNode rightBrotherFirstChild = rightBrother.children.get(0);
child.insertChild(childKeyNum + 1, rightBrotherFirstChild);
rightBrother.removeChild(0);
}
rightBrother.removeKey(0);
delete(child, key);
}
else if (i > 0)
{
// 3.b 存在左兄弟，合并
BTNode leftBrother = x.children.get(i - 1);
int leftBrotherKeyNum = leftBrother.n;
leftBrother.insertKey(leftBrotherKeyNum, x.keys.get(i - 1));
leftBrotherKeyNum++;
for (int j = 0; j < t - 1; j++)
{
leftBrother.insertKey(leftBrotherKeyNum, child.keys.get(j));
if (!isChildLeaf)
{
leftBrother.insertChild(leftBrotherKeyNum, child.children.get(j));
}
leftBrotherKeyNum++;
}
if (!isChildLeaf)
{
leftBrother.insertChild(leftBrotherKeyNum, child.children.get(t - 1));
}
x.removeChild(i);
x.removeKey(i - 1);
if (x.n == 0)
{
root = leftBrother;
}
delete(leftBrother, key);
}
else
{
// 3.b 存在右兄弟，合并
BTNode rightBrother = x.children.get(i + 1);
int childKeyNum = child.n;
child.insertKey(childKeyNum, x.keys.get(i));
childKeyNum++;
for (int j = 0; j < t - 1; j++)
{
child.insertKey(childKeyNum, rightBrother.keys.get(j));
if (!isChildLeaf)
{
child.insertChild(childKeyNum, rightBrother.children.get(j));
}
childKeyNum++;
}
if (!isChildLeaf)
{
child.insertChild(childKeyNum, rightBrother.children.get(t - 1));
}
x.removeKey(i);
x.removeChild(i + 1);
if (x.n == 0)
{
root = child;
}
delete(child, key);
}
}
}
private E deleteMinKey(BTNode x)
{
if (x.isLeaf)
{
return x.removeKey(0);
}
else
{
BTNode child = x.children.get(0);
boolean isChildLeaf = child.isLeaf;
BTNode rightBrother = x.children.get(1);
if (child.n >= t)
{
return deleteMinKey(child);
}
else if (rightBrother.n >= t)
{
// 3.a
E rightBrotherFirstKey = rightBrother.keys.get(0);
int childKeyNum = child.n;
child.insertKey(childKeyNum, x.keys.get(0));
x.keys.set(0, rightBrotherFirstKey);
if (!isChildLeaf)
{
BTNode rightBrotherFirstChild = rightBrother.children.get(0);
child.insertChild(childKeyNum + 1, rightBrotherFirstChild);
rightBrother.removeChild(0);
}
rightBrother.removeKey(0);
return deleteMinKey(child);
}
else
{
// 3.b
int childKeyNum = child.n;
child.insertKey(childKeyNum, x.keys.get(0));
childKeyNum++;
for (int j = 0; j < t - 1; j++)
{
child.insertKey(childKeyNum, rightBrother.keys.get(j));
if (!isChildLeaf)
{
child.insertChild(childKeyNum, rightBrother.children.get(j));
}
childKeyNum++;
}
if (!isChildLeaf)
{
child.insertChild(childKeyNum, rightBrother.children.get(t - 1));
}
x.removeChild(1);
x.removeKey(0);
return deleteMinKey(child);
}
}
}
private E deleteMaxKey(BTNode x)
{
int keyNum = x.n;
if (x.isLeaf)
{
return x.removeKey(keyNum - 1);
}
else
{
BTNode child = x.children.get(keyNum);
boolean isChildLeaf = child.isLeaf;
BTNode leftBrother = x.children.get(keyNum - 1);
int leftBrotherKeyNum = leftBrother.n;
if (child.n >= t)
{
return deleteMaxKey(child);
}
else if (leftBrother.n >= t)
{
// 3.a
E leftBrotherLastKey = leftBrother.keys.get(leftBrotherKeyNum - 1);
child.insertKey(0, x.keys.get(keyNum - 1));
x.keys.set(keyNum - 1, leftBrotherLastKey);
if (!isChildLeaf)
{
BTNode leftBrotherLastChild = leftBrother.children.get(leftBrotherKeyNum);
child.insertChild(0, leftBrotherLastChild);
leftBrother.removeChild(leftBrotherKeyNum);
}
leftBrother.removeKey(leftBrotherKeyNum - 1);
return deleteMaxKey(child);
}
else
{
// 3.b
leftBrother.insertKey(leftBrotherKeyNum, x.keys.get(keyNum - 1));
leftBrotherKeyNum++;
for (int j = 0; j < t - 1; j++)
{
leftBrother.insertKey(leftBrotherKeyNum, child.keys.get(j));
if (!isChildLeaf)
{
leftBrother.insertChild(leftBrotherKeyNum, child.children.get(j));
}
leftBrotherKeyNum++;
}
if (!isChildLeaf)
{
leftBrother.insertChild(leftBrotherKeyNum, child.children.get(t - 1));
}
// 删除关键字和孩子的操作最好放在后面来执行
x.removeChild(keyNum);
x.removeKey(keyNum - 1);
return deleteMaxKey(leftBrother);
}
}
}
public void print()
{
Queue queue = new LinkedBlockingQueue.BTNode > ();
queue.add(root);
while (!queue.isEmpty())
{
BTNode node = queue.poll();
for (int i = 0; i < node.n; i++)
{
System.out.print(node.keys.get(i) + " ");
}
System.out.println();
if (!node.isLeaf)
{
for (int i = 0; i < node.n + 1; i++)
{
queue.add(node.children.get(i));
}
}
}
}
public static void main(String[] args)
{
BTree bTree = new BTree(2);
bTree.insert("F");
bTree.insert("S");
bTree.insert("Q");
bTree.insert("K");
bTree.insert("C");
bTree.insert("L");
bTree.insert("H");
bTree.insert("T");
bTree.insert("V");
bTree.insert("W");
bTree.insert("M");
bTree.insert("R");
bTree.insert("N");
bTree.insert("P");
bTree.insert("A");
bTree.insert("B");
bTree.insert("X");
bTree.insert("Y");
bTree.insert("D");
bTree.insert("Z");
bTree.insert("E");
bTree.delete("Z");
bTree.delete("W");
bTree.delete("D");
bTree.delete("H");
bTree.delete("K");
bTree.delete("A");
bTree.delete("Y");
bTree.delete("F");
bTree.delete("M");
bTree.delete("Q");
bTree.delete("R");
bTree.delete("V");
bTree.delete("P");
bTree.delete("E");
bTree.delete("B");
bTree.delete("S");
bTree.delete("N");
bTree.delete("X");
bTree.delete("T");
bTree.delete("C");
bTree.delete("L");
bTree.print();
}
}以上就是创建b树的所有内容了，想了解更多b树相关的java常见问答知识，就请来关注我们网站吧。
推荐阅读：