从B树中删除

提示

删除操作流程：删除 B-树中的元素涉及查找目标节点、删除键，并在必要时对树进行平衡，以保证其满足 B-树的特性。
处理节点下溢：当节点键数少于最小要求时，发生下溢。处理下溢可以通过借用相邻节点的键或合并节点来实现，确保节点键数符合要求。
特殊情况处理：删除操作中，如果目标键在内部节点，用中序前驱或后继替换，然后递归删除替换的键。如果导致父节点键数不足，需递归处理上层节点，可能导致树高度减小。

在 B-树上删除一个元素包含三个主要步骤：查找要删除的键所在的节点、删除键并在必要时对树进行平衡。

在删除树的过程中，可能会出现一种称为下溢的情况。当一个节点包含的键少于它应该持有的最小数量时，就会发生下溢。

在学习删除操作之前，需要理解的术语有：

中序前驱 节点左孩子上的最大键称为其中序前驱。
中序后继 节点右孩子上的最小键称为其中序后继。

删除操作

在进行以下步骤之前，必须了解有关度为 m 的 B 树的以下事实。

一个节点最多可以有 m 个孩子。（例如：3）
一个节点最多可以包含 m - 1 个键。（例如：2）
一个节点应该至少有 ⌈m/2⌉ 个孩子。（例如：2）
一个节点（除根节点外）应该至少包含 ⌈m/2⌉ - 1 个键。（例如：1）

在 B 树中删除操作有三个主要情况。

情况一

要删除的键位于叶子节点。这有两种情况：

删除键不违反节点应持有的最小键数的属性。

在下面的树中，删除 32 不违反上述属性。
删除键违反了节点应持有的最小键数的属性。在这种情况下，我们从它的直接相邻兄弟节点借一个键，顺序是从左到右。

首先访问直接左兄弟。如果左兄弟节点的键数超过最小值，则从该节点借一个键。

否则，尝试从直接右兄弟节点借键。

在下面的树中，删除 31 导致了上述情况。让我们从左兄弟节点借一个键。

如果两个直接相邻的兄弟节点都已经有了最小数量的键，那么将节点与左兄弟节点或右兄弟节点合并。这种合并是通过父节点完成的。

删除 30 导致了上述情况。

情况二

如果要删除的键位于内部节点，则会出现以下情况。

被删除的内部节点由中序前驱替换，如果左孩子的键数超过最小值。
被删除的内部节点由中序后继替换，如果右孩子的键数超过最小值。
如果任一孩子刚好有最小数量的键，则合并左右孩子。

如果合并后父节点的键数少于最小值，则像情况一中所述寻找兄弟节点。

情况三

在这种情况下，树的高度会缩小。如果目标键位于内部节点，并且键的删除导致节点的键数减少（即少于所需的最小数量），则寻找中序前驱和中序后继。如果两个孩子都只有最小数量的键，则无法进行借键操作。这将导致

情况二（3），即合并孩子。

再次寻找兄弟节点以借一个键。但是，如果兄弟节点也只有最小数量的键，则将节点与兄弟及父节点合并。按照递增顺序排列孩子。

删除内部节点

Python、Java 和 C/C++ 示例

Python Java C C++

# 在 Python 中删除 B-树上的一个键


# B树节点
class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []


