🥳每日一练-B树的创建-JS不难版-六虎

假如你是一个了解 B 树的性质，正在寻觅代码怎样完成的同学，那这篇文章便是为你预备的

这篇文章来分享一个杂乱度稍弱于红黑树难度的数据结构–B 树

什么是 B 树？

简略来说，B树是一个特别的查找多叉树。相比于查找二叉树，查找多叉树也满足左节点 < 根节点 < 右节这样的性质，与之不同的是查找多叉树有多个分支，根节点的要害词也能够有多个，就像下图所示。

相关于普通的查找树，B树的要求会愈加严厉。下面是 B树性质的介绍：

在这样的严厉要求之下，关于 B树就能够推出它的核心特性：

上面的截图均来自 B站的王道数据结构视频课：王道-7.4_2_B树的刺进删除

假设一个 B树的阶是 5，那么根节点的要害词个数范围便是[1, m-1], 非根节点的要害词个数的范围是 [2, 4]，恣意非叶节点的分支个数的范围是 [3, 5]。

而且全部的子树的高度都相同，这个比 AVL 平衡二叉树的要求愈加严厉。一颗 AVL 只要求左右子树的要读差不超越 1 。不过这样的严厉要求也为代码的编写带来了方便。

下面我们一起来看看代码怎样写吧

预备数据

class BTreeNode {
	constructor() {
		this.keys = [];
		this.children = [];
	}
}
class BTree {
	constructor(level) {
		this.root = new BTreeNode();
		this.level = level;
	}
  insert(){}
}
const data = Array(9)
	.fill(1)
	.map((item, index) => index);
const btree = new BTree(5);
data.forEach((item) => btree.insert(item));

先界说了 B树节点的数据结构，其中有 keys，用来存储节点的要害词；children 用来储存节点的分支。

然后界说了 BTree 的结构，用来构建 B树。

接下来便是完成 insert 办法了

创立 B树

/**
* 向 B 树中刺进一个新值。
* @param {*} value - 要刺进到 B 树中的新值。
*/
insert(value) {
    // 调用私有办法 _insert，传入根节点和要刺进的值。
    this._insert(null, this.root, value);
}
/**
* 私有办法，用于向 B 树中刺进一个新值。
* @param {BTreeNode} parent - 当时刺进节点的孩子节点的父节点。
* @param {BTreeNode} node - 当时刺进节点。
* @param {*} value - 要刺进到 B 树中的新值。
*/
_insert(parent, node, value) {
    // 假如当时节点的子节点数为 0，将新值添加为新的键。
    if (node.children.length == 0) {
        // 将新值添加为新的键。
        this.addKeys(node, value);
    } else {
        // 遍历当时节点的子节点。
        let flag = -1;
        for (let i = 0; i < node.keys.length; i++) {
            // 假如新值小于或等于当时键，将新值刺进到对应子节点的键中。
            if (value <= node.keys[i]) {
                this._insert(node, node.children[i], value);
                flag = i;
                break;
            }
        }
        // 假如新值大于全部键，将其刺进到子节点数组中的最终一个元素。
        if (flag == -1) {
            this._insert(node, node.children.slice(-1)[0], value);
        }
    }
    // 判别节点数量是否过多
    this.judgeOver();
}
judgeOver(){
  	...
}
/**
* Adds a new key to the current node.
* @param {BTreeNode} node - The current node.
* @param {*} value - The new key to be added.
*/
addKeys(node, value) {
  	...
}

上面的代码比较多，一起来分析分析
首先 insert 办法是提供外界调用的办法，接纳一个节点的值。insert 内部调用 _insert 函数，完成节点的刺进。
_insert 函数完成刺进的进程和排序二叉树的相似，假如小于根节点，就往左节点刺进；假如大于根节点，就往右节点刺进。我这里支撑相同节点的重复刺进，所以刺进的节点等于当时节点，也往左节点刺进。

与排序二叉树不同的是，B树有多个要害词，也有多个分支，所以需要与各个要害词比较，才能知道要往哪个分支持续刺进。代码中设置了 flag 变量，用来监控是否大于全部的要害词，假如 flag==-1，那就将 value 刺进到最终一个分支中。

持续往子节点刺进是通过递归调用_insert 办法完成的，十分方便。等到了叶子节点，也便是node.children.length == 0，就不能再往下了递归了。就在叶子节点的要害词中找个适宜方位刺进。

适宜的方位便是使刺进之后，叶子节点要害词依旧是有序的，即从左往右，顺次增大。刺进的逻辑是 addKeys 完成的，相当于一个刺进排序的算法：

addKeys

/**
* 向当时节点中添加一个新的键。
* @param {BTreeNode} node - 当时节点。
* @param {number} value - 要添加的新键。
*/
addKeys(node, value) {
    // 遍历当时节点的键数组，查找刺进新键的方位。
    for (let i = 0; i < node.keys.length; i++) {
        // 假如新键小于或等于当时键，将新键添加到当时键数组中。
        if (value <= node.keys[i]) {
            // 将新键添加到当时键数组中。
            node.keys.splice(i, 0, value);
            return;
        }
    }
    // 假如新键大于全部键，将新键添加到子节点数组中的最终一个元素。
    node.keys.push(value);
}

