2-3 树 (搜索、插入和删除)

2-3 树

2-3 树是一种与普通树相同的数据结构，但它有一些不同的特性，例如任何节点都可以拥有单个值或双个值。因此，2-3 树有两种类型的节点：

单值节点

如果一个节点是单值的，那么它有两个子节点。左子节点的值将小于父节点的值，右子节点的值将大于父节点的值。

双值节点

如果一个节点有两个值，那么它将有三个子节点。左子节点的值将小于左父节点的值，中间子节点的值将大于左父节点的值但小于右父节点的值。右子节点的值将大于右父节点的值。由于每个节点都有两个或三个子节点，因此称为 2-3 树。它是一棵高度平衡的树，原因是所有叶节点都位于同一层。

由于它看起来像二叉搜索树，因此在搜索元素方面也具有非常好的时间复杂度。这种数据结构的实际应用在于文件系统和数据库系统中的字符串文件。在最坏的情况下，如果树的高度接近元素数量，二叉搜索树的操作成本可能为 O(n)，但在 2-3 树的情况下，时间复杂度将为 O(log N)。

这棵树有三种操作：

1. 搜索

搜索操作是指我们给出根节点和目标值。如果树中存在该值，则返回 true；否则，返回 false。

我们可以使用递归来搜索树中的任何元素。

情况 1

如果当前节点是单值的，并且目标值小于节点的值，则对左子节点调用递归函数。否则，对右子节点调用递归函数。

情况 2

如果当前节点是双值的，并且目标值小于左值，则对左子节点调用递归函数。如果目标元素大于当前节点的左值且小于当前节点的右值，则对中间子节点调用递归函数。否则，对右子节点调用递归函数。

基本情况

众所周知，递归的基本情况是终止递归调用的最重要条件。如果当前节点为空，则返回 false；或者如果当前节点的值等于目标元素，则返回 true。

2. 插入

如果我们要向树中插入一个元素，那么我们将找到它的正确位置，然后插入它。在插入操作中，我们可以有三种情况：

情况 1

假设要插入元素的节点包含一个值。在这种情况下，我们将简单地插入该元素。

例如

在上面的例子中，我们只是将目标放在了正确的位置。

情况 2

如果要在其中插入目标元素的节点包含双值且其父节点是单值，那么我们将把元素放在该节点上，节点中的中间值将移至其父节点。然后当前节点将被拆分成两个单独的节点。

例如

说明

在上面的例子中，我们有一个目标元素 14，并且要插入它的节点已经有两个值 11 和 12。所以第一步，我们将值插入到正确的位置，现在我们的节点有三个值 11、12 和 14，这是不允许的。所以中间值是 12，它的父节点有一个单值，这意味着我们可以将一个值插入到其父节点。所以我们将 12 插入到父节点，并将当前节点拆分成两个节点，其中一个节点的值是 11，另一个节点的值是 14。

情况 3

如果我们要插入的节点是双值节点，并且其父节点也是双值节点。我们将中间元素移到父节点，并将当前节点拆分。现在它的父节点有三个值，所以它也会将其中间元素移到父节点，并将父节点拆分成两个单独的节点。

3. 删除

为了删除一个值，它被它的中序后继替换。如果一个节点剩余的数据值少于一个，则必须将两个节点合并在一起。删除一个值后，如果一个节点变空，则会与其他节点合并。