class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t

    # 插入一个键
    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.child.insert(0, root)
            self.split_child(temp, 0)
            self.insert_non_full(temp, k)
        else:
            self.insert_non_full(root, k)

    # 插入非满节点
    def insert_non_full(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append((None, None))
            while i >= 0 and k[0] < x.keys[i][0]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k[0] < x.keys[i][0]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2 * self.t) - 1:
                self.split_child(x, i)
                if k[0] > x.keys[i][0]:
                    i += 1
            self.insert_non_full(x.child[i], k)

    # 分裂孩子节点
    def split_child(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t: (2 * t) - 1]
        y.keys = y.keys[0: t - 1]
        if not y.leaf:
            z.child = y.child[t: 2 * t]
            y.child = y.child[0: t - 1]

    # 删除一个节点
    def delete(self, x, k):
        t = self.t
        i = 0
        while i < len(x.keys) and k[0] > x.keys[i][0]:
            i += 1
        if x.leaf:
            if i < len(x.keys) and x.keys[i][0] == k[0]:
                x.keys.pop(i)
                return
            return

        if i < len(x.keys) and x.keys[i][0] == k[0]:
            return self.delete_internal_node(x, k, i)
        elif len(x.child[i].keys) >= t:
            self.delete(x.child[i], k)
        else:
            if i != 0 and i + 2 < len(x.child):
                if len(x.child[i - 1].keys) >= t:
                    self.delete_sibling(x, i, i - 1)
                elif len(x.child[i + 1].keys) >= t:
                    self.delete_sibling(x, i, i + 1)
                else:
                    self.delete_merge(x, i, i + 1)
            elif i == 0:
                if len(x.child[i + 1].keys) >= t:
                    self.delete_sibling(x, i, i + 1)
                else:
                    self.delete_merge(x, i, i + 1)
            elif i + 1 == len(x.child):
                if len(x.child[i - 1].keys) >= t:
                    self.delete_sibling(x, i, i - 1)
                else:
                    self.delete_merge(x, i, i - 1)
            self.delete(x.child[i], k)

    # Delete internal node
    def delete_internal_node(self, x, k, i):
        t = self.t
        if x.leaf:
            if x.keys[i][0] == k[0]:
                x.keys.pop(i)
                return
            return

        if len(x.child[i].keys) >= t:
            x.keys[i] = self.delete_predecessor(x.child[i])
            return
        elif len(x.child[i + 1].keys) >= t:
            x.keys[i] = self.delete_successor(x.child[i + 1])
            return
        else:
            self.delete_merge(x, i, i + 1)
            self.delete_internal_node(x.child[i], k, self.t - 1)

    # Delete the predecessor
    def delete_predecessor(self, x):
        if x.leaf:
            return x.pop()
        n = len(x.keys) - 1
        if len(x.child[n].keys) >= self.t:
            self.delete_sibling(x, n + 1, n)
        else:
            self.delete_merge(x, n, n + 1)
        self.delete_predecessor(x.child[n])

    # Delete the successor
    def delete_successor(self, x):
        if x.leaf:
            return x.keys.pop(0)
        if len(x.child[1].keys) >= self.t:
            self.delete_sibling(x, 0, 1)
        else:
            self.delete_merge(x, 0, 1)
        self.delete_successor(x.child[0])

    # Delete resolution
    def delete_merge(self, x, i, j):
        cnode = x.child[i]

        if j > i:
            rsnode = x.child[j]
            cnode.keys.append(x.keys[i])
            for k in range(len(rsnode.keys)):
                cnode.keys.append(rsnode.keys[k])
                if len(rsnode.child) > 0:
                    cnode.child.append(rsnode.child[k])
            if len(rsnode.child) > 0:
                cnode.child.append(rsnode.child.pop())
            new = cnode
            x.keys.pop(i)
            x.child.pop(j)
        else:
            lsnode = x.child[j]
            lsnode.keys.append(x.keys[j])
            for i in range(len(cnode.keys)):
                lsnode.keys.append(cnode.keys[i])
                if len(lsnode.child) > 0:
                    lsnode.child.append(cnode.child[i])
            if len(lsnode.child) > 0:
                lsnode.child.append(cnode.child.pop())
            new = lsnode
            x.keys.pop(j)
            x.child.pop(i)

        if x == self.root and len(x.keys) == 0:
            self.root = new

    # Delete the sibling
    def delete_sibling(self, x, i, j):
        cnode = x.child[i]
        if i < j:
            rsnode = x.child[j]
            cnode.keys.append(x.keys[i])
            x.keys[i] = rsnode.keys[0]
            if len(rsnode.child) > 0:
                cnode.child.append(rsnode.child[0])
                rsnode.child.pop(0)
            rsnode.keys.pop(0)
        else:
            lsnode = x.child[j]
            cnode.keys.insert(0, x.keys[i - 1])
            x.keys[i - 1] = lsnode.keys.pop()
            if len(lsnode.child) > 0:
                cnode.child.insert(0, lsnode.child.pop())

    # Print the tree
    def print_tree(self, x, l=0):
        print("Level ", l, " ", len(x.keys), end=":")
        for i in x.keys:
            print(i, end=" ")
        print()
        l += 1
        if len(x.child) > 0:
            for i in x.child:
                self.print_tree(i, l)



B = BTree(3)

for i in range(10):
    B.insert((i, 2 * i))

B.print_tree(B.root)

B.delete(B.root, (8,))
print("\n")
B.print_tree(B.root)

// 在 Java 中向 B 树插入键

