原文： https://www.programiz.com/dsa/deletion-from-a-b-tree

在本教程中，您将学习如何从 b 树中删除键。 此外，您还将找到在 C，C++ ，Java 和 Python 中从 B 树中删除键的工作示例。

删除 B 树上的元素包括三个主要事件：搜索要删除的键存在的节点，删除键并按需平衡树。

删除树时，可能会发生称为下溢的条件。 当节点包含的数量少于其应持有的最小键数时，就会发生下溢。

在研究删除操作之前，应了解以下术语：

  1. 有序前驱
    节点左子级上的最大键称为其有序前驱。
  2. 有序后继
    节点右子级上的最小键称为其有序后继。

删除操作

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

  1. 一个节点最多可以有m个子节点。 （即 3）
  2. 一个节点最多可以包含m - 1个键。 （即 2）
  3. 一个节点至少应具有⌈m/2⌉个子节点。 （即 2）
  4. 一个节点（根节点除外）应至少包含⌈m/2⌉ - 1键。 （即 1）

B 树中的删除操作主要有三种情况。

情况一

要删除的键位于叶子中。 有两种情况。

  1. 删除键不会违反节点应持有的最小键数的属性。
    在下面的树中，删除 32 不违反上述属性。
    从 B 树删除 - 图1
    从 B 树中删除叶子键（32）

  2. 键的删除违反了节点应持有的最小键数的属性。 在这种情况下，我们以从左到右的顺序从其直接相邻的兄弟节点借用键。
    首先，访问紧邻的左兄弟姐妹。 如果左兄弟节点的键数目超过最小数目，则从该节点借用键。
    否则，请检查以从紧邻的右同级节点借用。
    在下面的树中，删除 31 将导致上述情况。 让我们从左侧兄弟节点借用一个键。
    从 B 树删除 - 图2
    删除叶子键（31）
    如果两个直接同级节点都已经具有最小数量的键，则将该节点与左同级节点或右同级节点合并。 此合并是通过父节点完成的。
    在上述情况下，删除 30 个结果。
    从 B 树删除 - 图3
    删除叶子键（30）

情况二

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

  1. 如果左子节点的键数超过最小数目，则删除的内部节点将替换为有序的前驱节点。
    从 B 树删除 - 图4
    删除内部节点（33）

  2. 如果正确的子项超过了最小数目的键，则删除的内部节点将被有序后继替换。

  3. 如果任一子项的键数恰好最小，则合并左子项和右子项。
    从 B 树删除 - 图5
    删除内部节点（30）
    合并后，如果父节点的键数少于最小数目，则像情况 I 一样查找同级。

情况三

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

同样，寻找同胞借用钥匙。 但是，如果同级也只有最少数量的键，则将同级节点与父级合并。 相应地安排子级们（增加顺序）。

从 B 树删除 - 图6

删除内部节点（10）

