2023新版数据结构与算法Java视频教程（下篇），java高级程序员必学的数据

跟着写了几遍B树，发现balance方法里向右借key的代码好像有点小错误。

//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应该是越界了。

考虑到每次调用insertChild方法都是在insertKey之后，key已经++，此时keyNumber的值已经与孩子数目相等，所以插入索引应为keyNumber，猜测满老师可能是没有测试到这个情况。这里我给出一个测试用例，如有漏误欢迎指正

@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());
}

期待满老师继续产出高质量视频呀！(*^▽^*)