a. Please write a pseudocode function that takes a doubly circular linked list as input, and removes all the duplicate elements. For example, if the content of the doubly circular linked list is '1, 3, 3, 2, 4, 2', it becomes '1, 3, 2, 4' after your function is executed. No return values are expected. You have two options to store a set of unique elements: binary search tree and balanced search tree. You can directly use either of them, without explaining how they are implemented. Note: A node in a doubly circular linked list has two pointers, named 'next' and 'prev', respectively, where the 'next' pointer is used to find the next node and the 'prev' pointer is used to find the previous one.
b. Please analyze the complexity of your function when binary search tree is used to store the set of unique elements.
c. Please analyze the complexity of your function when balanced search tree is used to store the set of unique elements.
參考答案與解析
a.
FUNCTION RemoveDuplicates(head):
IF head == NULL: RETURN
T = 空的搜尋樹（BST 或平衡樹）
cur = head
first = true
REPEAT
nxt = cur.next
IF cur.value 已存在於 T 中:
cur.prev.next = cur.next
cur.next.prev = cur.prev
IF cur == head: head = nxt
ELSE:
將 cur.value 插入 T
cur = nxt
UNTIL cur == head
b. 用一般 BST：n 個元素每次搜尋/插入平均 O(log n)，但最壞情況（插入順序造成樹退化成鏈狀）單次操作 O(n)，整體最壞 O(n²)。 c. 用平衡樹（如 AVL/紅黑樹）：每次搜尋/插入都保證 O(log n)，整體最壞情況也是 O(n log n)。