資料結構與演算法

(5 points) B+ tree is an extension of B tree. The major differences from B tree are (1) all leaf nodes are linked together in a doubly-linked list, and (2) data points are stored on the leaf nodes only; internal nodes only hold keys and act as routers to the correct leaf node; the left child is smaller than the key and the right child is larger or equal than that. Please find any/all violations of a B+ tree structure in the following diagram. Assume the tree node can at most contain 4 data points (keys).

樹結構（由根往下；括號為標記候選）：

• 根：20
  • 左子（標記 (A)）：10
    • 6,8 → 葉 1,2,3 / 6,7 / 8,9
    • （標記 (B)）13,20 → 葉 10,11 / 13,14 / （標記 (C)）20,21
  • 右子：30,40
    • 22,27 → 葉 （標記 (D)）22,23 / 24,25 / 27,28
    • 33,36 → 葉 （標記 (E)）30,31 / 33,34 / 36,37
    • 47,52 → 葉 40,43 / 47,49 / 52,55