在完毕了刺进节点的作业后，就要查看叶子节点是否超支了。上文说到，节点要害词的数量最多是 m-1，即比阶数小一。完成查看的逻辑是 judgeOver 完成的

judgeOver

/**
* 查看当时节点是否有过多键。假如是，则割裂节点。
* @param {BTreeNode} parent - 当时节点的父节点。
* @param {BTreeNode} node - 当时节点。
*/
judgeOver(parent, node) {
    // 假如当时节点的键数超越最大允许的节点数，将节点割裂。
    if (node.keys.length >= this.level) {
        // 创立一个新的节点并将一些键和子节点移动到新节点中。
        this.splitNode(parent, node);
    }
}
/**
* 割裂一个节点，创立一个新的节点并将一些键和子节点移动到新节点中。
* @param {BTreeNode} parent - 当时节点的父节点。
* @param {BTreeNode} node - 当时节点。
* @returns {BTreeNode} - 新节点的父节点。
*/
splitNode(parent, node) {
   ...
}

假如node.keys.length >= this.level 就说明要害词多了，必需要差分节点，将节点的要害一分为二。

怎样拆分呢？

将节点的要害词从中间破开，分成三份，左边 [0～mid-1), mid-1, (mid-1, level] 。mid 便是Math.ceil(level/ 2) - 1，翻译一下：阶数除以 2，向上取整，然后减一。

左边的要害词和右边的要害词各生成一个节点，中间的要害词上升到父节点的方位。除此之外，父节点还多了一个指向右边新节点的分支。

这便是拆分的进程。很简略吧

这个图也是从王道考研数据结构视频课中截取的，咸鱼学长可太厉害了，快去给他打 call 吧 7.4_2_B树的刺进删除

splitNode

splitCode 代码完成：

/**
* 割裂一个节点，创立一个新的节点并将一些键和子节点移动到新节点中。
* @param {BTreeNode} parent - 当时节点的父节点。
* @param {BTreeNode} node - 当时节点。
* @returns {BTreeNode} - 新节点的父节点。
*/
splitNode(parent, node) {
    // 假如父节点为空，则创立一个新的父节点。
    if (parent == null) {
        parent = new BTreeNode();
        this.root = parent;
    }
    // 核算切割键的索引。
    const mid = Math.ceil(node.keys.length / 2) - 1;
    // 将切割键添加到父节点中。
    this.addKeys(parent, node.keys[mid]);
    // 创立一个新的节点并将切割后的键和子节点移动到新节点中。
    const rightKeys = node.keys.slice(mid + 1);
    const rightChildren = node.children.slice(mid + 1);
    const newLeaf = new BTreeNode();
    newLeaf.keys = rightKeys;
    newLeaf.children = rightChildren;
    // 假如父节点没有子节点，将新节点添加为父节点的子节点。
    if (parent.children.length == 0) {
        parent.children.push(node, newLeaf);
    } else {
        // 不然，将新节点添加为父节点的子节点。
        parent.children.push(newLeaf);
    }
    // 从当时节点中移除切割键和子节点。
    node.keys = node.keys.slice(0, mid);
    node.children = node.children.slice(0, mid + 1);
}

代码不难，便是按照方才讲的。将 node 一分为三，一左，一父，一右。

办法开头的判别parent == null，是为了拆分根节点做处理的。假如 node 为根节点，那么 parent 就一定为 null，所以需要创立一个父节点，并将 root 指向 parent。

拆分节点会增加父节点的要害词，所以查看完当时节点后，还需要查看父节点是否 Over。怎样完成呢？其实递归的_insert 已经完成了。当子节点 judgeOver 之后，就会回到父节点的_insert 函数，从而对父节点进行judgeOver。这便是递归的优点

完好代码

代码讲完了，来看看完好代码：

