0%

2-3 树

1. 介绍

2-3 树是一种平衡二叉树,具有自动平衡能力

2-3 树是一种拥有 2 种不同节点的树,称为 2-节点 和 3-节点

  1. 2-节点,拥有一个键值两个链接(左子树和右子树),实际上就是普通的二叉搜索树节点
  2. 3-节点,拥有两个键值三个链接,左子结点比最小的键值小,右子结点比最大的键值大,中子节点介于两者之间

2-3 Tree

2. 搜索

2-3 树的搜索和 BST 一样,根据比较结果来进入子树进行搜索。

3. 插入

2-3 树的插入稍微有些复杂,我们分情况来讨论。

3.1 在 2-节点 中插入

这是最简单的一种情况,只需将 2-节点 变为 3-节点即可。

Insert 2-node

3.2 在只有 3-节点的树中插入

在这种情况下,我们可以构建一个暂时的 4-节点,然后将其分裂三个 2-节点

这个操作会增加树的高度

Insert only 3-node

3.3 在父节点为 2-节点 的 23-节点 插入

这种情况就更加复杂了,此时,我们 将 3-节点 变为临时的 4-节点,然后将其分裂。

分裂 4-节点 时,将中间节点向上传递到父节点中,将剩下的两个节点作为 2-节点

Insert 3-node with the 2-node father

3.4 在父节点为 3-节点 的 3-节点 插入

这种情况和上一个稍微有点像,我们只需要将 3-节点 替换为临时的 4-节点,然后将其分裂。此时父节点成为 4-节点,所以我们递归地进行分裂操作,直到到达根节点位置。

如果根节点仍然是 4-节点,那么我们就将根节点分裂,增加树的高度。

Insert into 3-node with 3-node father and reach root

4. 性能

2-3 树能保证 2-节点 的完美平衡,在 BST 中,操作时间复杂度和树的高度成对数关系,所以:

2-3 树能保证任何的相关操作均在对数级别;

在最坏情况下,当所有的节点都是 2-节点 时,2-3 树的性能是 log2Nlog_2N 级别;

在最好情况下,当所有的节点都是 3-节点时,2-3 树的性能是 log3Nlog_3N 级别

在一个 NN 个节点的 2-3 树,搜索和插入只需要访问不超过 logNlogN 个节点。

5. 结论

2-3 树能保证树在插入时的完美 2-节点 平衡,不会出现 BST 的最坏情况。

然而,2-3 树十分难以实现,在实际工程中,我们需要对代码尽量小的改动,从而达到性能优化的结果。

  • 本文作者: Wafer Li
  • 本文链接: https://wafer.li/Algorithm/2-3 树/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!