import java.util.Stack;

public class BTree {

  private int T;

  public class Node {
    int n;
    int key[] = new int[2 * T - 1];
    Node child[] = new Node[2 * T];
    boolean leaf = true;

    public int Find(int k) {
      for (int i = 0; i < this.n; i++) {
        if (this.key[i] == k) {
          return i;
        }
      }
      return -1;
    };
  }

  public BTree(int t) {
    T = t;
    root = new Node();
    root.n = 0;
    root.leaf = true;
  }

  private Node root;

  // 搜索键
  private Node Search(Node x, int key) {
    int i = 0;
    if (x == null)
      return x;
    for (i = 0; i < x.n; i++) {
      if (key < x.key[i]) {
        break;
      }
      if (key == x.key[i]) {
        return x;
      }
    }
    if (x.leaf) {
      return null;
    } else {
      return Search(x.child[i], key);
    }
  }

  // 分裂函数
  private void Split(Node x, int pos, Node y) {
    Node z = new Node();
    z.leaf = y.leaf;
    z.n = T - 1;
    for (int j = 0; j < T - 1; j++) {
      z.key[j] = y.key[j + T];
    }
    if (!y.leaf) {
      for (int j = 0; j < T; j++) {
        z.child[j] = y.child[j + T];
      }
    }
    y.n = T - 1;
    for (int j = x.n; j >= pos + 1; j--) {
      x.child[j + 1] = x.child[j];
    }
    x.child[pos + 1] = z;

    for (int j = x.n - 1; j >= pos; j--) {
      x.key[j + 1] = x.key[j];
    }
    x.key[pos] = y.key[T - 1];
    x.n = x.n + 1;
  }

  // 插入键
  public void Insert(final int key) {
    Node r = root;
    if (r.n == 2 * T - 1) {
      Node s = new Node();
      root = s;
      s.leaf = false;
      s.n = 0;
      s.child[0] = r;
      Split(s, 0, r);
      _Insert(s, key);
    } else {
      _Insert(r, key);
    }
  }

