经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C# » 查看文章
图解B树及C#实现（3）数据的删除
来源：cnblogs　　作者：黑洞视界　　时间：2023/2/6 9:03:42　　对本文有异议

目录

前言

本文为系列文章

  1. B树的定义及数据的插入
  2. 数据的读取及遍历
  3. 数据的删除

阅读本文前，建议先复习前两篇文章，以便更好的理解本文。

从删除的数据所在的节点可分为两种情况：

  1. 从叶子节点删除数据
  2. 从非叶子节点删除数据

无论从叶子节点还是非叶子节点删除数据时都需要保证B树的特性：非根节点每个节点的 key 数量都在 [t-1, 2t-1] 之间。

借此保证B树的平衡性。

之前介绍的插入数据关注的是这个范围的上限 2t-1，插入时，如果节点的 key 数量大于 2t-1，就需要进行数据的分裂。

而删除数据则关注是下限 t-1，如果节点的 key 数量小于 t-1，就需要进行数据的移动或者合并。

删除数据时，需要考虑的情况比较多，本文会分别讨论这些情况，但一些比较边缘的情况为避免描述过于复杂，不再文中讨论，而是在代码中进行了注释。

因为删除逻辑比较复杂，请结合完整代码进行阅读。
https://github.com/eventhorizon-cli/EventHorizon.BTree/blob/b51881719146a86568669cdc78f8524299bee33d/src/EventHorizon.BTree/BTree.cs#L139

从叶子节点删除数据

如果待删除的数据在叶子节点，且该节点的 Item 数量大于 t-1，那么直接删除该数据即可。

从非叶子节点删除数据

如果待删除的数据在非叶子节点，那么需要先找到该数据的左子节点，然后将左子节点的数据替换到待删除的数据，最后再删除左子节点的数据。

这样能保证被删除数据的节点的 Item 数量不变，保证 B树 有 k 个子节点的非叶子节点拥有 k ? 1 个键的特性不受破坏。

提前扩充只有 t-1 的 Item 的节点：维持 B树 平衡的核心算法

在数据插入的时候，为了避免回溯性的节点分裂，我们提前将已满的子节点进行分裂。

同样的在数据删除，不断往下递归查找时，如果遇到只有 t-1 个 Item 的节点，我们也需要提前将其扩充，以避免回溯性的节点处理。

扩充的节点不一定是最后数据所在的节点，只是向下查找过程中遇到的节点。

节点扩充的分为两类，一个是从兄弟节点借用 Item，一个是合并兄弟节点，被借用的兄弟节点需要满足 Item 数量大于 t-1。具体可分为以下三种情况：

从左兄弟节点借用 Item

待扩充节点的左兄弟节点存在且左兄弟节点的 Item 数量 > t-1 时，从左兄弟节点借用 Item 进行扩充。

为了保证 B树 数据的顺序特性：任意 Item 的左子树中的 Key 均小于该 Item 的 Key，右子树中的 Key 均大于该 Item 的 Key。需要交换左兄弟节点的最右边的 Item 和父节点中对应位置的 Item（位于左兄弟节点右侧）。

以下图为例进行说明：

从右兄弟节点借用 Item

待扩充节点的左兄弟节点不存在或者左兄弟节点的 Item 数量 只有 t-1 时，无法外借。但右兄弟节点存在且右兄弟节点的 Item 数量 > t-1 时，从右兄弟节点借用 Item 进行扩充。

以下图为例进行说明：

从兄弟节点进行扩充可以概括为：借用，交换，插入。

与左兄弟节点或者右兄弟节点合并

如果待扩充节点的左兄弟节点和右兄弟节点都不存在或者都只有 t-1 个 Item 时，无法外借。此时需要与左兄弟节点或者右兄弟节点进行合并。

以下图为例进行说明：

最值的删除

之前章节介绍过 B树 最值的查找：

  1. 最小值：从根节点开始，一直往左子树走，直到叶子节点。
  2. 最大值：从根节点开始，一直往右子树走，直到叶子节点。

最值的删除就是先找到最值的位置并将其删除，在向下寻找的过程中，需要和普通的数据删除一样，对节点进行扩充或者合并。

代码实现

