資料結構與演算法

(5 points)（單選）Given a list of binary trees $T = \{t_1, t_2, \dots, t_7\}$ where each node is 0 or 1 shown as below, we would like to insert these trees into a linear-probing hash table of length $N = 11$. The hash function $f(t) = g(h(t)) \bmod N$, where $h(t)$ is the binary sequence obtained from in-order traversal of tree $t$ and $g(\cdot)$ converts a binary sequence to a decimal number. For instance, $g(\text{"1111111"}) = 127$. Here's the question: how many collisions occur during the insertion process?

七棵樹皆為 7 節點完全二元樹（根；左子 cL、右子 cR；cL 的左右葉 a,b；cR 的左右葉 c,d），中序序列為 [a, cL, b, root, c, cR, d]：

• $t_1$：root=0, cL=0, cR=1, a=0,b=1,c=1,d=0
• $t_2$：root=0, cL=0, cR=0, a=0,b=0,c=1,d=0
• $t_3$：root=1, cL=0, cR=1, a=0,b=0,c=1,d=1
• $t_4$：root=1, cL=0, cR=0, a=0,b=1,c=1,d=0
• $t_5$：root=0, cL=0, cR=0, a=0,b=1,c=0,d=1
• $t_6$：root=1, cL=0, cR=0, a=1,b=1,c=0,d=0
• $t_7$：root=1, cL=1, cR=0, a=0,b=1,c=1,d=0