  // 插入节点
  final private void _Insert(Node x, int k) {

    if (x.leaf) {
      int i = 0;
      for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
        x.key[i + 1] = x.key[i];
      }
      x.key[i + 1] = k;
      x.n = x.n + 1;
    } else {
      int i = 0;
      for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
      }
      ;
      i++;
      Node tmp = x.child[i];
      if (tmp.n == 2 * T - 1) {
        Split(x, i, tmp);
        if (k > x.key[i]) {
          i++;
        }
      }
      _Insert(x.child[i], k);
    }

  }

  public void Show() {
    Show(root);
  }

  private void Remove(Node x, int key) {
    int pos = x.Find(key);
    if (pos != -1) {
      if (x.leaf) {
        int i = 0;
        for (i = 0; i < x.n && x.key[i] != key; i++) {
        }
        ;
        for (; i < x.n; i++) {
          if (i != 2 * T - 2) {
            x.key[i] = x.key[i + 1];
          }
        }
        x.n--;
        return;
      }
      if (!x.leaf) {

        Node pred = x.child[pos];
        int predKey = 0;
        if (pred.n >= T) {
          for (;;) {
            if (pred.leaf) {
              System.out.println(pred.n);
              predKey = pred.key[pred.n - 1];
              break;
            } else {
              pred = pred.child[pred.n];
            }
          }
          Remove(pred, predKey);
          x.key[pos] = predKey;
          return;
        }

        Node nextNode = x.child[pos + 1];
        if (nextNode.n >= T) {
          int nextKey = nextNode.key[0];
          if (!nextNode.leaf) {
            nextNode = nextNode.child[0];
            for (;;) {
              if (nextNode.leaf) {
                nextKey = nextNode.key[nextNode.n - 1];
                break;
              } else {
                nextNode = nextNode.child[nextNode.n];
              }
            }
          }
          Remove(nextNode, nextKey);
          x.key[pos] = nextKey;
          return;
        }

        int temp = pred.n + 1;
        pred.key[pred.n++] = x.key[pos];
        for (int i = 0, j = pred.n; i < nextNode.n; i++) {
          pred.key[j++] = nextNode.key[i];
          pred.n++;
        }
        for (int i = 0; i < nextNode.n + 1; i++) {
          pred.child[temp++] = nextNode.child[i];
        }

        x.child[pos] = pred;
        for (int i = pos; i < x.n; i++) {
          if (i != 2 * T - 2) {
            x.key[i] = x.key[i + 1];
          }
        }
        for (int i = pos + 1; i < x.n + 1; i++) {
          if (i != 2 * T - 1) {
            x.child[i] = x.child[i + 1];
          }
        }
        x.n--;
        if (x.n == 0) {
          if (x == root) {
            root = x.child[0];
          }
          x = x.child[0];
        }
        Remove(pred, key);
        return;
      }
    } else {
      for (pos = 0; pos < x.n; pos++) {
        if (x.key[pos] > key) {
          break;
        }
      }
      Node tmp = x.child[pos];
      if (tmp.n >= T) {
        Remove(tmp, key);
        return;
      }
      if (true) {
        Node nb = null;
        int devider = -1;

        if (pos != x.n && x.child[pos + 1].n >= T) {
          devider = x.key[pos];
          nb = x.child[pos + 1];
          x.key[pos] = nb.key[0];
          tmp.key[tmp.n++] = devider;
          tmp.child[tmp.n] = nb.child[0];
          for (int i = 1; i < nb.n; i++) {
            nb.key[i - 1] = nb.key[i];
          }
          for (int i = 1; i <= nb.n; i++) {
            nb.child[i - 1] = nb.child[i];
          }
          nb.n--;
          Remove(tmp, key);
          return;
        } else if (pos != 0 && x.child[pos - 1].n >= T) {

          devider = x.key[pos - 1];
          nb = x.child[pos - 1];
          x.key[pos - 1] = nb.key[nb.n - 1];
          Node child = nb.child[nb.n];
          nb.n--;

          for (int i = tmp.n; i > 0; i--) {
            tmp.key[i] = tmp.key[i - 1];
          }
          tmp.key[0] = devider;
          for (int i = tmp.n + 1; i > 0; i--) {
            tmp.child[i] = tmp.child[i - 1];
          }
          tmp.child[0] = child;
          tmp.n++;
          Remove(tmp, key);
          return;
        } else {
          Node lt = null;
          Node rt = null;
          boolean last = false;
          if (pos != x.n) {
            devider = x.key[pos];
            lt = x.child[pos];
            rt = x.child[pos + 1];
          } else {
            devider = x.key[pos - 1];
            rt = x.child[pos];
            lt = x.child[pos - 1];
            last = true;
            pos--;
          }
          for (int i = pos; i < x.n - 1; i++) {
            x.key[i] = x.key[i + 1];
          }
          for (int i = pos + 1; i < x.n; i++) {
            x.child[i] = x.child[i + 1];
          }
          x.n--;
          lt.key[lt.n++] = devider;

          for (int i = 0, j = lt.n; i < rt.n + 1; i++, j++) {
            if (i < rt.n) {
              lt.key[j] = rt.key[i];
            }
            lt.child[j] = rt.child[i];
          }
          lt.n += rt.n;
          if (x.n == 0) {
            if (x == root) {
              root = x.child[0];
            }
            x = x.child[0];
          }
          Remove(lt, key);
          return;
        }
      }
    }
  }

  public void Remove(int key) {
    Node x = Search(root, key);
    if (x == null) {
      return;
    }
    Remove(root, key);
  }

  public void Task(int a, int b) {
    Stack<Integer> st = new Stack<>();
    FindKeys(a, b, root, st);
    while (st.isEmpty() == false) {
      this.Remove(root, st.pop());
    }
  }

  private void FindKeys(int a, int b, Node x, Stack<Integer> st) {
    int i = 0;
    for (i = 0; i < x.n && x.key[i] < b; i++) {
      if (x.key[i] > a) {
        st.push(x.key[i]);
      }
    }
    if (!x.leaf) {
      for (int j = 0; j < i + 1; j++) {
        FindKeys(a, b, x.child[j], st);
      }
    }
  }

  public boolean Contain(int k) {
    if (this.Search(root, k) != null) {
      return true;
    } else {
      return false;
    }
  }

  // Show the node
  private void Show(Node x) {
    assert (x == null);
    for (int i = 0; i < x.n; i++) {
      System.out.print(x.key[i] + " ");
    }
    if (!x.leaf) {
      for (int i = 0; i < x.n + 1; i++) {
        Show(x.child[i]);
      }
    }
  }

  public static void main(String[] args) {
    BTree b = new BTree(3);
    b.Insert(8);
    b.Insert(9);
    b.Insert(10);
    b.Insert(11);
    b.Insert(15);
    b.Insert(20);
    b.Insert(17);

    b.Show();

    b.Remove(10);
    System.out.println();
    b.Show();
  }
}