最值删除是删除的特殊情况，我们定义一个枚举用来区分普通数据的删除，最小值的删除以及最大值的删除，这三种方式只在数据查找的时候有所区分，其他的逻辑都是一样的。

  1. internal enum RemoveType
  2. {
  3.     Item,
  4.     Min,
  5.     Max
  6. }
  8. public sealed class BTree<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue?>>
  9. {
  10.     public bool TryRemove([NotNull] TKey key, out TValue? value)
  11.     {
  12.         ArgumentNullException.ThrowIfNull(key);
  14.         return TryRemove(key, RemoveType.Item, out value);
  15.     }
  17.     public bool TryRemoveMax(out TValue? value) => TryRemove(default, RemoveType.Max, out value);
  19.     public bool TryRemoveMin(out TValue? value) => TryRemove(default, RemoveType.Min, out value);
  21.         private bool TryRemove(TKey? key, RemoveType removeType, out TValue? value)
  22.     {
  23.         if (_root == null || _root.IsItemsEmpty)
  24.         {
  25.             value = default;
  26.             return false;
  27.         }
  29.         bool removed = _root.TryRemove(key, removeType, out var item);
  30.         if (_root.IsItemsEmpty && !_root.IsLeaf)
  31.         {
  32.             // 根节点原来的两个子节点进行了合并，根节点唯一的元素被移动到了子节点中，需要将合并后的子节点设置为新的根节点
  33.             _root = _root.GetChild(0);
  34.         }
  36.         if (removed)
  37.         {
  38.             _count--;
  39.             value = item!.Value;
  40.             return true;
  41.         }
  43.         value = default;
  44.         return removed;
  45.     }
  46. }

