# B+ 树
> 原文： [https://www.programiz.com/dsa/b-plus-tree](https://www.programiz.com/dsa/b-plus-tree)
#### 在本教程中，您将学习什么是 B+ 树。 此外，您还将找到在 C，C++ ，Java 和 Python 中对 B+ 树进行搜索操作的工作示例。
B+ 树是自平衡树的高级形式，其中所有值都存在于叶级别中。
学习 B+ 树之前要理解的重要概念是多级索引。 在多级索引中，索引索引如下图所示创建。 它使访问数据更容易，更快捷。
使用 B+ 树进行多级索引
* * *
## B+ 树的属性
1. 所有叶子处于同一级别。
2. 根至少有两个子级。
3. 除根节点外，每个节点最多可以包含`m`个子级，并且至少具有`m / 2`个子级。
4. 每个节点最多可以包含`m -1`键，以及最小`⌈m/2⌉ -1`键。
* * *
## B 树和 B+ 树之间的比较
B 树
B+ 树
数据指针仅出现在 B+ 树的叶子节点上，而数据指针则出现在 B 树的内部，叶子或根节点上。
叶子在 B 树上不相互连接，而在 B+ 树上连接。
B+ 树上的操作比 B 树上的操作快。
* * *
## B+ 树上的搜索
遵循以下步骤以在顺序为`m`的 B+ 树中搜索数据。 令要搜索的数据为`k`。
1. 从根节点开始。 比较`k`与根节点`[k1, k2, k3, ... k(m-1)]`上的键。
2. 如果`k < k1`，请转到根节点的左子节点。
3. 否则，如果`k == k1`，则比较`k2`。 如果`k < k2`，则`k`位于`k1`和`k2`之间。 因此，搜索`k2`的左子级。
4. 如果`k > k2`，则按照步骤 2 和步骤 6 中的`k3，k4，... k(m-1)`进行操作。
5. 重复上述步骤，直到到达叶节点。
6. 如果`k`在叶节点中存在，则返回`true`，否则返回`false`。
* * *
## B+ 树上的搜索示例
让我们在以下 B+ 树上搜索`k = 45`。
B+ 树
1. 将`k`与根节点进行比较。
在根下找不到
2. 由于`k > 25`，请找到合适的子级。
移至根的右侧
3. 比较`k`与 35。由于`k > 30`，将`k`与 45 比较。
未找到`k`
4. 由于`k≥45`，因此请找到合适的子级。
移至右侧
5. 找到了`k`。
* * *
## Python，Java 和 C/C++ 示例
```py
# B+ tee in python
import math
# Node creation
class Node:
def __init__(self, order):
self.order = order
self.values = []
self.keys = []
self.nextKey = None
self.parent = None
self.check_leaf = False
# Insert at the leaf
def insert_at_leaf(self, leaf, value, key):
if (self.values):
temp1 = self.values
for i in range(len(temp1)):
if (value == temp1[i]):
self.keys[i].append(key)
break
elif (value < temp1[i]):
self.values = self.values[:i] + [value] + self.values[i:]
self.keys = self.keys[:i] + [[key]] + self.keys[i:]
break
elif (i + 1 == len(temp1)):
self.values.append(value)
self.keys.append([key])
break
else:
self.values = [value]
self.keys = [[key]]
# B plus tree
class BplusTree:
def __init__(self, order):
self.root = Node(order)
self.root.check_leaf = True
# Insert operation
def insert(self, value, key):
value = str(value)
old_node = self.search(value)
old_node.insert_at_leaf(old_node, value, key)
if (len(old_node.values) == old_node.order):
node1 = Node(old_node.order)
node1.check_leaf = True
node1.parent = old_node.parent
mid = int(math.ceil(old_node.order / 2)) - 1
node1.values = old_node.values[mid + 1:]
node1.keys = old_node.keys[mid + 1:]
node1.nextKey = old_node.nextKey
old_node.values = old_node.values[:mid + 1]
old_node.keys = old_node.keys[:mid + 1]
old_node.nextKey = node1
self.insert_in_parent(old_node, node1.values[0], node1)
# Search operation for different operations
def search(self, value):
current_node = self.root
while(current_node.check_leaf == False):
temp2 = current_node.values
for i in range(len(temp2)):
if (value == temp2[i]):
current_node = current_node.keys[i + 1]
break
elif (value < temp2[i]):
current_node = current_node.keys[i]
break
elif (i + 1 == len(current_node.values)):
current_node = current_node.keys[i + 1]
break
return current_node
# Find the node
def find(self, value, key):
l = self.search(value)
for i, item in enumerate(l.values):
if item == value:
if key in l.keys[i]:
return True
else:
return False
return False
# Inserting at the parent
def insert_in_parent(self, n, value, ndash):
if (self.root == n):
rootNode = Node(n.order)
rootNode.values = [value]
rootNode.keys = [n, ndash]
self.root = rootNode
n.parent = rootNode
ndash.parent = rootNode
return
parentNode = n.parent
temp3 = parentNode.keys
for i in range(len(temp3)):
if (temp3[i] == n):
parentNode.values = parentNode.values[:i] + \
[value] + parentNode.values[i:]
parentNode.keys = parentNode.keys[:i +
1] + [ndash] + parentNode.keys[i + 1:]
if (len(parentNode.keys) > parentNode.order):
parentdash = Node(parentNode.order)
parentdash.parent = parentNode.parent
mid = int(math.ceil(parentNode.order / 2)) - 1
parentdash.values = parentNode.values[mid + 1:]
parentdash.keys = parentNode.keys[mid + 1:]
value_ = parentNode.values[mid]
if (mid == 0):
parentNode.values = parentNode.values[:mid + 1]
else:
parentNode.values = parentNode.values[:mid]
parentNode.keys = parentNode.keys[:mid + 1]
for j in parentNode.keys:
j.parent = parentNode
for j in parentdash.keys:
j.parent = parentdash
self.insert_in_parent(parentNode, value_, parentdash)
# Delete a node
def delete(self, value, key):
node_ = self.search(value)
temp = 0
for i, item in enumerate(node_.values):
if item == value:
temp = 1
if key in node_.keys[i]:
if len(node_.keys[i]) > 1:
node_.keys[i].pop(node_.keys[i].index(key))
elif node_ == self.root:
node_.values.pop(i)
node_.keys.pop(i)
else:
node_.keys[i].pop(node_.keys[i].index(key))
del node_.keys[i]
node_.values.pop(node_.values.index(value))
self.deleteEntry(node_, value, key)
else:
print("Value not in Key")
return
if temp == 0:
print("Value not in Tree")
return
# Delete an entry
def deleteEntry(self, node_, value, key):
if not node_.check_leaf:
for i, item in enumerate(node_.keys):
if item == key:
node_.keys.pop(i)
break
for i, item in enumerate(node_.values):
if item == value:
node_.values.pop(i)
break
if self.root == node_ and len(node_.keys) == 1:
self.root = node_.keys[0]
node_.keys[0].parent = None
del node_
return
elif (len(node_.keys) < int(math.ceil(node_.order / 2)) and node_.check_leaf == False) or (len(node_.values) < int(math.ceil((node_.order - 1) / 2)) and node_.check_leaf == True):
is_predecessor = 0
parentNode = node_.parent
PrevNode = -1
NextNode = -1
PrevK = -1
PostK = -1
for i, item in enumerate(parentNode.keys):
if item == node_:
if i > 0:
PrevNode = parentNode.keys[i - 1]
PrevK = parentNode.values[i - 1]
if i < len(parentNode.keys) - 1:
NextNode = parentNode.keys[i + 1]
PostK = parentNode.values[i]
if PrevNode == -1:
ndash = NextNode
value_ = PostK
elif NextNode == -1:
is_predecessor = 1
ndash = PrevNode
value_ = PrevK
else:
if len(node_.values) + len(NextNode.values) < node_.order:
ndash = NextNode
value_ = PostK
else:
is_predecessor = 1
ndash = PrevNode
value_ = PrevK
if len(node_.values) + len(ndash.values) < node_.order:
if is_predecessor == 0:
node_, ndash = ndash, node_
ndash.keys += node_.keys
if not node_.check_leaf:
ndash.values.append(value_)
else:
ndash.nextKey = node_.nextKey
ndash.values += node_.values
if not ndash.check_leaf:
for j in ndash.keys:
j.parent = ndash
self.deleteEntry(node_.parent, value_, node_)
del node_
else:
if is_predecessor == 1:
if not node_.check_leaf:
ndashpm = ndash.keys.pop(-1)
ndashkm_1 = ndash.values.pop(-1)
node_.keys = [ndashpm] + node_.keys
node_.values = [value_] + node_.values
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
p.values[i] = ndashkm_1
break
else:
ndashpm = ndash.keys.pop(-1)
ndashkm = ndash.values.pop(-1)
node_.keys = [ndashpm] + node_.keys
node_.values = [ndashkm] + node_.values
parentNode = node_.parent
for i, item in enumerate(p.values):
if item == value_:
parentNode.values[i] = ndashkm
break
else:
if not node_.check_leaf:
ndashp0 = ndash.keys.pop(0)
ndashk0 = ndash.values.pop(0)
node_.keys = node_.keys + [ndashp0]
node_.values = node_.values + [value_]
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
parentNode.values[i] = ndashk0
break
else:
ndashp0 = ndash.keys.pop(0)
ndashk0 = ndash.values.pop(0)
node_.keys = node_.keys + [ndashp0]
node_.values = node_.values + [ndashk0]
parentNode = node_.parent
for i, item in enumerate(parentNode.values):
if item == value_:
parentNode.values[i] = ndash.values[0]
break
if not ndash.check_leaf:
for j in ndash.keys:
j.parent = ndash
if not node_.check_leaf:
for j in node_.keys:
j.parent = node_
if not parentNode.check_leaf:
for j in parentNode.keys:
j.parent = parentNode
# Print the tree
def printTree(tree):
lst = [tree.root]
level = [0]
leaf = None
flag = 0
lev_leaf = 0
node1 = Node(str(level[0]) + str(tree.root.values))
while (len(lst) != 0):
x = lst.pop(0)
lev = level.pop(0)
if (x.check_leaf == False):
for i, item in enumerate(x.keys):
print(item.values)
else:
for i, item in enumerate(x.keys):
print(item.values)
if (flag == 0):
lev_leaf = lev
leaf = x
flag = 1
record_len = 3
bplustree = BplusTree(record_len)
bplustree.insert('5', '33')
bplustree.insert('15', '21')
bplustree.insert('25', '31')
bplustree.insert('35', '41')
bplustree.insert('45', '10')
printTree(bplustree)
if(bplustree.find('5', '34')):
print("Found")
else:
print("Not found")
```
```java
// Searching on a B+ tree in Java
import java.util.*;
public class BPlusTree {
int m;
InternalNode root;
LeafNode firstLeaf;
// Binary search program
private int binarySearch(DictionaryPair[] dps, int numPairs, int t) {
Comparator<DictionaryPair> c = new Comparator<DictionaryPair>() {
@Override
public int compare(DictionaryPair o1, DictionaryPair o2) {
Integer a = Integer.valueOf(o1.key);
Integer b = Integer.valueOf(o2.key);
return a.compareTo(b);
}
};
return Arrays.binarySearch(dps, 0, numPairs, new DictionaryPair(t, 0), c);
}
// Find the leaf node
private LeafNode findLeafNode(int key) {
Integer[] keys = this.root.keys;
int i;
for (i = 0; i < this.root.degree - 1; i++) {
if (key < keys[i]) {
break;
}
}
Node child = this.root.childPointers[i];
if (child instanceof LeafNode) {
return (LeafNode) child;
} else {
return findLeafNode((InternalNode) child, key);
}
}
// Find the leaf node
private LeafNode findLeafNode(InternalNode node, int key) {
Integer[] keys = node.keys;
int i;
for (i = 0; i < node.degree - 1; i++) {
if (key < keys[i]) {
break;
}
}
Node childNode = node.childPointers[i];
if (childNode instanceof LeafNode) {
return (LeafNode) childNode;
} else {
return findLeafNode((InternalNode) node.childPointers[i], key);
}
}
// Finding the index of the pointer
private int findIndexOfPointer(Node[] pointers, LeafNode node) {
int i;
for (i = 0; i < pointers.length; i++) {
if (pointers[i] == node) {
break;
}
}
return i;
}
// Get the mid point
private int getMidpoint() {
return (int) Math.ceil((this.m + 1) / 2.0) - 1;
}
// Balance the tree
private void handleDeficiency(InternalNode in) {
InternalNode sibling;
InternalNode parent = in.parent;
if (this.root == in) {
for (int i = 0; i < in.childPointers.length; i++) {
if (in.childPointers[i] != null) {
if (in.childPointers[i] instanceof InternalNode) {
this.root = (InternalNode) in.childPointers[i];
this.root.parent = null;
} else if (in.childPointers[i] instanceof LeafNode) {
this.root = null;
}
}
}
}
else if (in.leftSibling != null && in.leftSibling.isLendable()) {
sibling = in.leftSibling;
} else if (in.rightSibling != null && in.rightSibling.isLendable()) {
sibling = in.rightSibling;
int borrowedKey = sibling.keys[0];
Node pointer = sibling.childPointers[0];
in.keys[in.degree - 1] = parent.keys[0];
in.childPointers[in.degree] = pointer;
parent.keys[0] = borrowedKey;
sibling.removePointer(0);
Arrays.sort(sibling.keys);
sibling.removePointer(0);
shiftDown(in.childPointers, 1);
} else if (in.leftSibling != null && in.leftSibling.isMergeable()) {
} else if (in.rightSibling != null && in.rightSibling.isMergeable()) {
sibling = in.rightSibling;
sibling.keys[sibling.degree - 1] = parent.keys[parent.degree - 2];
Arrays.sort(sibling.keys, 0, sibling.degree);
parent.keys[parent.degree - 2] = null;
for (int i = 0; i < in.childPointers.length; i++) {
if (in.childPointers[i] != null) {
sibling.prependChildPointer(in.childPointers[i]);
in.childPointers[i].parent = sibling;
in.removePointer(i);
}
}
parent.removePointer(in);
sibling.leftSibling = in.leftSibling;
}
if (parent != null && parent.isDeficient()) {
handleDeficiency(parent);
}
}
private boolean isEmpty() {
return firstLeaf == null;
}
private int linearNullSearch(DictionaryPair[] dps) {
for (int i = 0; i < dps.length; i++) {
if (dps[i] == null) {
return i;
}
}
return -1;
}
private int linearNullSearch(Node[] pointers) {
for (int i = 0; i < pointers.length; i++) {
if (pointers[i] == null) {
return i;
}
}
return -1;
}
private void shiftDown(Node[] pointers, int amount) {
Node[] newPointers = new Node[this.m + 1];
for (int i = amount; i < pointers.length; i++) {
newPointers[i - amount] = pointers[i];
}
pointers = newPointers;
}
private void sortDictionary(DictionaryPair[] dictionary) {
Arrays.sort(dictionary, new Comparator<DictionaryPair>() {
@Override
public int compare(DictionaryPair o1, DictionaryPair o2) {
if (o1 == null && o2 == null) {
return 0;
}
if (o1 == null) {
return 1;
}
if (o2 == null) {
return -1;
}
return o1.compareTo(o2);
}
});
}
private Node[] splitChildPointers(InternalNode in, int split) {
Node[] pointers = in.childPointers;
Node[] halfPointers = new Node[this.m + 1];
for (int i = split + 1; i < pointers.length; i++) {
halfPointers[i - split - 1] = pointers[i];
in.removePointer(i);
}
return halfPointers;
}
private DictionaryPair[] splitDictionary(LeafNode ln, int split) {
DictionaryPair[] dictionary = ln.dictionary;
DictionaryPair[] halfDict = new DictionaryPair[this.m];
for (int i = split; i < dictionary.length; i++) {
halfDict[i - split] = dictionary[i];
ln.delete(i);
}
return halfDict;
}
private void splitInternalNode(InternalNode in) {
InternalNode parent = in.parent;
int midpoint = getMidpoint();
int newParentKey = in.keys[midpoint];
Integer[] halfKeys = splitKeys(in.keys, midpoint);
Node[] halfPointers = splitChildPointers(in, midpoint);
in.degree = linearNullSearch(in.childPointers);
InternalNode sibling = new InternalNode(this.m, halfKeys, halfPointers);
for (Node pointer : halfPointers) {
if (pointer != null) {
pointer.parent = sibling;
}
}
sibling.rightSibling = in.rightSibling;
if (sibling.rightSibling != null) {
sibling.rightSibling.leftSibling = sibling;
}
in.rightSibling = sibling;
sibling.leftSibling = in;
if (parent == null) {
Integer[] keys = new Integer[this.m];
keys[0] = newParentKey;
InternalNode newRoot = new InternalNode(this.m, keys);
newRoot.appendChildPointer(in);
newRoot.appendChildPointer(sibling);
this.root = newRoot;
in.parent = newRoot;
sibling.parent = newRoot;
} else {
parent.keys[parent.degree - 1] = newParentKey;
Arrays.sort(parent.keys, 0, parent.degree);
int pointerIndex = parent.findIndexOfPointer(in) + 1;
parent.insertChildPointer(sibling, pointerIndex);
sibling.parent = parent;
}
}
private Integer[] splitKeys(Integer[] keys, int split) {
Integer[] halfKeys = new Integer[this.m];
keys[split] = null;
for (int i = split + 1; i < keys.length; i++) {
halfKeys[i - split - 1] = keys[i];
keys[i] = null;
}
return halfKeys;
}
public void insert(int key, double value) {
if (isEmpty()) {
LeafNode ln = new LeafNode(this.m, new DictionaryPair(key, value));
this.firstLeaf = ln;
} else {
LeafNode ln = (this.root == null) ? this.firstLeaf : findLeafNode(key);
if (!ln.insert(new DictionaryPair(key, value))) {
ln.dictionary[ln.numPairs] = new DictionaryPair(key, value);
ln.numPairs++;
sortDictionary(ln.dictionary);
int midpoint = getMidpoint();
DictionaryPair[] halfDict = splitDictionary(ln, midpoint);
if (ln.parent == null) {
Integer[] parent_keys = new Integer[this.m];
parent_keys[0] = halfDict[0].key;
InternalNode parent = new InternalNode(this.m, parent_keys);
ln.parent = parent;
parent.appendChildPointer(ln);
} else {
int newParentKey = halfDict[0].key;
ln.parent.keys[ln.parent.degree - 1] = newParentKey;
Arrays.sort(ln.parent.keys, 0, ln.parent.degree);
}
LeafNode newLeafNode = new LeafNode(this.m, halfDict, ln.parent);
int pointerIndex = ln.parent.findIndexOfPointer(ln) + 1;
ln.parent.insertChildPointer(newLeafNode, pointerIndex);
newLeafNode.rightSibling = ln.rightSibling;
if (newLeafNode.rightSibling != null) {
newLeafNode.rightSibling.leftSibling = newLeafNode;
}
ln.rightSibling = newLeafNode;
newLeafNode.leftSibling = ln;
if (this.root == null) {
this.root = ln.parent;
} else {
InternalNode in = ln.parent;
while (in != null) {
if (in.isOverfull()) {
splitInternalNode(in);
} else {
break;
}
in = in.parent;
}
}
}
}
}
public Double search(int key) {
if (isEmpty()) {
return null;
}
LeafNode ln = (this.root == null) ? this.firstLeaf : findLeafNode(key);
DictionaryPair[] dps = ln.dictionary;
int index = binarySearch(dps, ln.numPairs, key);
if (index < 0) {
return null;
} else {
return dps[index].value;
}
}
public ArrayList<Double> search(int lowerBound, int upperBound) {
ArrayList<Double> values = new ArrayList<Double>();
LeafNode currNode = this.firstLeaf;
while (currNode != null) {
DictionaryPair dps[] = currNode.dictionary;
for (DictionaryPair dp : dps) {
if (dp == null) {
break;
}
if (lowerBound <= dp.key && dp.key <= upperBound) {
values.add(dp.value);
}
}
currNode = currNode.rightSibling;
}
return values;
}
public BPlusTree(int m) {
this.m = m;
this.root = null;
}
public class Node {
InternalNode parent;
}
private class InternalNode extends Node {
int maxDegree;
int minDegree;
int degree;
InternalNode leftSibling;
InternalNode rightSibling;
Integer[] keys;
Node[] childPointers;
private void appendChildPointer(Node pointer) {
this.childPointers[degree] = pointer;
this.degree++;
}
private int findIndexOfPointer(Node pointer) {
for (int i = 0; i < childPointers.length; i++) {
if (childPointers[i] == pointer) {
return i;
}
}
return -1;
}
private void insertChildPointer(Node pointer, int index) {
for (int i = degree - 1; i >= index; i--) {
childPointers[i + 1] = childPointers[i];
}
this.childPointers[index] = pointer;
this.degree++;
}
private boolean isDeficient() {
return this.degree < this.minDegree;
}
private boolean isLendable() {
return this.degree > this.minDegree;
}
private boolean isMergeable() {
return this.degree == this.minDegree;
}
private boolean isOverfull() {
return this.degree == maxDegree + 1;
}
private void prependChildPointer(Node pointer) {
for (int i = degree - 1; i >= 0; i--) {
childPointers[i + 1] = childPointers[i];
}
this.childPointers[0] = pointer;
this.degree++;
}
private void removeKey(int index) {
this.keys[index] = null;
}
private void removePointer(int index) {
this.childPointers[index] = null;
this.degree--;
}
private void removePointer(Node pointer) {
for (int i = 0; i < childPointers.length; i++) {
if (childPointers[i] == pointer) {
this.childPointers[i] = null;
}
}
this.degree--;
}
private InternalNode(int m, Integer[] keys) {
this.maxDegree = m;
this.minDegree = (int) Math.ceil(m / 2.0);
this.degree = 0;
this.keys = keys;
this.childPointers = new Node[this.maxDegree + 1];
}
private InternalNode(int m, Integer[] keys, Node[] pointers) {
this.maxDegree = m;
this.minDegree = (int) Math.ceil(m / 2.0);
this.degree = linearNullSearch(pointers);
this.keys = keys;
this.childPointers = pointers;
}
}
public class LeafNode extends Node {
int maxNumPairs;
int minNumPairs;
int numPairs;
LeafNode leftSibling;
LeafNode rightSibling;
DictionaryPair[] dictionary;
public void delete(int index) {
this.dictionary[index] = null;
numPairs--;
}
public boolean insert(DictionaryPair dp) {
if (this.isFull()) {
return false;
} else {
this.dictionary[numPairs] = dp;
numPairs++;
Arrays.sort(this.dictionary, 0, numPairs);
return true;
}
}
public boolean isDeficient() {
return numPairs < minNumPairs;
}
public boolean isFull() {
return numPairs == maxNumPairs;
}
public boolean isLendable() {
return numPairs > minNumPairs;
}
public boolean isMergeable() {
return numPairs == minNumPairs;
}
public LeafNode(int m, DictionaryPair dp) {
this.maxNumPairs = m - 1;
this.minNumPairs = (int) (Math.ceil(m / 2) - 1);
this.dictionary = new DictionaryPair[m];
this.numPairs = 0;
this.insert(dp);
}
public LeafNode(int m, DictionaryPair[] dps, InternalNode parent) {
this.maxNumPairs = m - 1;
this.minNumPairs = (int) (Math.ceil(m / 2) - 1);
this.dictionary = dps;
this.numPairs = linearNullSearch(dps);
this.parent = parent;
}
}
public class DictionaryPair implements Comparable<DictionaryPair> {
int key;
double value;
public DictionaryPair(int key, double value) {
this.key = key;
this.value = value;
}
public int compareTo(DictionaryPair o) {
if (key == o.key) {
return 0;
} else if (key > o.key) {
return 1;
} else {
return -1;
}
}
}
public static void main(String[] args) {
BPlusTree bpt = null;
bpt = new BPlusTree(3);
bpt.insert(5, 33);
bpt.insert(15, 21);
bpt.insert(25, 31);
bpt.insert(35, 41);
bpt.insert(45, 10);
if (bpt.search(15) != null) {
System.out.println("Found");
} else {
System.out.println("Not Found");
}
;
}
}
```
```c
// Searching on a B+ Tree in C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Default order
#define ORDER 3
typedef struct record {
int value;
} record;
// Node
typedef struct node {
void **pointers;
int *keys;
struct node *parent;
bool is_leaf;
int num_keys;
struct node *next;
} node;
int order = ORDER;
node *queue = NULL;
bool verbose_output = false;
// Enqueue
void enqueue(node *new_node);
// Dequeue
node *dequeue(void);
int height(node *const root);
int pathToLeaves(node *const root, node *child);
void printLeaves(node *const root);
void printTree(node *const root);
void findAndPrint(node *const root, int key, bool verbose);
void findAndPrintRange(node *const root, int range1, int range2, bool verbose);
int findRange(node *const root, int key_start, int key_end, bool verbose,
int returned_keys[], void *returned_pointers[]);
node *findLeaf(node *const root, int key, bool verbose);
record *find(node *root, int key, bool verbose, node **leaf_out);
int cut(int length);
record *makeRecord(int value);
node *makeNode(void);
node *makeLeaf(void);
int getLeftIndex(node *parent, node *left);
node *insertIntoLeaf(node *leaf, int key, record *pointer);
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key,
record *pointer);
node *insertIntoNode(node *root, node *parent,
int left_index, int key, node *right);
node *insertIntoNodeAfterSplitting(node *root, node *parent,
int left_index,
int key, node *right);
node *insertIntoParent(node *root, node *left, int key, node *right);
node *insertIntoNewRoot(node *left, int key, node *right);
node *startNewTree(int key, record *pointer);
node *insert(node *root, int key, int value);
// Enqueue
void enqueue(node *new_node) {
node *c;
if (queue == NULL) {
queue = new_node;
queue->next = NULL;
} else {
c = queue;
while (c->next != NULL) {
c = c->next;
}
c->next = new_node;
new_node->next = NULL;
}
}
// Dequeue
node *dequeue(void) {
node *n = queue;
queue = queue->next;
n->next = NULL;
return n;
}
// Print the leaves
void printLeaves(node *const root) {
if (root == NULL) {
printf("Empty tree.\n");
return;
}
int i;
node *c = root;
while (!c->is_leaf)
c = c->pointers[0];
while (true) {
for (i = 0; i < c->num_keys; i++) {
if (verbose_output)
printf("%p ", c->pointers[i]);
printf("%d ", c->keys[i]);
}
if (verbose_output)
printf("%p ", c->pointers[order - 1]);
if (c->pointers[order - 1] != NULL) {
printf(" | ");
c = c->pointers[order - 1];
} else
break;
}
printf("\n");
}
// Calculate height
int height(node *const root) {
int h = 0;
node *c = root;
while (!c->is_leaf) {
c = c->pointers[0];
h++;
}
return h;
}
// Get path to root
int pathToLeaves(node *const root, node *child) {
int length = 0;
node *c = child;
while (c != root) {
c = c->parent;
length++;
}
return length;
}
// Print the tree
void printTree(node *const root) {
node *n = NULL;
int i = 0;
int rank = 0;
int new_rank = 0;
if (root == NULL) {
printf("Empty tree.\n");
return;
}
queue = NULL;
enqueue(root);
while (queue != NULL) {
n = dequeue();
if (n->parent != NULL && n == n->parent->pointers[0]) {
new_rank = pathToLeaves(root, n);
if (new_rank != rank) {
rank = new_rank;
printf("\n");
}
}
if (verbose_output)
printf("(%p)", n);
for (i = 0; i < n->num_keys; i++) {
if (verbose_output)
printf("%p ", n->pointers[i]);
printf("%d ", n->keys[i]);
}
if (!n->is_leaf)
for (i = 0; i <= n->num_keys; i++)
enqueue(n->pointers[i]);
if (verbose_output) {
if (n->is_leaf)
printf("%p ", n->pointers[order - 1]);
else
printf("%p ", n->pointers[n->num_keys]);
}
printf("| ");
}
printf("\n");
}
// Find the node and print it
void findAndPrint(node *const root, int key, bool verbose) {
node *leaf = NULL;
record *r = find(root, key, verbose, NULL);
if (r == NULL)
printf("Record not found under key %d.\n", key);
else
printf("Record at %p -- key %d, value %d.\n",
r, key, r->value);
}
// Find and print the range
void findAndPrintRange(node *const root, int key_start, int key_end,
bool verbose) {
int i;
int array_size = key_end - key_start + 1;
int returned_keys[array_size];
void *returned_pointers[array_size];
int num_found = findRange(root, key_start, key_end, verbose,
returned_keys, returned_pointers);
if (!num_found)
printf("None found.\n");
else {
for (i = 0; i < num_found; i++)
printf("Key: %d Location: %p Value: %d\n",
returned_keys[i],
returned_pointers[i],
((record *)
returned_pointers[i])
->value);
}
}
// Find the range
int findRange(node *const root, int key_start, int key_end, bool verbose,
int returned_keys[], void *returned_pointers[]) {
int i, num_found;
num_found = 0;
node *n = findLeaf(root, key_start, verbose);
if (n == NULL)
return 0;
for (i = 0; i < n->num_keys && n->keys[i] < key_start; i++)
;
if (i == n->num_keys)
return 0;
while (n != NULL) {
for (; i < n->num_keys && n->keys[i] <= key_end; i++) {
returned_keys[num_found] = n->keys[i];
returned_pointers[num_found] = n->pointers[i];
num_found++;
}
n = n->pointers[order - 1];
i = 0;
}
return num_found;
}
// Find the leaf
node *findLeaf(node *const root, int key, bool verbose) {
if (root == NULL) {
if (verbose)
printf("Empty tree.\n");
return root;
}
int i = 0;
node *c = root;
while (!c->is_leaf) {
if (verbose) {
printf("[");
for (i = 0; i < c->num_keys - 1; i++)
printf("%d ", c->keys[i]);
printf("%d] ", c->keys[i]);
}
i = 0;
while (i < c->num_keys) {
if (key >= c->keys[i])
i++;
else
break;
}
if (verbose)
printf("%d ->\n", i);
c = (node *)c->pointers[i];
}
if (verbose) {
printf("Leaf [");
for (i = 0; i < c->num_keys - 1; i++)
printf("%d ", c->keys[i]);
printf("%d] ->\n", c->keys[i]);
}
return c;
}
record *find(node *root, int key, bool verbose, node **leaf_out) {
if (root == NULL) {
if (leaf_out != NULL) {
*leaf_out = NULL;
}
return NULL;
}
int i = 0;
node *leaf = NULL;
leaf = findLeaf(root, key, verbose);
for (i = 0; i < leaf->num_keys; i++)
if (leaf->keys[i] == key)
break;
if (leaf_out != NULL) {
*leaf_out = leaf;
}
if (i == leaf->num_keys)
return NULL;
else
return (record *)leaf->pointers[i];
}
int cut(int length) {
if (length % 2 == 0)
return length / 2;
else
return length / 2 + 1;
}
record *makeRecord(int value) {
record *new_record = (record *)malloc(sizeof(record));
if (new_record == NULL) {
perror("Record creation.");
exit(EXIT_FAILURE);
} else {
new_record->value = value;
}
return new_record;
}
node *makeNode(void) {
node *new_node;
new_node = malloc(sizeof(node));
if (new_node == NULL) {
perror("Node creation.");
exit(EXIT_FAILURE);
}
new_node->keys = malloc((order - 1) * sizeof(int));
if (new_node->keys == NULL) {
perror("New node keys array.");
exit(EXIT_FAILURE);
}
new_node->pointers = malloc(order * sizeof(void *));
if (new_node->pointers == NULL) {
perror("New node pointers array.");
exit(EXIT_FAILURE);
}
new_node->is_leaf = false;
new_node->num_keys = 0;
new_node->parent = NULL;
new_node->next = NULL;
return new_node;
}
node *makeLeaf(void) {
node *leaf = makeNode();
leaf->is_leaf = true;
return leaf;
}
int getLeftIndex(node *parent, node *left) {
int left_index = 0;
while (left_index <= parent->num_keys &&
parent->pointers[left_index] != left)
left_index++;
return left_index;
}
node *insertIntoLeaf(node *leaf, int key, record *pointer) {
int i, insertion_point;
insertion_point = 0;
while (insertion_point < leaf->num_keys && leaf->keys[insertion_point] < key)
insertion_point++;
for (i = leaf->num_keys; i > insertion_point; i--) {
leaf->keys[i] = leaf->keys[i - 1];
leaf->pointers[i] = leaf->pointers[i - 1];
}
leaf->keys[insertion_point] = key;
leaf->pointers[insertion_point] = pointer;
leaf->num_keys++;
return leaf;
}
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key, record *pointer) {
node *new_leaf;
int *temp_keys;
void **temp_pointers;
int insertion_index, split, new_key, i, j;
new_leaf = makeLeaf();
temp_keys = malloc(order * sizeof(int));
if (temp_keys == NULL) {
perror("Temporary keys array.");
exit(EXIT_FAILURE);
}
temp_pointers = malloc(order * sizeof(void *));
if (temp_pointers == NULL) {
perror("Temporary pointers array.");
exit(EXIT_FAILURE);
}
insertion_index = 0;
while (insertion_index < order - 1 && leaf->keys[insertion_index] < key)
insertion_index++;
for (i = 0, j = 0; i < leaf->num_keys; i++, j++) {
if (j == insertion_index)
j++;
temp_keys[j] = leaf->keys[i];
temp_pointers[j] = leaf->pointers[i];
}
temp_keys[insertion_index] = key;
temp_pointers[insertion_index] = pointer;
leaf->num_keys = 0;
split = cut(order - 1);
for (i = 0; i < split; i++) {
leaf->pointers[i] = temp_pointers[i];
leaf->keys[i] = temp_keys[i];
leaf->num_keys++;
}
for (i = split, j = 0; i < order; i++, j++) {
new_leaf->pointers[j] = temp_pointers[i];
new_leaf->keys[j] = temp_keys[i];
new_leaf->num_keys++;
}
free(temp_pointers);
free(temp_keys);
new_leaf->pointers[order - 1] = leaf->pointers[order - 1];
leaf->pointers[order - 1] = new_leaf;
for (i = leaf->num_keys; i < order - 1; i++)
leaf->pointers[i] = NULL;
for (i = new_leaf->num_keys; i < order - 1; i++)
new_leaf->pointers[i] = NULL;
new_leaf->parent = leaf->parent;
new_key = new_leaf->keys[0];
return insertIntoParent(root, leaf, new_key, new_leaf);
}
node *insertIntoNode(node *root, node *n,
int left_index, int key, node *right) {
int i;
for (i = n->num_keys; i > left_index; i--) {
n->pointers[i + 1] = n->pointers[i];
n->keys[i] = n->keys[i - 1];
}
n->pointers[left_index + 1] = right;
n->keys[left_index] = key;
n->num_keys++;
return root;
}
node *insertIntoNodeAfterSplitting(node *root, node *old_node, int left_index,
int key, node *right) {
int i, j, split, k_prime;
node *new_node, *child;
int *temp_keys;
node **temp_pointers;
temp_pointers = malloc((order + 1) * sizeof(node *));
if (temp_pointers == NULL) {
exit(EXIT_FAILURE);
}
temp_keys = malloc(order * sizeof(int));
if (temp_keys == NULL) {
exit(EXIT_FAILURE);
}
for (i = 0, j = 0; i < old_node->num_keys + 1; i++, j++) {
if (j == left_index + 1)
j++;
temp_pointers[j] = old_node->pointers[i];
}
for (i = 0, j = 0; i < old_node->num_keys; i++, j++) {
if (j == left_index)
j++;
temp_keys[j] = old_node->keys[i];
}
temp_pointers[left_index + 1] = right;
temp_keys[left_index] = key;
split = cut(order);
new_node = makeNode();
old_node->num_keys = 0;
for (i = 0; i < split - 1; i++) {
old_node->pointers[i] = temp_pointers[i];
old_node->keys[i] = temp_keys[i];
old_node->num_keys++;
}
old_node->pointers[i] = temp_pointers[i];
k_prime = temp_keys[split - 1];
for (++i, j = 0; i < order; i++, j++) {
new_node->pointers[j] = temp_pointers[i];
new_node->keys[j] = temp_keys[i];
new_node->num_keys++;
}
new_node->pointers[j] = temp_pointers[i];
free(temp_pointers);
free(temp_keys);
new_node->parent = old_node->parent;
for (i = 0; i <= new_node->num_keys; i++) {
child = new_node->pointers[i];
child->parent = new_node;
}
return insertIntoParent(root, old_node, k_prime, new_node);
}
node *insertIntoParent(node *root, node *left, int key, node *right) {
int left_index;
node *parent;
parent = left->parent;
if (parent == NULL)
return insertIntoNewRoot(left, key, right);
left_index = getLeftIndex(parent, left);
if (parent->num_keys < order - 1)
return insertIntoNode(root, parent, left_index, key, right);
return insertIntoNodeAfterSplitting(root, parent, left_index, key, right);
}
node *insertIntoNewRoot(node *left, int key, node *right) {
node *root = makeNode();
root->keys[0] = key;
root->pointers[0] = left;
root->pointers[1] = right;
root->num_keys++;
root->parent = NULL;
left->parent = root;
right->parent = root;
return root;
}
node *startNewTree(int key, record *pointer) {
node *root = makeLeaf();
root->keys[0] = key;
root->pointers[0] = pointer;
root->pointers[order - 1] = NULL;
root->parent = NULL;
root->num_keys++;
return root;
}
node *insert(node *root, int key, int value) {
record *record_pointer = NULL;
node *leaf = NULL;
record_pointer = find(root, key, false, NULL);
if (record_pointer != NULL) {
record_pointer->value = value;
return root;
}
record_pointer = makeRecord(value);
if (root == NULL)
return startNewTree(key, record_pointer);
leaf = findLeaf(root, key, false);
if (leaf->num_keys < order - 1) {
leaf = insertIntoLeaf(leaf, key, record_pointer);
return root;
}
return insertIntoLeafAfterSplitting(root, leaf, key, record_pointer);
}
int main() {
node *root;
char instruction;
root = NULL;
root = insert(root, 5, 33);
root = insert(root, 15, 21);
root = insert(root, 25, 31);
root = insert(root, 35, 41);
root = insert(root, 45, 10);
printTree(root);
findAndPrint(root, 15, instruction = 'a');
}
```
```cpp
// Searching on a B+ tree in C++
#include <climits>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;
int MAX = 3;
// BP node
class Node {
bool IS_LEAF;
int *key, size;
Node **ptr;
friend class BPTree;
public:
Node();
};
// BP tree
class BPTree {
Node *root;
void insertInternal(int, Node *, Node *);
Node *findParent(Node *, Node *);
public:
BPTree();
void search(int);
void insert(int);
void display(Node *);
Node *getRoot();
};
Node::Node() {
key = new int[MAX];
ptr = new Node *[MAX + 1];
}
BPTree::BPTree() {
root = NULL;
}
// Search operation
void BPTree::search(int x) {
if (root == NULL) {
cout << "Tree is empty\n";
} else {
Node *cursor = root;
while (cursor->IS_LEAF == false) {
for (int i = 0; i < cursor->size; i++) {
if (x < cursor->key[i]) {
cursor = cursor->ptr[i];
break;
}
if (i == cursor->size - 1) {
cursor = cursor->ptr[i + 1];
break;
}
}
}
for (int i = 0; i < cursor->size; i++) {
if (cursor->key[i] == x) {
cout << "Found\n";
return;
}
}
cout << "Not found\n";
}
}
// Insert Operation
void BPTree::insert(int x) {
if (root == NULL) {
root = new Node;
root->key[0] = x;
root->IS_LEAF = true;
root->size = 1;
} else {
Node *cursor = root;
Node *parent;
while (cursor->IS_LEAF == false) {
parent = cursor;
for (int i = 0; i < cursor->size; i++) {
if (x < cursor->key[i]) {
cursor = cursor->ptr[i];
break;
}
if (i == cursor->size - 1) {
cursor = cursor->ptr[i + 1];
break;
}
}
}
if (cursor->size < MAX) {
int i = 0;
while (x > cursor->key[i] && i < cursor->size)
i++;
for (int j = cursor->size; j > i; j--) {
cursor->key[j] = cursor->key[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];
cursor->ptr[cursor->size - 1] = NULL;
} else {
Node *newLeaf = new Node;
int virtualNode[MAX + 1];
for (int i = 0; i < MAX; i++) {
virtualNode[i] = cursor->key[i];
}
int i = 0, j;
while (x > virtualNode[i] && i < MAX)
i++;
for (int j = MAX + 1; j > i; j--) {
virtualNode[j] = virtualNode[j - 1];
}
virtualNode[i] = x;
newLeaf->IS_LEAF = true;
cursor->size = (MAX + 1) / 2;
newLeaf->size = MAX + 1 - (MAX + 1) / 2;
cursor->ptr[cursor->size] = newLeaf;
newLeaf->ptr[newLeaf->size] = cursor->ptr[MAX];
cursor->ptr[MAX] = NULL;
for (i = 0; i < cursor->size; i++) {
cursor->key[i] = virtualNode[i];
}
for (i = 0, j = cursor->size; i < newLeaf->size; i++, j++) {
newLeaf->key[i] = virtualNode[j];
}
if (cursor == root) {
Node *newRoot = new Node;
newRoot->key[0] = newLeaf->key[0];
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newLeaf;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
} else {
insertInternal(newLeaf->key[0], parent, newLeaf);
}
}
}
}
// Insert Operation
void BPTree::insertInternal(int x, Node *cursor, Node *child) {
if (cursor->size < MAX) {
int i = 0;
while (x > cursor->key[i] && i < cursor->size)
i++;
for (int j = cursor->size; j > i; j--) {
cursor->key[j] = cursor->key[j - 1];
}
for (int j = cursor->size + 1; j > i + 1; j--) {
cursor->ptr[j] = cursor->ptr[j - 1];
}
cursor->key[i] = x;
cursor->size++;
cursor->ptr[i + 1] = child;
} else {
Node *newInternal = new Node;
int virtualKey[MAX + 1];
Node *virtualPtr[MAX + 2];
for (int i = 0; i < MAX; i++) {
virtualKey[i] = cursor->key[i];
}
for (int i = 0; i < MAX + 1; i++) {
virtualPtr[i] = cursor->ptr[i];
}
int i = 0, j;
while (x > virtualKey[i] && i < MAX)
i++;
for (int j = MAX + 1; j > i; j--) {
virtualKey[j] = virtualKey[j - 1];
}
virtualKey[i] = x;
for (int j = MAX + 2; j > i + 1; j--) {
virtualPtr[j] = virtualPtr[j - 1];
}
virtualPtr[i + 1] = child;
newInternal->IS_LEAF = false;
cursor->size = (MAX + 1) / 2;
newInternal->size = MAX - (MAX + 1) / 2;
for (i = 0, j = cursor->size + 1; i < newInternal->size; i++, j++) {
newInternal->key[i] = virtualKey[j];
}
for (i = 0, j = cursor->size + 1; i < newInternal->size + 1; i++, j++) {
newInternal->ptr[i] = virtualPtr[j];
}
if (cursor == root) {
Node *newRoot = new Node;
newRoot->key[0] = cursor->key[cursor->size];
newRoot->ptr[0] = cursor;
newRoot->ptr[1] = newInternal;
newRoot->IS_LEAF = false;
newRoot->size = 1;
root = newRoot;
} else {
insertInternal(cursor->key[cursor->size], findParent(root, cursor), newInternal);
}
}
}
// Find the parent
Node *BPTree::findParent(Node *cursor, Node *child) {
Node *parent;
if (cursor->IS_LEAF || (cursor->ptr[0])->IS_LEAF) {
return NULL;
}
for (int i = 0; i < cursor->size + 1; i++) {
if (cursor->ptr[i] == child) {
parent = cursor;
return parent;
} else {
parent = findParent(cursor->ptr[i], child);
if (parent != NULL)
return parent;
}
}
return parent;
}
// Print the tree
void BPTree::display(Node *cursor) {
if (cursor != NULL) {
for (int i = 0; i < cursor->size; i++) {
cout << cursor->key[i] << " ";
}
cout << "\n";
if (cursor->IS_LEAF != true) {
for (int i = 0; i < cursor->size + 1; i++) {
display(cursor->ptr[i]);
}
}
}
}
// Get the root
Node *BPTree::getRoot() {
return root;
}
int main() {
BPTree node;
node.insert(5);
node.insert(15);
node.insert(25);
node.insert(35);
node.insert(45);
node.insert(55);
node.insert(40);
node.insert(30);
node.insert(20);
node.display(node.getRoot());
node.search(15);
}
```
* * *
## 搜索复杂度
### 时间复杂度
如果在节点内部实现线性搜索，则总复杂度为`Θ(log_t n)`。
如果使用二分搜索，则总复杂度为`Θ(log2 t x log_t n)`。
* * *
## B+ 树应用
* 多级索引
* 树上的更快操作（插入，删除，搜索）
* 数据库索引
- Programiz C 语言教程
- C 简介
- C 关键字和标识符
- C 变量，常量和字面值
- C 数据类型
- C 输入输出（I/O）
- C 编程运算符
- C 简单示例
- C 流程控制
- C if...else语句
- C for循环
- C while和do...while循环
- C break和continue
- C switch语句
- C goto声明
- C 控制流程示例
- C 函数
- C 函数
- C 用户定义的函数
- C 编程中用户定义函数的类型
- C 递归
- C 存储类
- C 函数示例
- C 数组
- C 数组
- C 多维数组
- 将数组传递给 C 中的函数
- C 编程指针
- C 指针
- 数组和指针之间的关系
- C 按引用调用：使用指针
- C 动态内存分配
- C 数组和指针示例
- C 字符串
- C 编程字符串
- 使用库函数进行 C 编程中的字符串操作
- C 编程中的字符串示例
- 结构与联合
- 结构
- 结构和指针
- C 结构与函数
- C 联合
- C 结构示例
- C 文件
- C 文件处理
- C 文件示例
- 其他主题
- 枚举
- C 预处理器和宏
- C 标准库函数
- C 示例
- C 程序：打印金字塔和图案
- C 程序：检查数字是否为质数
- C 程序：检查数字是否为回文
- C 程序：HelloWorld
- C 程序：打印整数（由用户输入）
- C 程序：相加两个整数
- C 程序：将两个浮点数相乘
- C 程序：查找字符的 ASCII 值
- C 程序：商和余数
- C 程序：查找int，float，double和char的大小
- C 程序：long关键字演示
- C 程序：交换两个数字
- C 程序：检查数字是偶数还是奇数
- C 程序：检查字符是元音还是辅音
- C 程序：查找三个数字中最大的数字
- C 程序：查找二次方程的根
- C 程序：检查闰年
- C 程序：检查数字是正数还是负数
- C 程序：检查字符是否为字母
- C 程序：计算自然数之和
- C 程序：查找数字阶乘
- C 程序：生成乘法表
- C 程序：显示斐波那契数列
- C 程序：查找两个数字的 GCD
- C 程序：查找两个数字的 LCM
- C 程序：使用循环从 A 到 Z 显示字符
- C 程序：计算整数中的位数
- C 程序：反转数字
- C 程序：计算数字的幂
- C 程序：显示两个间隔之间的质数
- C 程序：检查阿姆斯特朗数
- C 程序：在两个间隔之间显示阿姆斯特朗数
- C 程序：显示数字因数
- C 程序：使用switch...case制作一个简单的计算器
- C 程序：使用函数显示区间内的质数
- C 程序：使用用户定义的函数检查质数或阿姆斯特朗数
- C 程序：检查一个数字是否可以表示为两个质数之和
- C 程序：使用递归查找自然数之和
- C 程序：使用递归查找数字的阶乘
- C 程序：使用递归查找 GCD
- C 程序：将二进制数转换为十进制，反之亦然
- C 程序：将八进制数转换为十进制，反之亦然
- C 程序：将二进制数转换为八进制，反之亦然
- C 程序：使用递归来反转句子
- C 程序：使用递归计算幂
- C 程序：使用数组计算平均值
- C 程序：查找数组中的最大元素
- C 程序：计算标准差
- C 程序：使用多维数组相加两个矩阵
- C 程序：使用多维数组将两个矩阵相乘
- C 程序：查找矩阵的转置
- C 程序：通过将矩阵传递给函数来将两个矩阵相乘
- C 程序：使用指针访问数组元素
- C 程序：使用按引用调用以循环顺序交换数字
- C 程序：使用动态内存分配查找最大数字
- C 程序：查找字符串中字符的频率
- C 程序：计算元音，辅音等的数量
- C 程序：删除字符串中除字母之外的所有字符
- C 程序：查找字符串的长度
- C 程序：连接两个字符串
- C 程序：不使用strcpy()复制字符串
- C 程序：按字典顺序（字典顺序）对元素进行排序
- C 程序：使用程序存储学生信息
- C 程序：使用结构相加两个距离（以英寸-英尺系统为单位）
- C 程序：通过将结构传递给函数来相加两个复数
- C 程序：计算两个时间段之间的差异
- C 程序：使用结构存储学生信息
- C 程序：在结构中动态存储数据
- C 程序：将句子写入文件
- C 程序：从文件中读取一行并显示它
- C 程序：显示自己的源代码作为输出
- Programiz C++ 教程
- C++ 简介
- C++ 变量，文字和常量
- C++ 数据类型
- C++ 基本输入/输出
- C++ 类型转换
- C++ 运算符
- C++ 注释
- C++ 流控制
- C++ if，if...else和嵌套if...else
- C++ for循环
- C++ while和do...while循环
- C++ break语句
- C++ switch..case语句
- C++ goto语句
- C++ 函数
- C++ 函数
- C++ 中用户定义函数的类型
- C++ 函数重载
- C++ 编程默认参数（参数）
- C++ 存储类
- C++ 递归
- C++ 通过引用返回
- C++ 数组和字符串
- C++ 数组
- C++ 多维数组
- 在 C++ 编程中将数组传递给函数
- C++ 字符串
- C++ 结构
- C++ 结构
- C++ 结构与功能
- C++ 结构指针
- C++ 枚举
- C++ 对象和类
- C++ 类和对象
- C++ 构造器
- 如何通过 C++ 中的函数传递和返回对象？
- C++ 运算符重载
- C++ 指针
- C++ 指针
- C++ 指针和数组
- 通过引用进行 C++ 调用：使用指针[包含示例]
- C++ 内存管理：new和delete
- C++ 继承
- C++ 继承
- C++ 编程中的公共，受保护和私有继承
- C++ 函数覆盖
- C++ 多重，多层和层次继承
- C++ 友元函数和友元类
- C++ 虚函数
- C++ 模板
- C++ 示例
- C++ 程序：HelloWorld
- C++ 程序：检查数字是否为质数
- C++ 程序：创建金字塔和图案
- C++ 程序：加两个数字
- C++ 程序：打印用户输入的数字
- C++ 程序：查找商数和余数
- C++ 程序：在系统中查找int，float，double和char的大小
- C++ 程序：交换两个数字
- C++ 程序：检查数字是偶数还是奇数
- C++ 程序：检查字符是元音还是辅音
- C++ 程序：查找三个数字中最大的数字
- C++ 程序：查找二次方程式的所有根
- C++ 程序：计算自然数之和
- C++ 程序：检查闰年
- C++ 程序：查找阶乘
- C++ 程序：生成乘法表
- C++ 程序：显示斐波那契数列
- C++ 程序：查找 GCD
- C++ 程序：查找 LCM
- C++ 程序：反转数字
- C++ 程序：计算数字的幂
- C++ 程序：递增++和递减--运算符重载
- C++ 程序：使用运算符重载减去复数
- C++ 程序：查找字符的 ASCII 值
- C++ 程序：将两个数相乘
- C++ 程序：检查数字是否为回文
- C++ 程序：显示两个间隔之间的质数
- C++ 程序：检查阿姆斯特朗数
- C++ 程序：显示两个间隔之间的阿姆斯特朗数
- C++ 程序：显示数字的因数
- C++ 程序：使用switch...case的简单的加减乘除计算器
- C++ 程序：使用函数显示两个时间间隔之间的质数
- C++ 程序：通过创建函数来检查质数
- C++ 程序：检查数字是否可以表示为两个质数之和
- C++ 程序：使用递归查找自然数之和
- C++ 程序：使用递归计算数字的阶乘
- C++ 程序：使用递归查找 GCD
- C++ 程序：将二进制数转换为十进制，反之亦然
- C++ 程序：将八进制数转换为十进制，反之亦然
- C++ 程序：将二进制数转换为八进制，反之亦然
- C++ 程序：使用递归来反转句子
- C++ 程序：使用递归计算幂
- C++ 程序：使用数组计算数字平均值
- C++ 程序：查找数组的最大元素
- C++ 程序：计算标准差
- C++ 程序：使用多维数组相加两个矩阵
- C++ 程序：使用多维数组将两个矩阵相乘
- C++ 程序：查找矩阵的转置
- C++ 程序：通过将矩阵传递给函数将两个矩阵相乘
- C++ 程序：使用指针访问数组元素
- C++ 程序：使用引用调用以循环顺序交换数字
- C++ 程序：查找字符串中字符的频率
- C++ 程序：查找字符串中元音，辅音，数字和空白的数量
- C++ 程序：删除字符串中除字母之外的所有字符
- C++ 程序：查找字符串的长度
- C++ 程序：连接两个字符串
- C++ 程序：复制字符串
- C++ 程序：按字典顺序（字典顺序）对元素进行排序
- C++ 程序：在结构中存储学生的信息
- C++ 程序：使用结构相加两个距离（以英寸-英尺为单位）
- C++ 程序：通过将结构传递给函数来添加复数
- C++ 程序：计算两个时间段之间的差异
- C++ 程序：使用结构存储和显示信息
- Programiz C# 教程
- 简介
- C# Hello World - 您的第一个 C# 程序
- C# 关键字和标识符
- C# 变量和（原始）数据类型
- C# 运算符
- C# 基本输入和输出
- C# 表达式，语句和块（带有示例）
- C# 注释
- 流程控制
- C# if，if...else，if...else if和嵌套if语句
- C# for循环
- C# while和do...while循环
- C# foreach循环
- C# switch语句
- C# 三元（?:）运算符
- 其他话题
- C# 按位和移位运算符
- C# 预处理程序指令
- C# 编程中的命名空间
- C# 部分类和部分方法
- Programiz 数据结构和算法教程
- DSA 简介
- 什么是算法？
- 为什么要学习数据结构和算法？
- 渐近分析
- 主定理
- 分治算法
- 数据结构（一）
- 栈
- 队列
- 队列类型
- 循环队列
- 优先队列
- 双端队列
- 数据结构（二）
- 链表
- 链表操作：遍历，插入和删除
- 链表的类型 - 单链，双链和循环链
- 哈希表
- 堆数据结构
- 斐波那契堆
- 减小斐波那契堆上的键和删除节点的操作
- 基于树的 DSA（I）
- 树数据结构
- 树遍历 - 中序，前序和后序
- 满二叉树
- 满二叉树
- 完美二叉树
- 完全二叉树
- 平衡二叉树
- 二叉搜索树（BST）
- AVL 树
- 基于树的 DSA（II）
- B 树
- 插入 B 树
- 从 B 树删除
- B+ 树
- 在 B+ 树上插入
- 从 B+ 树中删除
- 红黑树
- 插入红黑树
- 从红黑树中删除
- 基于图的 DSA
- 图数据结构
- 生成树和最小生成树
- 强连通的组件
- 邻接矩阵
- 邻接表
- DFS 算法
- BFS 算法
- Bellman Ford 算法
- 排序和搜索算法
- 冒泡排序算法
- 选择排序算法
- 插入排序算法
- 归并排序算法
- 快速排序算法
- 计数排序算法
- 基数排序算法
- 桶排序算法
- 堆排序算法
- Shell 排序算法
- 线性搜索
- 二分搜索
- 贪婪算法
- 贪婪算法
- Ford-Fulkerson 算法
- Dijkstra 算法
- Kruskal 算法
- Prim 算法
- 霍夫曼编码
- 动态规划
- 动态规划
- Floyd-Warshall 算法
- 最长公共子序列
- 其他算法
- 回溯算法
- Rabin-Karp 算法
- Programiz Java 教程
- Java 简介
- Java HelloWorld 程序
- Java JDK，JRE 和 JVM
- Java 变量和（原始）数据类型
- Java 运算符
- Java 基本输入和输出
- Java 表达式，语句和块
- Java 注释
- Java 流程控制
- Java if，if...else语句
- Java switch语句
- Java for循环
- Java for-each循环（增强循环）
- Java while和do...while循环
- Java Break语句
- Java continue语句
- Java 数组
- Java 数组
- Java 多维数组
- Java 复制数组
- Java OOP（I）
- Java 类和对象
- Java 方法
- Java 构造器
- Java 字符串
- Java 访问修饰符
- Java this关键字
- Java final关键字
- Java 递归
- Java instanceof
- Java OOP（II）
- Java 继承
- Java 方法覆盖
- Java super
- Java 抽象类和抽象方法
- Java 接口
- Java 多态
- Java 封装
- Java OOP（III）
- Java 嵌套和内部类
- Java 静态嵌套类
- Java 匿名类
- Java 单例
- Java 枚举
- Java 枚举构造器
- Java 枚举字符串
- Java 反射
- Java 异常处理
- Java 异常
- Java 异常处理
- Java throw
- Java 捕获多个异常
- Java try-with-resources
- Java 注解
- Java 注解类型
- Java 日志
- Java 断言
- Java 列表
- Java 集合框架
- Java Collection接口
- Java List接口
- Java ArrayList类
- Java Vector
- Java Stack类
- Java 队列
- Java Queue接口
- Java PriorityQueue
- Java Deque接口
- Java LinkedList
- Java ArrayDeque
- Java BlockingQueue
- Java ArrayBlockingQueue
- Java LinkedBlockingQueue
- Java 映射
- Java Map接口
- Java HashMap
- Java LinkedHashMap
- Java WeakHashMap
- Java EnumMap
- Java SortedMap接口
- Java NavigableMap接口
- Java TreeMap
- Java ConcurrentMap接口
- Java ConcurrentHashMap
- Java 集
- Java Set接口
- Java HashSet类
- Java EnumSet
- Java LinkedHashSet
- Java SortedSet接口
- Java NavigableSet接口
- Java TreeSet
- Java 算法
- Java Iterator接口
- Java ListIterator接口
- Java I/O 流
- Java I/O 流
- Java InputStream类
- Java OutputStream类
- Java FileInputStream类
- Java FileOutputStream类
- Java ByteArrayInputStream类
- Java ByteArrayOutputStream类
- Java ObjectInputStream类
- Java ObjectOutputStream类
- Java BufferedInputStream类
- Java BufferedOutputStream类
- Java PrintStream类
- Java 读取器/写入器
- Java Reader类
- Java Writer类
- Java InputStreamReader类
- Java OutputStreamWriter类
- Java FileReader类
- Java FileWriter类
- Java BufferedReader类
- Java BufferedWriter类
- Java StringReader类
- Java StringWriter类
- Java PrintWriter类
- 其他主题
- Java Scanner类
- Java 类型转换
- Java 自动装箱和拆箱
- Java Lambda 表达式
- Java 泛型
- Java File类
- Java 包装器类
- Java 命令行参数
- Java 实例
- Java 程序：检查数字是否为质数
- Java 程序：显示斐波那契数列
- Java 程序：创建金字塔和图案
- Java 程序：反转数字
- Java 程序：打印整数（由用户输入）
- Java 程序：相加两个整数
- Java 程序：将两个浮点数相乘
- Java 程序：查找字符的 ASCII 值
- Java 程序：计算商数和余数
- Java 程序：交换两个数字
- Java 程序：检查数字是偶数还是奇数
- Java 程序：检查字母是元音还是辅音
- Java 程序：在三个数字中找到最大值
- Java 程序：查找二次方程式的所有根
- Java 程序：检查闰年
- Java 程序：检查数字是正数还是负数
- Java 程序：检查字符是否为字母
- Java 程序：计算自然数之和
- Java 程序：查找数字的阶乘
- Java 程序：生成乘法表
- Java 程序：显示斐波那契数列
- Java 程序：查找两个数字的 GCD
- Java 程序：查找两个数字的 LCM
- Java 程序：使用循环从 A 到 Z 显示字符
- Java 程序：计算整数的位数
- Java 程序：计算数字的幂
- Java 程序：检查数字是否为回文
- Java 程序：检查数字是否为质数
- Java 程序：显示两个时间间隔之间的质数
- Java 程序：检查阿姆斯特朗数
- Java 程序：显示两个间隔之间的阿姆斯特朗数
- Java 程序：使用函数显示间隔之间的质数
- Java 程序：使用函数显示间隔之间的阿姆斯特朗数
- Java 程序：以显示数字的因数
- Java 程序：使用switch...case创建一个简单的计算器
- Java 程序：检查一个数字是否可以表示为两个质数之和
- Java 程序：使用递归查找自然数之和
- Java 程序：使用递归查找数字的阶乘
- Java 程序：使用递归查找 GCD
- Java 程序：将二进制数转换为十进制，反之亦然
- Java 程序：将八进制数转换为十进制，反之亦然
- Java 程序：将二进制数转换为八进制，反之亦然
- Java 程序：使用递归来反转句子
- Java 程序：使用递归来计算幂
- Java 程序：使用数组计算平均值
- Java 程序：查找数组的最大元素
- Java 程序：计算标准差
- Java 程序：使用多维数组相加两个矩阵
- Java 程序：使用多维数组相乘矩阵
- Java 程序：通过将矩阵传递给函数来将两个矩阵相乘
- Java 程序：查找矩阵转置
- Java 程序：查找字符串中字符的频率
- Java 程序：计算句子中元音和辅音的数量
- Java 程序：按字典顺序对元素进行排序
- Java 程序：通过将对象传递给函数来相加两个复数
- Java 程序：计算两个时间段之间的差异
- Java 程序：从字符串中删除所有空格
- Java 程序：打印数组
- Java 程序：将字符串转换为日期
- Java 程序：将数字四舍五入到 n 个小数位
- Java 程序：连接两个数组
- Java 程序：将字符转换为字符串，反之亦然
- Java 程序：检查数组是否包含给定值
- Java 程序：检查字符串是否为空或null
- Java 程序：获取当前日期/时间
- Java 程序：将毫秒转换为分钟和秒
- Java 程序：相加两个日期
- Java 程序：连接两个列表
- Java 程序：将列表（ArrayList）转换为数组，反之亦然
- Java 程序：获取当前工作目录
- Java 程序：将映射（HashMap）转换为列表
- Java 程序：将数组转换为集（HashSet），反之亦然
- Java 程序：将字节数组转换为十六进制
- Java 程序：从文件内容创建字符串
- Java 程序：将文本附加到现有文件
- Java 程序：将栈跟踪转换为字符串
- Java 程序：将文件转换为字节数组，反之亦然
- Java 程序：将InputStream转换为字符串
- Java 程序：将OutputStream转换为字符串
- Java 程序：按字符串值查找枚举
- Java 程序：比较字符串
- Java 程序：按值对映射进行排序
- Java 程序：按属性对自定义对象的ArrayList进行排序
- Java 程序：检查字符串是否为数字
- Java 程序：创建目录
- Java 程序：重命名文件
- Java 程序：列出目录中的文件
- Java 程序：复制文件
- Programiz Kotlin 教程
- Kotlin 简介
- Kotlin HelloWorld - 您的 Kotlin 程序
- Kotlin 变量和原始类型
- Kotlin 运算符
- Kotlin 类型转换
- Kotlin 表达式，语句和块
- Kotlin 注释
- Kotlin 基本输入/输出
- Kotlin 流程控制
- Kotlin if表达式
- Kotlin when表达式
- Kotlin while和do...while循环
- Kotlin for循环
- Kotlin break表达式
- Kotlin continue表达式
- Kotlin 函数
- Kotlin 函数
- Kotlin 中缀函数调用
- Kotlin 默认和命名参数
- Kotlin 递归（递归函数）和尾递归
- Kotlin OOP
- Kotlin 类和对象
- Kotlin 构造器
- Kotlin 获取器和设置器
- Kotlin 继承
- Kotlin 可见性修饰符
- Kotlin 抽象类
- Kotlin 接口
- Kotlin 嵌套和内部类
- Kotlin 数据类
- Kotlin 密封类
- Kotlin 对象声明和表达式
- Kotlin 伴随对象
- Kotlin 扩展函数
- Kotlin 运算符重载
- Kotlin 示例
- Kotlin 程序：获取当前日期/时间
- Kotlin 程序：将列表（ArrayList）转换为Array，反之亦然
- Kotlin 程序：将字符串转换为日期
- Kotlin 程序：按属性对自定义对象的ArrayList进行排序
- Kotlin 程序：打印整数（由用户输入）
- Kotlin 程序：相加两个整数
- Kotlin 程序：将两个浮点数相乘
- Kotlin 程序：查找字符的 ASCII 值
- Kotlin 程序：计算商数和余数
- Kotlin 程序：交换两个数字
- Kotlin 程序：检查数字是偶数还是奇数
- Kotlin 程序：检查字母是元音还是辅音
- Kotlin 程序：在三个数字中找到最大的一个
- Kotlin 程序：查找二次方程的所有根
- Kotlin 程序：检查闰年
- Kotlin 程序：检查数字是正数还是负数
- Kotlin 程序：检查字符是否为字母
- Kotlin 程序：计算自然数之和
- Kotlin 程序：查找数字的阶乘
- Kotlin 程序：生成乘法表
- Kotlin 程序：展示斐波那契数列
- Kotlin 程序：查找两个数字的 GCD
- Kotlin 程序：查找两个数字的 LCM
- Kotlin 程序：使用循环从 A 到 Z 显示字符
- Kotlin 程序：计算整数位数
- Kotlin 程序：反转数字
- Kotlin 程序：计算数字的幂
- Kotlin 程序：检查数字是否为回文
- Kotlin 程序：检查数字是否为质数
- Kotlin 程序：显示两个间隔之间的质数
- Kotlin 程序：检查阿姆斯特朗数
- Kotlin 程序：显示两个间隔之间的阿姆斯特朗数
- Kotlin 程序：使用函数显示间隔之间的质数
- Kotlin 程序：使用函数显示间隔之间的阿姆斯特朗数
- Kotlin 程序：显示数字因数
- Kotlin 程序：使用switch...case制作一个简单的计算器
- Kotlin 程序：检查一个数字是否可以表示为两个质数之和
- Kotlin 程序：使用递归找到自然数之和
- Kotlin 程序：使用递归查找数字的阶乘
- Kotlin 程序：使用递归查找 GCD
- Kotlin 程序：将二进制数转换为十进制，反之亦然
- Kotlin 程序：将八进制数转换为十进制，反之亦然
- Kotlin 程序：将二进制数转换为八进制，反之亦然
- Kotlin 程序：使用递归来反转句子
- Kotlin 程序：使用递归来计算幂
- Kotlin 程序：使用数组计算平均值
- Kotlin 程序：在数组中查找最大的元素
- Kotlin 程序：计算标准差
- Kotlin 程序：使用多维数组相加两个矩阵
- Kotlin 程序：使用多维数组乘以矩阵
- Kotlin 程序：通过将矩阵传递给函数来将两个矩阵相乘
- Kotlin 程序：查找矩阵的转置
- Kotlin 程序：查找字符串中字符的频率
- Kotlin 程序：计算句子中元音和辅音的数量
- Kotlin 程序：按字典顺序（字典顺序）对元素进行排序
- Kotlin 程序：通过将类传递给函数来相加两个复数
- Kotlin 程序：计算两个时间段之间的差异
- Kotlin 程序：创建金字塔和图案
- Kotlin 程序：从字符串中删除所有空格
- Kotlin 程序：打印数组
- Kotlin 程序：将数字四舍五入到 n 个小数位
- Kotlin 程序：连接两个数组
- Kotlin 程序：将字符转换为字符串并反之
- Kotlin 程序：检查数组是否包含给定值
- Kotlin 程序：检查字符串是否为空或null
- Kotlin 程序：将毫秒转换为分钟
- Kotlin 程序：相加两个日期
- Kotlin 程序：连接两个列表
- Kotlin 程序：获取当前工作目录
- Kotlin 程序：将映射（HashMap）转换为列表
- Kotlin 程序：将数组转换为Set（HashSet），反之亦然
- Kotlin 程序：将字节数组转换为十六进制
- Kotlin 程序：从文件内容创建字符串
- Kotlin 程序：将文本附加到现有文件
- Kotlin 程序：将栈跟踪转换为字符串
- Kotlin 程序：将文件转换为字节数组，反之亦然
- Kotlin 程序：将InputStream转换为字符串
- Kotlin 程序：将OutputStream转换为字符串
- Kotlin 程序：通过字符串值查找枚举
- Kotlin 程序：比较字符串
- Kotlin 程序：按值对映射排序
- Kotlin 程序：检查字符串是否为数字
- Programiz Python 教程
- Python 简介
- 如何开始使用 Python？
- Python 关键字和标识符
- Python 语句，缩进和注释
- Python 变量，常量和字面值
- Python 数据类型
- Python 类型转换
- Python 输入，输出和导入
- Python 运算符
- Python 命名空间和范围
- Python 流程控制
- Python if...else语句
- Python for循环
- Python While循环
- Python break和continue
- Python pass语句
- Python 函数
- Python 函数
- Python 函数参数
- Python 递归
- Python 匿名/ Lambda 函数
- Python 全局，局部和非局部变量
- Python global关键字
- Python 模块
- Python 包
- Python 数据类型
- Python 数字，类型转换和数学
- Python 列表
- Python 元组
- Python 字符串
- Python 集
- Python 字典
- Python 文件
- Python 文件 I/O
- Python 目录和文件管理
- Python 错误和内置异常
- Python 使用try，except和finally语句的异常处理
- Python 自定义异常
- Python 对象和类
- Python 面向对象编程
- Python 对象和类
- Python 继承
- Python 多重继承
- Python 运算符重载
- Python 高级主题
- Python 迭代器
- Python 生成器
- Python 闭包
- Python 装饰器
- Python @property装饰器
- Python 正则表达式
- Python 日期时间
- Python 日期时间
- Python strftime()
- Python strptime()
- 如何在 Python 中获取当前日期和时间？
- Python 获取当前时间
- Python 日期时间到时间戳，反之亦然
- Python time模块
- Python sleep()
- Python 示例
- Python 程序：检查质数
- Python 程序：相加两个数字
- Python 程序：查找数字阶乘
- Python 程序：制作一个简单的计算器
- Python 程序：打印 Helloworld
- Python 程序：查找平方根
- Python 程序：计算三角形的面积
- Python 程序：求解二次方程式
- Python 程序：交换两个变量
- Python 程序：生成随机数
- Python 程序：将公里转换为英里
- Python 程序：将摄氏温度转换为华氏温度
- Python 程序：检查数字是正数，负数还是 0
- Python 程序：检查数字是奇数还是偶数
- Python 程序：检查闰年
- Python 程序：在三个数字中找到最大的
- Python 程序：检查质数
- Python 程序：打印一个间隔内的所有质数
- Python 程序：查找数字阶乘
- Python 程序：显示乘法表
- Python 程序：打印斐波那契序列
- Python 程序：检查阿姆斯特朗数
- Python 程序：查找间隔内的阿姆斯特朗数
- Python 程序：查找自然数总和
- Python 程序：使用匿名函数显示 2 的幂
- Python 程序：查找可被另一个数整除的数字
- Python 程序：将十进制转换为二进制，八进制和十六进制
- Python 程序：查找字符的 ASCII 值
- Python 程序：查找 HCF 或 GCD
- Python 程序：查找 LCM
- Python 程序：查找数字的因数
- Python 程序：制作一个简单的计算器
- Python 程序：打乱纸牌
- Python 程序：显示日历
- Python 程序：使用递归显示斐波那契数列
- Python 程序：使用递归查找自然数之和
- Python 程序：使用递归查找数字的阶乘
- Python 程序：使用递归将十进制转换为二进制
- Python 程序：相加两个矩阵
- Python 程序：转置矩阵
- Python 程序：将两个矩阵相乘
- Python 程序：检查字符串是否为回文
- Python 程序：从字符串中删除标点符号
- Python 程序：按字母顺序对单词进行排序
- Python 程序：演示不同的集合操作
- Python 程序：计算每个元音的数量
- Python 程序：合并邮件
- Python 程序：查找图像的大小（分辨率）
- Python 程序：查找文件哈希
- Programiz Swift 教程
- Swift 介绍
- Swift HelloWorld 程序
- Swift 变量，常量和字面值
- Swift 数据类型
- Swift 可选项
- Swift 的字符和字符串
- Swift 基本输入和输出
- Swift 表达式，语句和代码块
- Swift 注释
- Swift 运算符
- Swift 运算符
- Swift 运算符的优先级和关联性
- Swift 三元条件运算符
- Swift 按位和移位运算符
- Seift 流程控制
- Swift if，if...else语句
- switch语句
- Swift for-in循环
- Swift while和repeat...while循环
- Swift 中的嵌套循环
- break语句
- continue语句
- Guard语句
- Swift 集合
- Swift 数组
- Swift 集
- Swift 字典
- Swift 函数
- Swift 函数
- Swift 函数参数和返回值
- Swift 嵌套函数
- Swift 递归
- Swift 范围
- Swift 函数重载
- Swift 进阶
- Swift 闭包
- Swift 类型别名