Python，Java 和 C/C++ 示例

  1. # Deleting a key on a B-tree in Python
  3. # Btree node
  4. class BTreeNode:
  5.     def __init__(self, leaf=False):
  6.         self.leaf = leaf
  7.         self.keys = []
  8.         self.child = []
  10. class BTree:
  11.     def __init__(self, t):
  12.         self.root = BTreeNode(True)
  13.         self.t = t
  15.     # Insert a key
  16.     def insert(self, k):
  17.         root = self.root
  18.         if len(root.keys) == (2 * self.t) - 1:
  19.             temp = BTreeNode()
  20.             self.root = temp
  21.             temp.child.insert(0, root)
  22.             self.split_child(temp, 0)
  23.             self.insert_non_full(temp, k)
  24.         else:
  25.             self.insert_non_full(root, k)
  27.     # Insert non full
  28.     def insert_non_full(self, x, k):
  29.         i = len(x.keys) - 1
  30.         if x.leaf:
  31.             x.keys.append((None, None))
  32.             while i >= 0 and k[0] < x.keys[i][0]:
  33.                 x.keys[i + 1] = x.keys[i]
  34.                 i -= 1
  35.             x.keys[i + 1] = k
  36.         else:
  37.             while i >= 0 and k[0] < x.keys[i][0]:
  38.                 i -= 1
  39.             i += 1
  40.             if len(x.child[i].keys) == (2 * self.t) - 1:
  41.                 self.split_child(x, i)
  42.                 if k[0] > x.keys[i][0]:
  43.                     i += 1
  44.             self.insert_non_full(x.child[i], k)
  46.     # Split the child
  47.     def split_child(self, x, i):
  48.         t = self.t
  49.         y = x.child[i]
  50.         z = BTreeNode(y.leaf)
  51.         x.child.insert(i + 1, z)
  52.         x.keys.insert(i, y.keys[t - 1])
  53.         z.keys = y.keys[t: (2 * t) - 1]
  54.         y.keys = y.keys[0: t - 1]
  55.         if not y.leaf:
  56.             z.child = y.child[t: 2 * t]
  57.             y.child = y.child[0: t - 1]
  59.     # Delete a node
  60.     def delete(self, x, k):
  61.         t = self.t
  62.         i = 0
  63.         while i < len(x.keys) and k[0] > x.keys[i][0]:
  64.             i += 1
  65.         if x.leaf:
  66.             if i < len(x.keys) and x.keys[i][0] == k[0]:
  67.                 x.keys.pop(i)
  68.                 return
  69.             return
  71.         if i < len(x.keys) and x.keys[i][0] == k[0]:
  72.             return self.delete_internal_node(x, k, i)
  73.         elif len(x.child[i].keys) >= t:
  74.             self.delete(x.child[i], k)
  75.         else:
  76.             if i != 0 and i + 2 < len(x.child):
  77.                 if len(x.child[i - 1].keys) >= t:
  78.                     self.delete_sibling(x, i, i - 1)
  79.                 elif len(x.child[i + 1].keys) >= t:
  80.                     self.delete_sibling(x, i, i + 1)
  81.                 else:
  82.                     self.delete_merge(x, i, i + 1)
  83.             elif i == 0:
  84.                 if len(x.child[i + 1].keys) >= t:
  85.                     self.delete_sibling(x, i, i + 1)
  86.                 else:
  87.                     self.delete_merge(x, i, i + 1)
  88.             elif i + 1 == len(x.child):
  89.                 if len(x.child[i - 1].keys) >= t:
  90.                     self.delete_sibling(x, i, i - 1)
  91.                 else:
  92.                     self.delete_merge(x, i, i - 1)
  93.             self.delete(x.child[i], k)
  95.     # Delete internal node
  96.     def delete_internal_node(self, x, k, i):
  97.         t = self.t
  98.         if x.leaf:
  99.             if x.keys[i][0] == k[0]:
  100.                 x.keys.pop(i)
  101.                 return
  102.             return
  104.         if len(x.child[i].keys) >= t:
  105.             x.keys[i] = self.delete_predecessor(x.child[i])
  106.             return
  107.         elif len(x.child[i + 1].keys) >= t:
  108.             x.keys[i] = self.delete_successor(x.child[i + 1])
  109.             return
  110.         else:
  111.             self.delete_merge(x, i, i + 1)
  112.             self.delete_internal_node(x.child[i], k, self.t - 1)
  114.     # Delete the predecessor
  115.     def delete_predecessor(self, x):
  116.         if x.leaf:
  117.             return x.pop()
  118.         n = len(x.keys) - 1
  119.         if len(x.child[n].keys) >= self.t:
  120.             self.delete_sibling(x, n + 1, n)
  121.         else:
  122.             self.delete_merge(x, n, n + 1)
  123.         self.delete_predecessor(x.child[n])
  125.     # Delete the successor
  126.     def delete_successor(self, x):
  127.         if x.leaf:
  128.             return x.keys.pop(0)
  129.         if len(x.child[1].keys) >= self.t:
  130.             self.delete_sibling(x, 0, 1)
  131.         else:
  132.             self.delete_merge(x, 0, 1)
  133.         self.delete_successor(x.child[0])
  135.     # Delete resolution
  136.     def delete_merge(self, x, i, j):
  137.         cnode = x.child[i]
  139.         if j > i:
  140.             rsnode = x.child[j]
  141.             cnode.keys.append(x.keys[i])
  142.             for k in range(len(rsnode.keys)):
  143.                 cnode.keys.append(rsnode.keys[k])
  144.                 if len(rsnode.child) > 0:
  145.                     cnode.child.append(rsnode.child[k])
  146.             if len(rsnode.child) > 0:
  147.                 cnode.child.append(rsnode.child.pop())
  148.             new = cnode
  149.             x.keys.pop(i)
  150.             x.child.pop(j)
  151.         else:
  152.             lsnode = x.child[j]
  153.             lsnode.keys.append(x.keys[j])
  154.             for i in range(len(cnode.keys)):
  155.                 lsnode.keys.append(cnode.keys[i])
  156.                 if len(lsnode.child) > 0:
  157.                     lsnode.child.append(cnode.child[i])
  158.             if len(lsnode.child) > 0:
  159.                 lsnode.child.append(cnode.child.pop())
  160.             new = lsnode
  161.             x.keys.pop(j)
  162.             x.child.pop(i)
  164.         if x == self.root and len(x.keys) == 0:
  165.             self.root = new
  167.     # Delete the sibling
  168.     def delete_sibling(self, x, i, j):
  169.         cnode = x.child[i]
  170.         if i < j:
  171.             rsnode = x.child[j]
  172.             cnode.keys.append(x.keys[i])
  173.             x.keys[i] = rsnode.keys[0]
  174.             if len(rsnode.child) > 0:
  175.                 cnode.child.append(rsnode.child[0])
  176.                 rsnode.child.pop(0)
  177.             rsnode.keys.pop(0)
  178.         else:
  179.             lsnode = x.child[j]
  180.             cnode.keys.insert(0, x.keys[i - 1])
  181.             x.keys[i - 1] = lsnode.keys.pop()
  182.             if len(lsnode.child) > 0:
  183.                 cnode.child.insert(0, lsnode.child.pop())
  185.     # Print the tree
  186.     def print_tree(self, x, l=0):
  187.         print("Level ", l, " ", len(x.keys), end=":")
  188.         for i in x.keys:
  189.             print(i, end=" ")
  190.         print()
  191.         l += 1
  192.         if len(x.child) > 0:
  193.             for i in x.child:
  194.                 self.print_tree(i, l)
  196. def main():
  197.     B = BTree(3)
  199.     for i in range(10):
  200.         B.insert((i, 2 * i))
  202.     B.print_tree(B.root)
  204.     B.delete(B.root, (8,))
  205.     print("\n")
  206.     B.print_tree(B.root)
  1. // Inserting a key on a B-tree in Java
  3. import java.util.Stack;
  5. public class BTree {
  7.   private int T;
  9.   public class Node {
  10.     int n;
  11.     int key[] = new int[2 * T - 1];
  12.     Node child[] = new Node[2 * T];
  13.     boolean leaf = true;
  15.     public int Find(int k) {
  16.       for (int i = 0; i < this.n; i++) {
  17.         if (this.key[i] == k) {
  18.           return i;
  19.         }
  20.       }
  21.       return -1;
  22.     };
  23.   }
  25.   public BTree(int t) {
  26.     T = t;
  27.     root = new Node();
  28.     root.n = 0;
  29.     root.leaf = true;
  30.   }
  32.   private Node root;
  34.   // Search the key
  35.   private Node Search(Node x, int key) {
  36.     int i = 0;
  37.     if (x == null)
  38.       return x;
  39.     for (i = 0; i < x.n; i++) {
  40.       if (key < x.key[i]) {
  41.         break;
  42.       }
  43.       if (key == x.key[i]) {
  44.         return x;
  45.       }
  46.     }
  47.     if (x.leaf) {
  48.       return null;
  49.     } else {
  50.       return Search(x.child[i], key);
  51.     }
  52.   }
  54.   // Split function
  55.   private void Split(Node x, int pos, Node y) {
  56.     Node z = new Node();
  57.     z.leaf = y.leaf;
  58.     z.n = T - 1;
  59.     for (int j = 0; j < T - 1; j++) {
  60.       z.key[j] = y.key[j + T];
  61.     }
  62.     if (!y.leaf) {
  63.       for (int j = 0; j < T; j++) {
  64.         z.child[j] = y.child[j + T];
  65.       }
  66.     }
  67.     y.n = T - 1;
  68.     for (int j = x.n; j >= pos + 1; j--) {
  69.       x.child[j + 1] = x.child[j];
  70.     }
  71.     x.child[pos + 1] = z;
  73.     for (int j = x.n - 1; j >= pos; j--) {
  74.       x.key[j + 1] = x.key[j];
  75.     }
  76.     x.key[pos] = y.key[T - 1];
  77.     x.n = x.n + 1;
  78.   }
  80.   // Insert the key
  81.   public void Insert(final int key) {
  82.     Node r = root;
  83.     if (r.n == 2 * T - 1) {
  84.       Node s = new Node();
  85.       root = s;
  86.       s.leaf = false;
  87.       s.n = 0;
  88.       s.child[0] = r;
  89.       Split(s, 0, r);
  90.       _Insert(s, key);
  91.     } else {
  92.       _Insert(r, key);
  93.     }
  94.   }
  96.   // Insert the node
  97.   final private void _Insert(Node x, int k) {
  99.     if (x.leaf) {
  100.       int i = 0;
  101.       for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
  102.         x.key[i + 1] = x.key[i];
  103.       }
  104.       x.key[i + 1] = k;
  105.       x.n = x.n + 1;
  106.     } else {
  107.       int i = 0;
  108.       for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
  109.       }
  110.       ;
  111.       i++;
  112.       Node tmp = x.child[i];
  113.       if (tmp.n == 2 * T - 1) {
  114.         Split(x, i, tmp);
  115.         if (k > x.key[i]) {
  116.           i++;
  117.         }
  118.       }
  119.       _Insert(x.child[i], k);
  120.     }
  122.   }
  124.   public void Show() {
  125.     Show(root);
  126.   }
  128.   private void Remove(Node x, int key) {
  129.     int pos = x.Find(key);
  130.     if (pos != -1) {
  131.       if (x.leaf) {
  132.         int i = 0;
  133.         for (i = 0; i < x.n && x.key[i] != key; i++) {
  134.         }
  135.         ;
  136.         for (; i < x.n; i++) {
  137.           if (i != 2 * T - 2) {
  138.             x.key[i] = x.key[i + 1];
  139.           }
  140.         }
  141.         x.n--;
  142.         return;
  143.       }
  144.       if (!x.leaf) {
  146.         Node pred = x.child[pos];
  147.         int predKey = 0;
  148.         if (pred.n >= T) {
  149.           for (;;) {
  150.             if (pred.leaf) {
  151.               System.out.println(pred.n);
  152.               predKey = pred.key[pred.n - 1];
  153.               break;
  154.             } else {
  155.               pred = pred.child[pred.n];
  156.             }
  157.           }
  158.           Remove(pred, predKey);
  159.           x.key[pos] = predKey;
  160.           return;
  161.         }
  163.         Node nextNode = x.child[pos + 1];
  164.         if (nextNode.n >= T) {
  165.           int nextKey = nextNode.key[0];
  166.           if (!nextNode.leaf) {
  167.             nextNode = nextNode.child[0];
  168.             for (;;) {
  169.               if (nextNode.leaf) {
  170.                 nextKey = nextNode.key[nextNode.n - 1];
  171.                 break;
  172.               } else {
  173.                 nextNode = nextNode.child[nextNode.n];
  174.               }
  175.             }
  176.           }
  177.           Remove(nextNode, nextKey);
  178.           x.key[pos] = nextKey;
  179.           return;
  180.         }
  182.         int temp = pred.n + 1;
  183.         pred.key[pred.n++] = x.key[pos];
  184.         for (int i = 0, j = pred.n; i < nextNode.n; i++) {
  185.           pred.key[j++] = nextNode.key[i];
  186.           pred.n++;
  187.         }
  188.         for (int i = 0; i < nextNode.n + 1; i++) {
  189.           pred.child[temp++] = nextNode.child[i];
  190.         }
  192.         x.child[pos] = pred;
  193.         for (int i = pos; i < x.n; i++) {
  194.           if (i != 2 * T - 2) {
  195.             x.key[i] = x.key[i + 1];
  196.           }
  197.         }
  198.         for (int i = pos + 1; i < x.n + 1; i++) {
  199.           if (i != 2 * T - 1) {
  200.             x.child[i] = x.child[i + 1];
  201.           }
  202.         }
  203.         x.n--;
  204.         if (x.n == 0) {
  205.           if (x == root) {
  206.             root = x.child[0];
  207.           }
  208.           x = x.child[0];
  209.         }
  210.         Remove(pred, key);
  211.         return;
  212.       }
  213.     } else {
  214.       for (pos = 0; pos < x.n; pos++) {
  215.         if (x.key[pos] > key) {
  216.           break;
  217.         }
  218.       }
  219.       Node tmp = x.child[pos];
  220.       if (tmp.n >= T) {
  221.         Remove(tmp, key);
  222.         return;
  223.       }
  224.       if (true) {
  225.         Node nb = null;
  226.         int devider = -1;
  228.         if (pos != x.n && x.child[pos + 1].n >= T) {
  229.           devider = x.key[pos];
  230.           nb = x.child[pos + 1];
  231.           x.key[pos] = nb.key[0];
  232.           tmp.key[tmp.n++] = devider;
  233.           tmp.child[tmp.n] = nb.child[0];
  234.           for (int i = 1; i < nb.n; i++) {
  235.             nb.key[i - 1] = nb.key[i];
  236.           }
  237.           for (int i = 1; i <= nb.n; i++) {
  238.             nb.child[i - 1] = nb.child[i];
  239.           }
  240.           nb.n--;
  241.           Remove(tmp, key);
  242.           return;
  243.         } else if (pos != 0 && x.child[pos - 1].n >= T) {
  245.           devider = x.key[pos - 1];
  246.           nb = x.child[pos - 1];
  247.           x.key[pos - 1] = nb.key[nb.n - 1];
  248.           Node child = nb.child[nb.n];
  249.           nb.n--;
  251.           for (int i = tmp.n; i > 0; i--) {
  252.             tmp.key[i] = tmp.key[i - 1];
  253.           }
  254.           tmp.key[0] = devider;
  255.           for (int i = tmp.n + 1; i > 0; i--) {
  256.             tmp.child[i] = tmp.child[i - 1];
  257.           }
  258.           tmp.child[0] = child;
  259.           tmp.n++;
  260.           Remove(tmp, key);
  261.           return;
  262.         } else {
  263.           Node lt = null;
  264.           Node rt = null;
  265.           boolean last = false;
  266.           if (pos != x.n) {
  267.             devider = x.key[pos];
  268.             lt = x.child[pos];
  269.             rt = x.child[pos + 1];
  270.           } else {
  271.             devider = x.key[pos - 1];
  272.             rt = x.child[pos];
  273.             lt = x.child[pos - 1];
  274.             last = true;
  275.             pos--;
  276.           }
  277.           for (int i = pos; i < x.n - 1; i++) {
  278.             x.key[i] = x.key[i + 1];
  279.           }
  280.           for (int i = pos + 1; i < x.n; i++) {
  281.             x.child[i] = x.child[i + 1];
  282.           }
  283.           x.n--;
  284.           lt.key[lt.n++] = devider;
  286.           for (int i = 0, j = lt.n; i < rt.n + 1; i++, j++) {
  287.             if (i < rt.n) {
  288.               lt.key[j] = rt.key[i];
  289.             }
  290.             lt.child[j] = rt.child[i];
  291.           }
  292.           lt.n += rt.n;
  293.           if (x.n == 0) {
  294.             if (x == root) {
  295.               root = x.child[0];
  296.             }
  297.             x = x.child[0];
  298.           }
  299.           Remove(lt, key);
  300.           return;
  301.         }
  302.       }
  303.     }
  304.   }
  306.   public void Remove(int key) {
  307.     Node x = Search(root, key);
  308.     if (x == null) {
  309.       return;
  310.     }
  311.     Remove(root, key);
  312.   }
  314.   public void Task(int a, int b) {
  315.     Stack<Integer> st = new Stack<>();
  316.     FindKeys(a, b, root, st);
  317.     while (st.isEmpty() == false) {
  318.       this.Remove(root, st.pop());
  319.     }
  320.   }
  322.   private void FindKeys(int a, int b, Node x, Stack<Integer> st) {
  323.     int i = 0;
  324.     for (i = 0; i < x.n && x.key[i] < b; i++) {
  325.       if (x.key[i] > a) {
  326.         st.push(x.key[i]);
  327.       }
  328.     }
  329.     if (!x.leaf) {
  330.       for (int j = 0; j < i + 1; j++) {
  331.         FindKeys(a, b, x.child[j], st);
  332.       }
  333.     }
  334.   }
  336.   public boolean Contain(int k) {
  337.     if (this.Search(root, k) != null) {
  338.       return true;
  339.     } else {
  340.       return false;
  341.     }
  342.   }
  344.   // Show the node
  345.   private void Show(Node x) {
  346.     assert (x == null);
  347.     for (int i = 0; i < x.n; i++) {
  348.       System.out.print(x.key[i] + " ");
  349.     }
  350.     if (!x.leaf) {
  351.       for (int i = 0; i < x.n + 1; i++) {
  352.         Show(x.child[i]);
  353.       }
  354.     }
  355.   }
  357.   public static void main(String[] args) {
  358.     BTree b = new BTree(3);
  359.     b.Insert(8);
  360.     b.Insert(9);
  361.     b.Insert(10);
  362.     b.Insert(11);
  363.     b.Insert(15);
  364.     b.Insert(20);
  365.     b.Insert(17);
  367.     b.Show();
  369.     b.Remove(10);
  370.     System.out.println();
  371.     b.Show();
  372.   }
  373. }