主要的逻辑定义在 Node 中，不断向下递归

  1. internal class Node<TKey, TValue>
  2. {
  3.         public bool TryRemove(TKey? key, RemoveType removeType, [MaybeNullWhen(false)] out Item<TKey, TValue?> item)
  4.     {
  5.         int index = 0;
  6.         bool found = false;
  7.         if (removeType == RemoveType.Max)
  8.         {
  9.             if (IsLeaf)
  10.             {
  11.                 if (_items.Count == 0)
  12.                 {
  13.                     item = default;
  14.                     return false;
  15.                 }
  17.                 // 如果是叶子节点，直接删除最后一个元素，就是删除最大的 Item
  18.                 item = _items.RemoveLast();
  19.                 return true;
  20.             }
  22.             // 当前节点不是叶子节点，需要找到最大的子节点，继续向下查找并删除
  23.             index = ItemsCount;
  24.         }
  26.         if (removeType == RemoveType.Min)
  27.         {
  28.             if (IsLeaf)
  29.             {
  30.                 if (_items.Count == 0)
  31.                 {
  32.                     item = default;
  33.                     return false;
  34.                 }
  36.                 // 当前节点是叶子节点，直接删除第一个元素，就是删除最小的 Item
  37.                 item = _items.RemoveAt(0);
  38.                 return true;
  39.             }
  41.             // 当前节点不是叶子节点，需要找到最小的子节点，继续向下查找并删除
  42.             index = 0;
  43.         }
  45.         if (removeType == RemoveType.Item)
  46.         {
  47.             // 如果没有找到，index 表示的是 key 可能在的子树的索引
  48.             found = _items.TryFindKey(key!, out index);
  50.             if (IsLeaf)
  51.             {
  52.                 // 如果是叶子节点，能找到就删除，找不到就返回 false，表示删除失败
  53.                 if (found)
  54.                 {
  55.                     item = _items.RemoveAt(index);
  56.                     return true;
  57.                 }
  59.                 item = default;
  60.                 return false;
  61.             }
  62.         }
  64.         // 如果当前节点的左子节点的 Item 个数小于最小 Item 个数，就需要进行合并或者借元素
  65.         // 这个处理对应两种情况：
  66.         // 1. 要删除的 Item 不在当前节点的子节点中，为避免删除后导致数据所在节点的 Item 个数小于最小 Item 个数，需要先进行合并或者借元素。
  67.         // 2. 要删除的 Item 就在当前节点中，为避免删除后导致当前节点的 Item 个数小于最小 Item 个数，需要先从左子节点中借一个 Item 过来，保证当前节点的 Item 数量不变。
  68.         // 为此先要保证左子节点被借用后的 Item 个数不小于最小 Item 个数。
  69.         if (_children[index].ItemsCount <= _minItems)
  70.         {
  71.             return GrowChildrenAndTryRemove(index, key!, removeType, out item);
  72.         }
  74.         var child = _children[index];
  76.         if (found)
  77.         {
  78.             // 如果在当前节点找到了，就删除当前节点的 Item，然后将 左子节点 中的最大的 Item 移动到当前节点中
  79.             // 以维持当前节点的 Item 个数不变，保证 B树 有 k 个子节点的非叶子节点拥有 k ? 1 个键的特性。
  80.             item = _items[index];
  81.             child.TryRemove(default!, RemoveType.Max, out var stolenItem);
  82.             _items[index] = stolenItem;
  83.             return true;
  84.         }
  86.         return child.TryRemove(key!, removeType, out item);
  87.     }
  89.     private bool GrowChildrenAndTryRemove(
  90.         int childIndex,
  91.         TKey key,
  92.         RemoveType removeType,
  93.         [MaybeNullWhen(false)] out Item<TKey, TValue?> item)
  94.     {
  95.         if (childIndex > 0 && _children[childIndex - 1].ItemsCount > _minItems)
  96.         {
  97.             // 如果左边的子节点存在且左边的子节点的item数量大于最小值，则从左边的子节点借一个item
  98.             var child = _children[childIndex];
  99.             var leftChild = _children[childIndex - 1];
  100.             var stolenItem = leftChild._items.RemoveLast();
  101.             child._items.InsertAt(0, _items[childIndex - 1]);
  102.             _items[childIndex - 1] = stolenItem;
  103.             if (!leftChild.IsLeaf)
  104.             {
  105.                 // 非叶子节点的子节点需要保证数量比item多1，item数量变了，子节点数量也要变
  106.                 // 所以需要从左边的子节点中移除最后一个子节点，然后插入到当前子节点的第一个位置
  107.                 child._children.InsertAt(0, leftChild._children.RemoveLast());
  108.             }
  109.         }
  110.         else if (childIndex < ChildrenCount - 1 && _children[childIndex + 1].ItemsCount > _minItems)
  111.         {
  112.             // 如果右边的子节点存在且右边的子节点的item数量大于最小值，则从右边的子节点借一个item
  113.             var child = _children[childIndex];
  114.             var rightChild = _children[childIndex + 1];
  115.             var stolenItem = rightChild._items.RemoveAt(0);
  116.             child._items.Add(_items[childIndex]);
  117.             _items[childIndex] = stolenItem;
  118.             if (!rightChild.IsLeaf)
  119.             {
  120.                 // 非叶子节点的子节点需要保证数量比item多1，item数量变了，子节点数量也要变
  121.                 // 所以需要从右边的子节点中移除第一个子节点，然后插入到当前子节点的最后一个位置
  122.                 child.AddChild(rightChild._children.RemoveAt(0));
  123.             }
  124.         }
  125.         else
  126.         {
  127.             // 如果当前节点左右两边的子节点的item数量都不大于最小值（例如正好等于最小值 t-1 ），则合并当前节点和右边的子节点或者左边的子节点
  128.             // 优先和右边的子节点合并，如果右边的子节点不存在，则和左边的子节点合并
  129.             if (childIndex >= ItemsCount)
  130.             {
  131.                 // ItemCount 代表最的子节点的索引，如果 childIndex 大于等于 ItemCount，说明右边的子节点不存在，需要和左边的子节点合并
  132.                 childIndex--;
  133.             }
  135.             var child = _children[childIndex];
  136.             var mergeItem = _items.RemoveAt(childIndex);
  137.             var mergeChild = _children.RemoveAt(childIndex + 1);
  138.             child._items.Add(mergeItem);
  139.             child._items.AddRange(mergeChild._items);
  140.             child._children.AddRange(mergeChild._children);
  141.         }
  143.         return TryRemove(key, removeType, out item);
  144.     }
  145. }

Benchmarks：与 优先队列 PriorityQueue 的比较

我们实现的 BTree 支持自定义排序规则，也实现最值的删除，意味着可以充当优先队列使用。

我们使用 PriorityQueue 与 BTree 进行性能对比来看看 B树 能否充当优先队列使用。

入队性能

  1. public class BTree_PriorityQueue_EnequeueBenchmarks
  2. {
  3.     [Params(1000, 1_0000, 10_0000)] public int DataSize;
  5.     [Params(2, 4, 8, 16)] public int Degree;
  7.     private HashSet<int> _data;
  9.     [IterationSetup]
  10.     public void Setup()
  11.     {
  12.         var random = new Random();
  13.         _data = new HashSet<int>();
  14.         while (_data.Count < DataSize)
  15.         {
  16.             var value = random.Next();
  17.             _data.Add(value);
  18.         }
  19.     }
  21.     [Benchmark]
  22.     public void BTree_Add()
  23.     {
  24.         var btree = new BTree<int, int>(Degree);
  26.         foreach (var value in _data)
  27.         {
  28.             btree.Add(value, value);
  29.         }
  30.     }
  32.     [Benchmark]
  33.     public void PriorityQueue_Enqueue()
  34.     {
  35.         var priorityQueue = new PriorityQueue<int, int>(DataSize);
  37.         foreach (var value in _data)
  38.         {
  39.             priorityQueue.Enqueue(value, value);
  40.         }
  41.     }
  42. }