// Deleting a key from a B-tree in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 3
#define MIN 2

struct BTreeNode {
  int item[MAX + 1], count;
  struct BTreeNode *linker[MAX + 1];
};

struct BTreeNode *root;

// 创建节点
struct BTreeNode *createNode(int item, struct BTreeNode *child) {
  struct BTreeNode *newNode;
  newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
  newNode->item[1] = item;
  newNode->count = 1;
  newNode->linker[0] = root;
  newNode->linker[1] = child;
  return newNode;
}

// 向节点添加值
void addValToNode(int item, int pos, struct BTreeNode *node,
          struct BTreeNode *child) {
  int j = node->count;
  while (j > pos) {
    node->item[j + 1] = node->item[j];
    node->linker[j + 1] = node->linker[j];
    j--;
  }
  node->item[j + 1] = item;
  node->linker[j + 1] = child;
  node->count++;
}

// 分裂节点
void splitNode(int item, int *pval, int pos, struct BTreeNode *node,
         struct BTreeNode *child, struct BTreeNode **newNode) {
  int median, j;

  if (pos > MIN)
    median = MIN + 1;
  else
    median = MIN;

  *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
  j = median + 1;
  while (j <= MAX) {
    (*newNode)->item[j - median] = node->item[j];
    (*newNode)->linker[j - median] = node->linker[j];
    j++;
  }
  node->count = median;
  (*newNode)->count = MAX - median;

  if (pos <= MIN) {
    addValToNode(item, pos, node, child);
  } else {
    addValToNode(item, pos - median, *newNode, child);
  }
  *pval = node->item[node->count];
  (*newNode)->linker[0] = node->linker[node->count];
  node->count--;
}

// 在节点中设置值
int setValueInNode(int item, int *pval,
           struct BTreeNode *node, struct BTreeNode **child) {
  int pos;
  if (!node) {
    *pval = item;
    *child = NULL;
    return 1;
  }

  if (item < node->item[1]) {
    pos = 0;
  } else {
    for (pos = node->count;
       (item < node->item[pos] && pos > 1); pos--)
      ;
    if (item == node->item[pos]) {
      printf("Duplicates not allowed\n");
      return 0;
    }
  }
  if (setValueInNode(item, pval, node->linker[pos], child)) {
    if (node->count < MAX) {
      addValToNode(*pval, pos, node, *child);
    } else {
      splitNode(*pval, pval, pos, node, *child, child);
      return 1;
    }
  }
  return 0;
}

// 插入操作
void insertion(int item) {
  int flag, i;
  struct BTreeNode *child;

  flag = setValueInNode(item, &i, root, &child);
  if (flag)
    root = createNode(i, child);
}

// 复制后继
void copySuccessor(struct BTreeNode *myNode, int pos) {
  struct BTreeNode *dummy;
  dummy = myNode->linker[pos];

  for (; dummy->linker[0] != NULL;)
    dummy = dummy->linker[0];
  myNode->item[pos] = dummy->item[1];
}

// 移除值
void removeVal(struct BTreeNode *myNode, int pos) {
  int i = pos + 1;
  while (i <= myNode->count) {
    myNode->item[i - 1] = myNode->item[i];
    myNode->linker[i - 1] = myNode->linker[i];
    i++;
  }
  myNode->count--;
}

// 执行右移
void rightShift(struct BTreeNode *myNode, int pos) {
  struct BTreeNode *x = myNode->linker[pos];
  int j = x->count;

  while (j > 0) {
    x->item[j + 1] = x->item[j];
    x->linker[j + 1] = x->linker[j];
  }
  x->item[1] = myNode->item[pos];
  x->linker[1] = x->linker[0];
  x->count++;

  x = myNode->linker[pos - 1];
  myNode->item[pos] = x->item[x->count];
  myNode->linker[pos] = x->linker[x->count];
  x->count--;
  return;
}

// 执行左移
void leftShift(struct BTreeNode *myNode, int pos) {
  int j = 1;
  struct BTreeNode *x = myNode->linker[pos - 1];

  x->count++;
  x->item[x->count] = myNode->item[pos];
  x->linker[x->count] = myNode->linker[pos]->linker[0];

  x = myNode->linker[pos];
  myNode->item[pos] = x->item[1];
  x->linker[0] = x->linker[1];
  x->count--;

  while (j <= x->count) {
    x->item[j] = x->item[j + 1];
    x->linker[j] = x->linker[j + 1];
    j++;
  }
  return;
}