// 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;

// Node creation
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;
}

// Add value to the node
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++;
}

// Split the node
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--;
}

// Set the value in the node
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;
}

// Insertion operation
void insertion(int item) {
  int flag, i;
  struct BTreeNode *child;

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

// Copy the successor
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];
}

// Remove the value
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--;
}

// Do right shift
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;
}

// Do left shift
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;
}

// Merge the nodes
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);
}

// Adjust the node
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);
    }
  }
}

// Delete a value from the node
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;
}

// Delete operaiton
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);
}

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

#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 tree node
BTreeNode::BTreeNode(int t1, bool leaf1) {
  t = t1;
  leaf = leaf1;

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

  n = 0;
}

// Find the key
int BTreeNode::findKey(int k) {
  int idx = 0;
  while (idx < n && keys[idx] < k)
    ++idx;
  return idx;
}

// Deletion operation
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;
}

// Remove from the leaf
void BTreeNode::removeFromLeaf(int idx) {
  for (int i = idx + 1; i < n; ++i)
    keys[i - 1] = keys[i];

  n--;

  return;
}

// Delete from non leaf node
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;
}

// Borrow from previous
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;
}

// Borrow from the next
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;
}

// Merge
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;
}

// Insertion operation
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);
  }
}

// Insertion non full
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);
  }
}

// Split child
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;
}

// Traverse
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)