出队性能

  1. public class BTree_PriorityQueue_DequeueBenchmarks
  2. {
  3.     [Params(1000, 1_0000, 10_0000)] public int DataSize;
  5.     [Params(2, 4, 8, 16)] public int Degree;
  7.     private BTree<int, int> _btree;
  9.     private PriorityQueue<int, int> _priorityQueue;
  11.     [IterationSetup]
  12.     public void Setup()
  13.     {
  14.         var random = new Random();
  15.         _btree = new BTree<int, int>(Degree);
  16.         _priorityQueue = new PriorityQueue<int, int>(DataSize);
  18.         while (_btree.Count < DataSize)
  19.         {
  20.             var value = random.Next();
  21.             _btree.Add(value, value);
  22.             _priorityQueue.Enqueue(value, value);
  23.         }
  24.     }
  26.     [Benchmark]
  27.     public void BTree_Remove()
  28.     {
  29.         while (_btree.Count > 0)
  30.         {
  31.             _btree.RemoveMin();
  32.         }
  33.     }
  35.     [Benchmark]
  36.     public void PriorityQueue_Dequeue()
  37.     {
  38.         while (_priorityQueue.Count > 0)
  39.         {
  40.             _priorityQueue.Dequeue();
  41.         }
  42.     }
  43. }

可以看到，B树 虽然在入队性能上比 PriorityQueue 差。但在数据量和 degree 较大时，出队性能比 PriorityQueue 好，是有能力充当优先队列使用的。

总结

B树 在 degree 较大时，树的高度较低，删除的效率较高，可充当优先队列使用。

B树 的插入，删除，查找都是基于递归的，递归的深度为树的高度。

B树 对数据的查找基于二分查找，时间复杂度为 O(log n)，B树 的插入和删除基于 B树的查找算法，都要找到数据所在的节点，然后在该节点进行插入和删除。因此，B树 的插入和删除的时间复杂度也为 O(log n)。

B树 是对二叉树的一种优化，使得树的高度更低，但是在插入，删除的过程中，需要进行大量的节点分裂，合并，借用，交换等操作，使得算法的复杂度更高。

参考资料

Google 用 Go 实现的内存版 B树 https://github.com/google/btree

B树 维基百科 https://zh.m.wikipedia.org/zh-hans/B树

原文链接：https://www.cnblogs.com/eventhorizon/p/17092336.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C#热门文章

  • NPOI的Excel的读取和写入
  • 事务在c#中的使用
  • 基于欧姆龙PLC#FinsTcp协议上位机通讯(二)-C#通讯模块开发
  • C# 当前 .NET SDK 不支持将 .NET Core 2.1 设置为目标。请将 .NET Core 2.0 或更低版本设置为目标，或使用支持 .NET Core 2.1 的 .NET SDK 版本。
  • C#读写Excel的几种方法
  • C#NPOI操作Excel，实现Excel数据导入导出（支持多个sheet）
  • c#中token的使用方法实例
  • OrderBy和OrderByDescending排序
  • C#中的modbus&nbsp;Tcp协议的数据抓取和使用解析
  • C#Aspose操作Word &amp; Excel简版（后会研究补充更多功能）

    • C#推荐文章

  • .NET 9 优化，抢先体验 C# 13 新特性
  • 使用C#爬取快手作者主页，并下载视频/图集(附源码及软件下载链接)
  • 聊一聊 C# 中让人惶恐的 Bitmap
  • C#/.NET/.NET Core技术前沿周刊 | 第 2 期（2024年8.19-8.25）
  • Elsa V3学习之Flowchart详解（上）
  • C#模拟键盘输入、键状态和监听键盘消息
  • 可以调用Null的实例方法吗？
  • SemanticKernel/C#：实现接口，接入本地嵌入模型
  • C#.Net筑基-解密委托与事件
  • C#/.NET/.NET Core优秀项目和框架2024年7月简报

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号