// 合并节点
void mergeNodes(struct BTreeNode *myNode, int pos) {
  int j = 1;
  struct BTreeNode *x1 = myNode->linker[pos], *x2 = myNode->linker[pos - 1];

  x2->count++;
  x2->item[x2->count] = myNode->item[pos];
  x2->linker[x2->count] = myNode->linker[0];

  while (j <= x1->count) {
    x2->count++;
    x2->item[x2->count] = x1->item[j];
    x2->linker[x2->count] = x1->linker[j];
    j++;
  }

  j = pos;
  while (j < myNode->count) {
    myNode->item[j] = myNode->item[j + 1];
    myNode->linker[j] = myNode->linker[j + 1];
    j++;
  }
  myNode->count--;
  free(x1);
}

// 调整节点
void adjustNode(struct BTreeNode *myNode, int pos) {
  if (!pos) {
    if (myNode->linker[1]->count > MIN) {
      leftShift(myNode, 1);
    } else {
      mergeNodes(myNode, 1);
    }
  } else {
    if (myNode->count != pos) {
      if (myNode->linker[pos - 1]->count > MIN) {
        rightShift(myNode, pos);
      } else {
        if (myNode->linker[pos + 1]->count > MIN) {
          leftShift(myNode, pos + 1);
        } else {
          mergeNodes(myNode, pos);
        }
      }
    } else {
      if (myNode->linker[pos - 1]->count > MIN)
        rightShift(myNode, pos);
      else
        mergeNodes(myNode, pos);
    }
  }
}

// 从节点中删除值
int delValFromNode(int item, struct BTreeNode *myNode) {
  int pos, flag = 0;
  if (myNode) {
    if (item < myNode->item[1]) {
      pos = 0;
      flag = 0;
    } else {
      for (pos = myNode->count; (item < myNode->item[pos] && pos > 1); pos--)
        ;
      if (item == myNode->item[pos]) {
        flag = 1;
      } else {
        flag = 0;
      }
    }
    if (flag) {
      if (myNode->linker[pos - 1]) {
        copySuccessor(myNode, pos);
        flag = delValFromNode(myNode->item[pos], myNode->linker[pos]);
        if (flag == 0) {
          printf("Given data is not present in B-Tree\n");
        }
      } else {
        removeVal(myNode, pos);
      }
    } else {
      flag = delValFromNode(item, myNode->linker[pos]);
    }
    if (myNode->linker[pos]) {
      if (myNode->linker[pos]->count < MIN)
        adjustNode(myNode, pos);
    }
  }
  return flag;
}

// 删除操作
void delete (int item, struct BTreeNode *myNode) {
  struct BTreeNode *tmp;
  if (!delValFromNode(item, myNode)) {
    printf("Not present\n");
    return;
  } else {
    if (myNode->count == 0) {
      tmp = myNode;
      myNode = myNode->linker[0];
      free(tmp);
    }
  }
  root = myNode;
  return;
}

void searching(int item, int *pos, struct BTreeNode *myNode) {
  if (!myNode) {
    return;
  }

  if (item < myNode->item[1]) {
    *pos = 0;
  } else {
    for (*pos = myNode->count;
       (item < myNode->item[*pos] && *pos > 1); (*pos)--)
      ;
    if (item == myNode->item[*pos]) {
      printf("%d present in B-tree", item);
      return;
    }
  }
  searching(item, pos, myNode->linker[*pos]);
  return;
}

void traversal(struct BTreeNode *myNode) {
  int i;
  if (myNode) {
    for (i = 0; i < myNode->count; i++) {
      traversal(myNode->linker[i]);
      printf("%d ", myNode->item[i + 1]);
    }
    traversal(myNode->linker[i]);
  }
}

int main() {
  int item, ch;

  insertion(8);
  insertion(9);
  insertion(10);
  insertion(11);
  insertion(15);
  insertion(16);
  insertion(17);
  insertion(18);
  insertion(20);
  insertion(23);

  traversal(root);

  delete (20, root);
  printf("\n");
  traversal(root);
}

// 在 C++ 中从 B-树删除键

#include <iostream>
using namespace std;