class BTree {
  constructor(level) {
    this.root = new BTreeNode();
    this.level = level;
  }
  /**
* 向 B 树中刺进一个新值。
* @param {*} value - 要刺进到 B 树中的新值。
*/
  insert(value) {
    // 调用私有办法 _insert，传入根节点和要刺进的值。
    this._insert(null, this.root, value);
  }
  /**
* 私有办法，用于向 B 树中刺进一个新值。
* @param {BTreeNode} parent - 当时刺进节点的孩子节点的父节点。
* @param {BTreeNode} node - 当时刺进节点。
* @param {*} value - 要刺进到 B 树中的新值。
*/
  _insert(parent, node, value) {
    // 假如当时节点的子节点数为 0，将新值添加为新的键。
    if (node.children.length == 0) {
      // 将新值添加为新的键。
      this.addKeys(node, value);
    } else {
      // 遍历当时节点的子节点。
      let flag = -1;
      for (let i = 0; i < node.keys.length; i++) {
        // 假如新值小于或等于当时键，将新值刺进到对应子节点的键中。
        if (value <= node.keys[i]) {
          this._insert(node, node.children[i], value);
          flag = i;
          break;
        }
      }
      // 假如新值大于全部键，将其刺进到子节点数组中的最终一个元素。
      if (flag == -1) {
        this._insert(node, node.children.slice(-1)[0], value);
      }
    }
    // 假如当时节点的键数超越最大允许的节点数，将节点割裂。
    this.judgeOver(parent, node);
  }
  /**
* 查看当时节点是否有过多键。假如是，则割裂节点。
* @param {BTreeNode} parent - 当时节点的父节点。
* @param {BTreeNode} node - 当时节点。
*/
  judgeOver(parent, node) {
    // 假如当时节点的键数超越最大允许的节点数，将节点割裂。
    if (node.keys.length >= this.level) {
      // 创立一个新的节点并将一些键和子节点移动到新节点中。
      this.splitNode(parent, node);
    }
  }
  /**
* 割裂一个节点，创立一个新的节点并将一些键和子节点移动到新节点中。
* @param {BTreeNode} parent - 当时节点的父节点。
* @param {BTreeNode} node - 当时节点。
* @returns {BTreeNode} - 新节点的父节点。
*/
  splitNode(parent, node) {
    // 假如父节点为空，则创立一个新的父节点。
    if (parent == null) {
      parent = new BTreeNode();
      this.root = parent;
    }
    // 核算切割键的索引。
    const mid = Math.ceil(node.keys.length / 2) - 1;
    // 将切割键添加到父节点中。
    this.addKeys(parent, node.keys[mid]);
    // 创立一个新的节点并将切割后的键和子节点移动到新节点中。
    const rightKeys = node.keys.slice(mid + 1);
    const rightChildren = node.children.slice(mid + 1);
    const newLeaf = new BTreeNode();
    newLeaf.keys = rightKeys;
    newLeaf.children = rightChildren;
    // 假如父节点没有子节点，将新节点添加为父节点的子节点。
    if (parent.children.length == 0) {
      parent.children.push(node, newLeaf);
    } else {
      // 不然，将新节点添加为父节点的子节点。
      parent.children.push(newLeaf);
    }
    // 从当时节点中移除切割键和子节点。
    node.keys = node.keys.slice(0, mid);
    node.children = node.children.slice(0, mid + 1);
  }
  /**
* 向当时节点中添加一个新的键。
* @param {BTreeNode} node - 当时节点。
* @param {*} value - 要添加的新键。
*/
  addKeys(node, value) {
    // 遍历当时节点的键数组，查找刺进新键的方位。
    for (let i = 0; i < node.keys.length; i++) {
      // 假如新键小于或等于当时键，将新键添加到当时键数组中。
      if (value <= node.keys[i]) {
        // 将新键添加到当时键数组中。
        node.keys.splice(i, 0, value);
        return;
      }
    }
    // 假如新键大于全部键，将新键添加到子节点数组中的最终一个元素。
    node.keys.push(value);
  }
}

测试一下：

const data = Array(9)
	.fill(1)
	.map((item, index) => index);
const btree = new BTree(5);
data.forEach((item) => btree.insert(item));

创立了一个从 0 到 8 的数据，然后将这 9 个数字顺次刺进到 B树中，将 B树打印出来看看：

let res = "";
const printTree = (data, deeps = [1]) => {
	if (!data) return res;
	let space = deeps
		.slice(0, -1)
		.map((item) => {
			return item == 1 ? "|tt" : "tt";
		})
		.join("");
	space += "|__";
	const content = data.keys.join(", ");
	res = res + space + content + "n";
	if (!data) return res;
	data.children.forEach((item, index) => {
		printTree(item, [...deeps, index == data.children.length - 1 ? 0 : 1]);
	});
	return res;
};
printTree(btree.root);
console.log(res);

printTree 是一个将 B 树结构在控制台以树形结构输出的函数，下面是打印成果：

的确满足 B树的性质，但打印成果也不能说明全部，来个更具说服力的依据

这是一个线上的数据结构网站，我顺次刺进了 9 个数字，B树的结构和我控制台打印出来的结构如出一辙。

这是网址，感兴趣的网页能够去看看：B-Tree Visualization

再来看几组：

完美，一摸一样，代码完全正确

总结：

这篇文章分享了一个比较有难度的数据结构–B树。

假如你是一个了解 B 树的性质，正在寻觅代码怎样完成的同学，那这篇文章便是为你预备的；当然假如你仅有一些 B 树的基础，文中的代码你还是能够看得懂的。假如你一点 B 树的基础都没有，主张先看 B 栈王道考研数据结构的视频，对 B 树有个大致的了解，再来看这篇文章，信任你会很有收成

下篇文章，我将会分享 B 树节点删除，这个比 B树创立愈加杂乱。不过我信任，只要你仔细看，还是能够拿下的

你觉得这篇文章怎样样？喜爱就点赞+关注吧

🥳每日一练-B树的创建-JS不难版

什么是 B 树？

预备数据

创立 B树

addKeys

judgeOver

splitNode

完好代码

总结：

相关文章

画一手好的架构图是码农进阶的开始

不改一行业务代码，飞书 iOS 低端机启动优化实践

你还不会写 vite 插件吗？没关系，我教你啊！

【简写Mybatis】03-Mapper xml的注册和使用

作者信息