- 数据结构与算法
- DSA - 主页
- DSA - 概述
- DSA - 环境设置
- 数据结构
- DSA - 数据结构基础知识
- DSA - 数据结构和类型
- DSA - 数组数据结构
- 链表
- DSA - 链表基础知识
- DSA - 双向链表
- DSA - 循环链表
- 堆栈和队列
- DSA - 堆栈
- DSA - 表达式解析
- DSA-队列
- 图数据结构
- DSA - 图数据结构
- DSA-深度优先遍历
- DSA-广度优先遍历
- DSA——生成树
- 树数据结构
- DSA - 树数据结构
- DSA - 树遍历
- DSA - 二叉搜索树
- DSA - AVL 树
- DSA - 红黑树
- DSA - B 树
- DSA - B+ 树
- DSA - 八字树
- DSA - 尝试
- DSA-堆
- 递归
- DSA - 递归基础知识
- DSA - 河内塔
- DSA - 斐波那契数列
- DSA 有用资源
- DSA - 问题与解答
- DSA - 快速指南
- DSA - 有用的资源
- DSA - 讨论
数据结构和算法 - B 树
B 树是扩展的二叉搜索树,专门用于 m 路搜索,因为 B 树的顺序是“m”。树的阶数定义为节点可以容纳的最大子节点数。因此,ab树的高度相对小于AVL树和RB树的高度。
它们是二叉搜索树的一般形式,因为它包含多个键和两个子项。
B 树的各种属性包括 -
B 树中的每个节点最多可容纳 m 个子节点和 (m-1) 个键,因为树的顺序为 m。
B 树中的每个节点(除了根和叶)至少可以容纳 m/2 个子节点
根节点必须有不少于两个子节点。
B树中的所有路径必须在同一层结束,即叶节点必须在同一层。
AB 树始终维护排序的数据。
B树也广泛应用于磁盘访问,由于ab树的高度较低,可以最大限度地减少磁盘访问时间。
注- 磁盘访问是对存储信息的计算机磁盘的内存访问,磁盘访问时间是系统访问磁盘内存所花费的时间。
B树的基本操作
B树支持的操作有插入、删除和搜索,每个操作的时间复杂度为O(log n) 。
插入
B 树的插入操作与二叉搜索树类似,但元素被插入到同一节点中,直到达到最大键数。插入是使用以下过程完成的 -
步骤 1 - 计算最大值 $\mathrm{\left ( m-1 \right )}$ 和最小值 $\mathrm{\left ( \left \lceil \frac{m}{2}\right \rceil-1 \right )}$ 一个节点可以保存的键的数量,其中 m 由 B 树的阶数表示。
步骤 2 - 使用二分搜索插入将数据插入到树中,一旦键达到最大数量,节点就会分成两半,中间键成为内部节点,而左右键成为其子节点。
步骤 3 - 所有叶节点必须位于同一级别。
键 5、3、21、9、13 都根据二分查找属性添加到节点中,但如果我们添加键 22,则会违反最大键属性。因此,节点被分成两半,中值键被转移到父节点,然后继续插入。
在插入 11 的过程中发生了另一个问题,因此该节点被分裂,中位数被转移到父节点。
当插入16时,即使节点被分成两部分,父节点也会因为达到最大键值而溢出。因此,父节点首先被分裂,中值键成为根。然后,叶节点被分成两半,叶节点的中位数移至其父节点。
插入所有元素后就得到了最终的B树。
例子
// Insert the value void insertion(int item) { int flag, i; struct btreeNode *child; flag = setNodeValue(item, &i, root, &child); if (flag) root = createNode(i, child); }
删除
B树中的删除操作与二叉搜索树的删除操作略有不同。从 B 树中删除节点的过程如下 -
情况 1 - 如果要删除的键位于叶节点中,并且删除不违反最小键属性,则只需删除该节点。
情况 2 - 如果要删除的键位于叶节点中,但删除违反了最小键属性,则从其左同级或右同级借用键。如果两个同级节点都有确切的最小数量的键,则合并其中一个节点中的节点。
情况 3 - 如果要删除的键位于内部节点中,则根据哪个子节点拥有更多键,将其替换为左子节点或右子节点中的键。但如果两个子节点都有最小数量的键,它们就会合并在一起。
情况 4 - 如果要删除的键位于违反最小键属性的内部节点中,并且其子节点和兄弟节点都具有最小数量的键,则合并子节点。然后将其兄弟与其父级合并。
以下是 B 树中删除操作的功能 C++ 代码片段 -
// Deletion operation void deletion(int key){ int index = searchkey(key); if (index < n && keys[index] == key) { if (leaf) deletion_at_leaf(index); else deletion_at_nonleaf(index); } else { if (leaf) { cout << "key " << key << " does not exist in the tree\n"; return; } bool flag = ((index == n) ? true : false); if (C[index]->n < t) fill(index); if (flag && index > n) C[index - 1]->deletion(key); else C[index]->deletion(key); } return; } // Deletion at the leaf nodes void deletion_at_leaf(int index){ for (int i = index + 1; i < n; ++i) keys[i - 1] = keys[i]; n--; return; } // Deletion at the non leaf node void deletion_at_nonleaf(int index){ int key = keys[index]; if (C[index]->n >= t) { int pred = get_Predecessor(index); keys[index] = pred; C[index]->deletion(pred); } else if (C[index + 1]->n >= t) { int successor = copysuccessoressor(index); keys[index] = successor; C[index + 1]->deletion(successor); } else { merge(index); C[index]->deletion(key); } return; }
例子
// C Program for B trees #include <stdio.h> #include <stdlib.h> struct BTree { //node declaration int *d; struct BTree **child_ptr; int l; int n; }; struct BTree *r = NULL; struct BTree *np = NULL; struct BTree *x = NULL; //creation of node struct BTree* init() { int i; np = (struct BTree*)malloc(sizeof(struct BTree)); //order 6 np->d = (int*)malloc(6 * sizeof(int)); np->child_ptr = (struct BTree**)malloc(7 * sizeof(struct BTree*)); np->l = 1; np->n = 0; for (i = 0; i < 7; i++) { np->child_ptr[i] = NULL; } return np; } //traverse the tree void traverse(struct BTree *p) { printf("\n"); int i; for (i = 0; i < p->n; i++) { if (p->l == 0) { traverse(p->child_ptr[i]); } printf(" %d", p->d[i]); } if (p->l == 0) { traverse(p->child_ptr[i]); } printf("\n"); } //sort the tree void sort(int *p, int n) { int i, j, t; for (i = 0; i < n; i++) { for (j = i; j <= n; j++) { if (p[i] > p[j]) { t = p[i]; p[i] = p[j]; p[j] = t; } } } } int split_child(struct BTree *x, int i) { int j, mid; struct BTree *np1, *np3, *y; np3 = init(); //create new node np3->l = 1; if (i == -1) { mid = x->d[2]; //find mid x->d[2] = 0; x->n--; np1 = init(); np1->l = 0; x->l = 1; for (j = 3; j < 6; j++) { np3->d[j - 3] = x->d[j]; np3->child_ptr[j - 3] = x->child_ptr[j]; np3->n++; x->d[j] = 0; x->n--; } for (j = 0; j < 6; j++) { x->child_ptr[j] = NULL; } np1->d[0] = mid; np1->child_ptr[np1->n] = x; np1->child_ptr[np1->n + 1] = np3; np1->n++; r = np1; } else { y = x->child_ptr[i]; mid = y->d[2]; y->d[2] = 0; y->n--; for (j = 3; j < 6; j++) { np3->d[j - 3] = y->d[j]; np3->n++; y->d[j] = 0; y->n--; } x->child_ptr[i + 1] = y; x->child_ptr[i + 1] = np3; } return mid; } void insert(int a) { int i, t; x = r; if (x == NULL) { r = init(); x = r; } else { if (x->l == 1 && x->n == 6) { t = split_child(x, -1); x = r; for (i = 0; i < x->n; i++) { if (a > x->d[i] && a < x->d[i + 1]) { i++; break; } else if (a < x->d[0]) { break; } else { continue; } } x = x->child_ptr[i]; } else { while (x->l == 0) { for (i = 0; i < x->n; i++) { if (a > x->d[i] && a < x->d[i + 1]) { i++; break; } else if (a < x->d[0]) { break; } else { continue; } } if (x->child_ptr[i]->n == 6) { t = split_child(x, i); x->d[x->n] = t; x->n++; continue; } else { x = x->child_ptr[i]; } } } } x->d[x->n] = a; sort(x->d, x->n); x->n++; } int main() { int i, n, t; insert(10); insert(20); insert(30); insert(40); insert(50); printf("B tree:\n"); traverse(r); return 0; }
输出
B tree: 10 20 30 40 50
#include<iostream> using namespace std; struct BTree {//node declaration int *d; BTree **child_ptr; bool l; int n; }*r = NULL, *np = NULL, *x = NULL; BTree* init() {//creation of node int i; np = new BTree; np->d = new int[6];//order 6 np->child_ptr = new BTree *[7]; np->l = true; np->n = 0; for (i = 0; i < 7; i++) { np->child_ptr[i] = NULL; } return np; } void traverse(BTree *p) { //traverse the tree cout<<endl; int i; for (i = 0; i < p->n; i++) { if (p->l == false) { traverse(p->child_ptr[i]); } cout << " " << p->d[i]; } if (p->l == false) { traverse(p->child_ptr[i]); } cout<<endl; } void sort(int *p, int n){ //sort the tree int i, j, t; for (i = 0; i < n; i++) { for (j = i; j <= n; j++) { if (p[i] >p[j]) { t = p[i]; p[i] = p[j]; p[j] = t; } } } } int split_child(BTree *x, int i) { int j, mid; BTree *np1, *np3, *y; np3 = init();//create new node np3->l = true; if (i == -1) { mid = x->d[2];//find mid x->d[2] = 0; x->n--; np1 = init(); np1->l= false; x->l= true; for (j = 3; j < 6; j++) { np3->d[j - 3] = x->d[j]; np3->child_ptr[j - 3] = x->child_ptr[j]; np3->n++; x->d[j] = 0; x->n--; } for (j = 0; j < 6; j++) { x->child_ptr[j] = NULL; } np1->d[0] = mid; np1->child_ptr[np1->n] = x; np1->child_ptr[np1->n + 1] = np3; np1->n++; r = np1; } else { y = x->child_ptr[i]; mid = y->d[2]; y->d[2] = 0; y->n--; for (j = 3; j <6 ; j++) { np3->d[j - 3] = y->d[j]; np3->n++; y->d[j] = 0; y->n--; } x->child_ptr[i + 1] = y; x->child_ptr[i + 1] = np3; } return mid; } void insert(int a) { int i, t; x = r; if (x == NULL) { r = init(); x = r; } else { if (x->l== true && x->n == 6) { t = split_child(x, -1); x = r; for (i = 0; i < (x->n); i++) { if ((a >x->d[i]) && (a < x->d[i + 1])) { i++; break; } else if (a < x->d[0]) { break; } else { continue; } } x = x->child_ptr[i]; } else { while (x->l == false) { for (i = 0; i < (x->n); i++) { if ((a >x->d[i]) && (a < x->d[i + 1])) { i++; break; } else if (a < x->d[0]) { break; } else { continue; } } if ((x->child_ptr[i])->n == 6) { t = split_child(x, i); x->d[x->n] = t; x->n++; continue; } else { x = x->child_ptr[i]; } } } } x->d[x->n] = a; sort(x->d, x->n); x->n++; } int main() { int i, n, t; insert(10); insert(20); insert(30); insert(40); insert(50); cout<<"B tree:\n"; traverse(r); }
输出
B tree: 10 20 30 40 50
//Java code for B trees import java.util.Arrays; class BTree { private int[] d; private BTree[] child_ptr; private boolean l; private int n; public BTree() { d = new int[6]; // order 6 child_ptr = new BTree[7]; l = true; n = 0; Arrays.fill(child_ptr, null); } public void traverse() { System.out.println("B tree: "); for (int i = 0; i < n; i++) { if (!l) { child_ptr[i].traverse(); } System.out.print(d[i] + " "); } if (!l) { child_ptr[n].traverse(); } System.out.println(); } public void sort() { Arrays.sort(d, 0, n); } public int splitChild(int i) { int j, mid; BTree np1, np3, y; np3 = new BTree(); np3.l = true; if (i == -1) { mid = d[2]; d[2] = 0; n--; np1 = new BTree(); np1.l = false; l = true; for (j = 3; j < 6; j++) { np3.d[j - 3] = d[j]; np3.n++; d[j] = 0; n--; } for (j = 0; j < 6; j++) { np3.child_ptr[j] = child_ptr[j + 3]; child_ptr[j + 3] = null; } np1.d[0] = mid; np1.child_ptr[0] = this; np1.child_ptr[1] = np3; np1.n++; return mid; } else { y = child_ptr[i]; mid = y.d[2]; y.d[2] = 0; y.n--; for (j = 3; j < 6; j++) { np3.d[j - 3] = y.d[j]; np3.n++; y.d[j] = 0; y.n--; } child_ptr[i + 1] = y; child_ptr[i + 2] = np3; return mid; } } public void insert(int a) { int i, t; BTree x = this; if (x.l && x.n == 6) { t = x.splitChild(-1); x = this; for (i = 0; i > x.n; i++) { if (a > x.d[i] && a < x.d[i + 1]) { i++; break; } else if (a < x.d[0]) { break; } } x = x.child_ptr[i]; } else { while (!x.l) { for (i = 0; i < x.n; i++) { if (a > x.d[i] && a < x.d[i + 1]) { i++; break; } else if (a < x.d[0]) { break; } } if (x.child_ptr[i].n == 6) { t = x.splitChild(i); x.d[x.n] = t; x.n++; continue; } x = x.child_ptr[i]; } } x.d[x.n] = a; x.sort(); x.n++; } } public class Main { public static void main(String[] args) { BTree bTree = new BTree(); bTree.insert(20); bTree.insert(10); bTree.insert(40); bTree.insert(30); bTree.insert(50); // Duplicate value, ignored //call the traverse method bTree.traverse(); } }
输出
B tree: 10 20 30 40 50
#python program for B treesa class BTree: def __init__(self): #node declartion self.d = [0] * 6 self.child_ptr = [None] * 7 self.l = True self.n = 0 #creation of node def init(): np = BTree() np.l = True np.n = 0 return np #traverse the tree def traverse(p): if p is not None: for i in range(p.n): if not p.l: traverse(p.child_ptr[i]) print(p.d[i], end=" ") if not p.l: traverse(p.child_ptr[p.n]) #sort the tree def sort(p, n): for i in range(n): for j in range(i, n+1): if p[i] > p[j]: p[i], p[j] = p[j], p[i] def split_child(x, i): np3 = init() #create new node np3.l = True if i == -1: mid = x.d[2] #find mid x.d[2] = 0 x.n -= 1 np1 = init() np1.l = False x.l = True for j in range(3, 6): np3.d[j-3] = x.d[j] np3.child_ptr[j-3] = x.child_ptr[j] np3.n += 1 x.d[j] = 0 x.n -= 1 for j in range(6): x.child_ptr[j] = None np1.d[0] = mid np1.child_ptr[np1.n] = x np1.child_ptr[np1.n + 1] = np3 np1.n += 1 return np1 else: y = x.child_ptr[i] mid = y.d[2] y.d[2] = 0 y.n -= 1 for j in range(3, 6): np3.d[j-3] = y.d[j] np3.n += 1 y.d[j] = 0 y.n -= 1 x.child_ptr[i + 1] = y x.child_ptr[i + 1] = np3 return mid def insert(a): global r, x if r is None: r = init() x = r else: if x.l and x.n == 6: t = split_child(x, -1) x = r for i in range(x.n): if a > x.d[i] and a < x.d[i + 1]: i += 1 break elif a < x.d[0]: break else: continue x = x.child_ptr[i] else: while not x.l: for i in range(x.n): if a > x.d[i] and a < x.d[i + 1]: i += 1 break elif a < x.d[0]: break else: continue if x.child_ptr[i].n == 6: t = split_child(x, i) x.d[x.n] = t x.n += 1 continue else: x = x.child_ptr[i] x.d[x.n] = a sort(x.d, x.n) x.n += 1 if __name__ == '__main__': r = None x = None insert(10) insert(20) insert(30) insert(40) insert(50) print("B tree:") traverse(r)
输出
B tree: 10 20 30 40 50