資料結構與演算法

(10 points) A Binary Search Tree (BST) is comprised of nodes that maintain a specific order among their keys. Given a single node $x$ and two BSTs $L$ and $R$, in which $l.\text{key} < x.\text{key} < r.\text{key}$ for all nodes $l \in L$ and $r \in R$, the objective is to design a $\text{Join}(L, x, R)$ function that integrates the input into a unified BST $T$ with the nodes $L \cup \{x\} \cup R$. AVL and Red-Black trees are specific types of BSTs. Given the constraint that $T$, $L$, and $R$ must share the same type, they are required to be either all BSTs, all AVL trees, or all Red-Black trees.

The $\text{Join}(L, x, R)$ function is implemented with the steps: (1) selecting a subtree $T'$ from either $L$ or $R$ (a subtree may be empty, a portion, or the entire tree), (2) detaching $T'$, (3) attaching $T'$ under the node $x$, (4) attaching the other tree (which does not contain $T'$) under $x$, and (5) re-attaching the tree rooted at $x$ to the former parent of $T'$. The modified tree is returned as $T$. If $T'$ has no former parent, the tree rooted at $x$ is simply returned as $T$.

Almost all steps except (1) have been finalized — there could be multiple ways to choose $T'$ in (1), so the tree returned may not be unique. Unlike AVL or Red-Black trees, $\text{Join}(L, x, R)$ does not perform re-coloring and re-balancing. Consider the following arguments passed into $\text{Join}(L_2, x_2, R_2)$. All nil nodes (considered as leaves in red-black trees) are omitted for brevity.

• $L_2$: root $2$, with left child $1$ and right child $3$.
• $x_2 = 4$.
• $R_2$: root $10$; $10.\text{left}=7$, $10.\text{right}=13$; $7.\text{left}=5$, $7.\text{right}=9$; $5.\text{right}=6$; $9.\text{left}=8$; $13.\text{left}=11$, $13.\text{right}=15$; $11.\text{right}=12$; $15.\text{left}=14$, $15.\text{right}=16$; $16.\text{right}=17$.

Please select the correct description(s) below.