跟著寫(xiě)了幾遍B樹(shù)，發(fā)現(xiàn)balance方法里向右借key的代碼好像有點(diǎn)小錯(cuò)誤。

//2.2向右借用
if (right != null && right.keyNumber > MIN_KEY_NUMBER) {
    node.insertKey(parent.keys[index], node.keyNumber);
    parent.keys[index] = right.removeLeftmostKey();
    if (!right.leaf) {
        node.insertChild(right.removeLeftmostChild(), node.keyNumber + 1);
    }
    return;
}

這里node.keyNumber+1應(yīng)該是越界了。

考慮到每次調(diào)用insertChild方法都是在insertKey之后，key已經(jīng)++，此時(shí)keyNumber的值已經(jīng)與孩子數(shù)目相等，所以插入索引應(yīng)為keyNumber，猜測(cè)滿(mǎn)老師可能是沒(méi)有測(cè)試到這個(gè)情況。這里我給出一個(gè)測(cè)試用例，如有漏誤歡迎指正

@Test
@DisplayName("case5: balance left rotate")
public void testRemove5_2() {
    /*
        4|5|6  ==>  5
                   / \
                  4   6
       5
      / \        ==>      5|7    ==>    5|7
     4   6|7|8           / | \         / | \
                        4  6  8      2|3|4  6 8

     3|5|7                     5                             5
    / | | \  ==>             /   \                        /     \
   2  4 6  8                3     7              ==>     3      7|9
                           / \   / \                    / \    / | \
                          2   4 6   8|9|10             2   4  6  8  10

     5                           7
    / \                        /   \
   _   7|9      ==>           5     9
   |   /|\                   / \   / \
  2|4 6 8 10                2|4 6 8  10
    */
    BTree tree = new BTree(2);
    tree.put(4);
    tree.put(5);
    tree.put(6);
    tree.put(7);
    tree.put(8);
    tree.put(3);
    tree.put(2);
    tree.put(9);
    tree.put(10);

    tree.remove(3);
    assertEquals("[7]", tree.root.toString());
    assertEquals("[5]", tree.root.children[0].toString());
    assertEquals("[9]", tree.root.children[1].toString());
    assertEquals("[2, 4]", tree.root.children[0].children[0].toString());
    assertEquals("[6]", tree.root.children[0].children[1].toString());
    assertEquals("[8]", tree.root.children[1].children[0].toString());
    assertEquals("[10]", tree.root.children[1].children[1].toString());
}

期待滿(mǎn)老師繼續(xù)產(chǎn)出高質(zhì)量視頻呀！(*^▽^*)