数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究数据结构中的B树插入
在这里，我们将了解如何在B树中执行插入操作。假设我们有一个如下所示的B树：
B树示例 −
插入元素的思路与BST非常相似，但我们需要遵循一些规则。每个节点有m个子节点和m-1个元素。如果我们将一个元素插入到一个节点中，则有两种情况。如果节点的元素少于m-1，则新元素将直接插入到该节点中。如果它有m-1个元素，那么通过取所有元素以及将要插入的元素，然后取它们的中间值，并将中间值通过执行相同的标准发送到该节点的根节点，然后从节点的左半部分和右半部分创建两个单独的列表。
假设我们要将79插入到树中。首先，它将与根节点进行比较，它大于56。然后它将进入最右边的子树。现在它小于81，因此移动到左子树。之后，它将被插入到根节点。现在有三个元素[66, 78, 79]。中位数是78，所以78将向上移动，根节点变为[79, 81]，节点的元素将被分成两个节点。一个将包含66，另一个将包含79。
插入79后的B树。
算法
BTreeInsert(root, key)−
输入 − 树的根节点以及要插入的键。我们将假设该键不在列表中。
x := Read root if x is full, then y := new node z := new node Locate the middle object oi, stored in x, move the objects to the left of oi in to node y Move the object to the right of oi into node z. If x is an index node, then move the child pointers accordingly x->child[1] := address of y x->child[2] := address of z end if
更新于: 2020年8月11日
701 次查看
广告