class BTreeNode {
 int *keys;
 int t;
 BTreeNode **C;
 int n;
 bool leaf;

  public:
 BTreeNode(int _t, bool _leaf);

 void traverse();

 int findKey(int k);
 void insertNonFull(int k);
 void splitChild(int i, BTreeNode *y);
 void deletion(int k);
 void removeFromLeaf(int idx);
 void removeFromNonLeaf(int idx);
 int getPredecessor(int idx);
 int getSuccessor(int idx);
 void fill(int idx);
 void borrowFromPrev(int idx);
 void borrowFromNext(int idx);
 void merge(int idx);
 friend class BTree;
};

class BTree {
 BTreeNode *root;
 int t;

  public:
 BTree(int _t) {
   root = NULL;
   t = _t;
 }

 void traverse() {
   if (root != NULL)
     root->traverse();
 }

 void insertion(int k);

 void deletion(int k);
};

// B树节点
BTreeNode::BTreeNode(int t1, bool leaf1) {
 t = t1;
 leaf = leaf1;

 keys = new int[2 * t - 1];
 C = new BTreeNode *[2 * t];

 n = 0;
}

// 查找键
int BTreeNode::findKey(int k) {
 int idx = 0;
 while (idx < n && keys[idx] < k)
   ++idx;
 return idx;
}

// 删除操作
void BTreeNode::deletion(int k) {
 int idx = findKey(k);

 if (idx < n && keys[idx] == k) {
   if (leaf)
     removeFromLeaf(idx);
   else
     removeFromNonLeaf(idx);
 } else {
   if (leaf) {
     cout << "The key " << k << " is does not exist in the tree\n";
     return;
   }

   bool flag = ((idx == n) ? true : false);

   if (C[idx]->n < t)
     fill(idx);

   if (flag && idx > n)
     C[idx - 1]->deletion(k);
   else
     C[idx]->deletion(k);
 }
 return;
}

// 从叶子节点中移除
void BTreeNode::removeFromLeaf(int idx) {
 for (int i = idx + 1; i < n; ++i)
   keys[i - 1] = keys[i];

 n--;

 return;
}

// 从非叶子节点中删除
void BTreeNode::removeFromNonLeaf(int idx) {
 int k = keys[idx];

 if (C[idx]->n >= t) {
   int pred = getPredecessor(idx);
   keys[idx] = pred;
   C[idx]->deletion(pred);
 }

 else if (C[idx + 1]->n >= t) {
   int succ = getSuccessor(idx);
   keys[idx] = succ;
   C[idx + 1]->deletion(succ);
 }

 else {
   merge(idx);
   C[idx]->deletion(k);
 }
 return;
}

int BTreeNode::getPredecessor(int idx) {
 BTreeNode *cur = C[idx];
 while (!cur->leaf)
   cur = cur->C[cur->n];

 return cur->keys[cur->n - 1];
}

int BTreeNode::getSuccessor(int idx) {
 BTreeNode *cur = C[idx + 1];
 while (!cur->leaf)
   cur = cur->C[0];

 return cur->keys[0];
}

void BTreeNode::fill(int idx) {
 if (idx != 0 && C[idx - 1]->n >= t)
   borrowFromPrev(idx);

 else if (idx != n && C[idx + 1]->n >= t)
   borrowFromNext(idx);

 else {
   if (idx != n)
     merge(idx);
   else
     merge(idx - 1);
 }
 return;
}

// 从前一个节点借用
void BTreeNode::borrowFromPrev(int idx) {
 BTreeNode *child = C[idx];
 BTreeNode *sibling = C[idx - 1];

 for (int i = child->n - 1; i >= 0; --i)
   child->keys[i + 1] = child->keys[i];

 if (!child->leaf) {
   for (int i = child->n; i >= 0; --i)
     child->C[i + 1] = child->C[i];
 }

 child->keys[0] = keys[idx - 1];

 if (!child->leaf)
   child->C[0] = sibling->C[sibling->n];

 keys[idx - 1] = sibling->keys[sibling->n - 1];

 child->n += 1;
 sibling->n -= 1;

 return;
}

