資料結構›Ch9 進階樹
第 8 題/共 88 題
◀ DS 8/88
8. BST、Join Operation、AVL、Red-Black Tree
#DS-09-008難BSTJoin OperationAVLRed-Black Tree

A Binary Search Tree (abbreviated as BST) is a tree structure comprised of nodes that maintain a specific order among their keys. Given a single node xx and two BSTs LL and RR, in which l.key<x.key<r.keyl.key < x.key < r.key for all nodes l∈Ll \in L and r∈Rr \in R, the objective is to design a Join(L,x,R)Join(L,x,R) function that integrates the given input into a unified BST TT with the nodes L∪{x}∪RL \cup \{x\} \cup R. Be aware that AVL and Red-Black trees are specific types of BSTs. Given the constraint that TT, LL, and RR must share the same type, they are required to be either all BSTs, all AVL trees, or all Red-Black trees.

The Join(L,x,R)Join(L,x,R) function is implemented with the steps: (1) selecting a subtree T′T' from either LL or RR, where a subtree is defined as potentially being empty, a portion, or the entire tree, (2) detaching T′T', (3) attaching the other tree (which does not contain T′T') under xx, (4) re-attaching the tree rooted at xx to the former parent of T′T'. The modified tree is then returned as TT. If T′T' has no former parent, the tree rooted at xx is simply returned as TT. The following figure demonstrates an example result of Join(L1,x1,R1)Join(L_1,x_1,R_1), where the letters α,β,γ,δ,\alpha, \beta, \gamma, \delta, and η\eta denote arbitrary subtrees.

Please note that almost all steps, except for (1), have been finalized — there could be multiple ways to choose T′T' in (1). The tree returned from Join(L,x,R)Join(L,x,R) may not be unique. Additionally, unlike AVL or Red-Black trees, Join(L,x,R)Join(L,x,R) does not perform re-coloring and re-balancing. Consider the following arguments passed into Join(L2,x2,R2)Join(L_2,x_2,R_2). All nil nodes (considered as leaves in red-black trees) are omitted for brevity.

Please select the correct description(s) below.

題目附圖題目附圖
📄 台大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch9 進階樹
本章題號 · 1–20 / 88