// 从下一个节点借用
void BTreeNode::borrowFromNext(int idx) {
 BTreeNode *child = C[idx];
 BTreeNode *sibling = C[idx + 1];

 child->keys[(child->n)] = keys[idx];

 if (!(child->leaf))
   child->C[(child->n) + 1] = sibling->C[0];

 keys[idx] = sibling->keys[0];

 for (int i = 1; i < sibling->n; ++i)
   sibling->keys[i - 1] = sibling->keys[i];

 if (!sibling->leaf) {
   for (int i = 1; i <= sibling->n; ++i)
     sibling->C[i - 1] = sibling->C[i];
 }

 child->n += 1;
 sibling->n -= 1;

 return;
}

// 合并
void BTreeNode::merge(int idx) {
 BTreeNode *child = C[idx];
 BTreeNode *sibling = C[idx + 1];

 child->keys[t - 1] = keys[idx];

 for (int i = 0; i < sibling->n; ++i)
   child->keys[i + t] = sibling->keys[i];

 if (!child->leaf) {
   for (int i = 0; i <= sibling->n; ++i)
     child->C[i + t] = sibling->C[i];
 }

 for (int i = idx + 1; i < n; ++i)
   keys[i - 1] = keys[i];

 for (int i = idx + 2; i <= n; ++i)
   C[i - 1] = C[i];

 child->n += sibling->n + 1;
 n--;

 delete (sibling);
 return;
}

// 插入操作
void BTree::insertion(int k) {
 if (root == NULL) {
   root = new BTreeNode(t, true);
   root->keys[0] = k;
   root->n = 1;
 } else {
   if (root->n == 2 * t - 1) {
     BTreeNode *s = new BTreeNode(t, false);

     s->C[0] = root;

     s->splitChild(0, root);

     int i = 0;
     if (s->keys[0] < k)
       i++;
     s->C[i]->insertNonFull(k);

     root = s;
   } else
     root->insertNonFull(k);
 }
}

// 插入非满节点
void BTreeNode::insertNonFull(int k) {
 int i = n - 1;

 if (leaf == true) {
   while (i >= 0 && keys[i] > k) {
     keys[i + 1] = keys[i];
     i--;
   }

   keys[i + 1] = k;
   n = n + 1;
 } else {
   while (i >= 0 && keys[i] > k)
     i--;

   if (C[i + 1]->n == 2 * t - 1) {
     splitChild(i + 1, C[i + 1]);

     if (keys[i + 1] < k)
       i++;
   }
   C[i + 1]->insertNonFull(k);
 }
}

// 分割子节点
void BTreeNode::splitChild(int i, BTreeNode *y) {
 BTreeNode *z = new BTreeNode(y->t, y->leaf);
 z->n = t - 1;

 for (int j = 0; j < t - 1; j++)
   z->keys[j] = y->keys[j + t];

 if (y->leaf == false) {
   for (int j = 0; j < t; j++)
     z->C[j] = y->C[j + t];
 }

 y->n = t - 1;

 for (int j = n; j >= i + 1; j--)
   C[j + 1] = C[j];

 C[i + 1] = z;

 for (int j = n - 1; j >= i; j--)
   keys[j + 1] = keys[j];

 keys[i] = y->keys[t - 1];

 n = n + 1;
}

// 遍历
void BTreeNode::traverse() {
 int i;
 for (i = 0; i < n; i++) {
   if (leaf == false)
     C[i]->traverse();
   cout << " " << keys[i];
 }

 if (leaf == false)
   C[i]->traverse();
}

// Delete Operation
void BTree::deletion(int k) {
 if (!root) {
   cout << "The tree is empty\n";
   return;
 }

 root->deletion(k);

 if (root->n == 0) {
   BTreeNode *tmp = root;
   if (root->leaf)
     root = NULL;
   else
     root = root->C[0];

   delete tmp;
 }
 return;
}

int main() {
 BTree t(3);
 t.insertion(8);
 t.insertion(9);
 t.insertion(10);
 t.insertion(11);
 t.insertion(15);
 t.insertion(16);
 t.insertion(17);
 t.insertion(18);
 t.insertion(20);
 t.insertion(23);

 cout << "The B-tree is: ";
 t.traverse();

 t.deletion(20);

 cout << "\nThe B-tree is: ";
 t.traverse();
}

删除复杂度

最佳情况时间复杂度：Θ(log n)

平均情况空间复杂度：Θ(n)

最坏情况空间复杂度：Θ(n)

从B树中删除

删除操作​

情况一​

情况二​

情况三​

Python、Java 和 C/C++ 示例​

删除复杂度​

删除操作

情况一

情况二

情况三

Python、Java 和 C/C++ 示例

删除复杂度