19｜智慧指標與二元搜尋樹

還沒完成只限 C++CPU 時間上限 1 秒計算 heap 用量

題目說明

只限 C++｜CPU 時間上限 1 秒｜計算 heap 用量，有記憶體洩漏就不通過

題目

二元搜尋樹（binary search tree, BST）是一種樹狀結構：每個節點存一個值，最多有左、右兩個子節點，而且

左子樹裡的所有值都比它小，
右子樹裡的所有值都比它大。

        50
       /  \
     30    70
    /  \  /  \
   20 40 60  80

一開始樹是空的。依序執行輸入的指令：

指令	動作	輸出
`insert x`	插入 x；x 已經在樹裡就忽略	無
`find x`	x 在不在樹裡	`yes` 或 `no`
`erase x`	刪除 x；x 不在樹裡就什麼都不做	無
`inorder`	中序走訪：先左子樹、再自己、再右子樹	所有值由小到大，以一個空白分隔；空樹輸出 `empty`
`height`	樹的高度	空樹是 `0`，只有一個節點是 `1`，否則是 1 + 左右子樹高度的較大者

height 的答案取決於樹的形狀，所以插入和刪除都必須照下面的規則做：

插入：從根開始，x 比目前節點小就往左、比較大就往右，走到空的位置就把新節點放在那裡。
刪除：找到值是 x 的節點之後——
1. 它沒有左子樹：用它的右子樹取代它（右子樹也可能是空的）。
2. 它有左子樹、沒有右子樹：用它的左子樹取代它。
3. 左右子樹都有：找出右子樹裡最小的值（從右子節點開始一路往左走到底），把這個值複製到要刪除的節點，再從右子樹裡刪除這個最小值（它一定沒有左子樹，所以會落到情況 1）。

這一題的規定：用智慧指標管理記憶體

子節點必須用 std::unique_ptr<Node> 存（根也是），用 std::make_unique<Node>(x) 建立節點。
你的程式裡不能出現 new 和 delete。
但是程式結束時不能有記憶體洩漏，被刪除的節點也要真的被釋放。
不要用 std::set、std::map 等現成的容器存資料。

（檢查程式看不出你有沒有用 new / delete 或 std::set，請自己遵守。）

聽起來矛盾？這就是 C++ 的 RAII：unique_ptr 被銷毀或被賦予新的值時，會自動 delete 它原本擁有的節點；節點被 delete 時，它的 left、right 也跟著被銷毀，於是整棵子樹一層一層自動釋放。只要讓每個節點都剛好被一個 unique_ptr 擁有，記憶體就會在正確的時間被釋放。

輸入

每行一個指令，格式如上表，指令名稱和數字之間有一個空白。
指令最多 20000 個（也可能完全沒有指令），一直讀到輸入結束（EOF）為止。
每個 x 都是整數，−1000000000 ≤ x ≤ 1000000000。
大部分測試的值是隨機的，樹的高度不會太大；但也有依照大小順序插入、讓樹變成一條長鏈的測試。任何時候樹的高度都不超過 1000，所以用遞迴寫沒有問題。

輸出

只有 find、inorder、height 會輸出，每次輸出一行，格式如上表。

範例

輸入：

insert 50
insert 30
insert 70
insert 20
insert 40
insert 60
insert 80
insert 30
inorder
height
find 40
find 45
erase 30
inorder
erase 50
inorder
find 50
insert 75
height
erase 99
erase 60
erase 20
erase 40
erase 70
erase 75
erase 80
inorder
height

輸出：

20 30 40 50 60 70 80
3
yes
no
20 40 50 60 70 80
20 40 60 70 80
no
4
empty
0

說明：前 7 個 insert 建出上面那棵樹，第 8 個 insert 30 重複所以忽略。erase 30 時 30 左右都有子節點，右子樹最小的是 40，所以 40 移到 30 的位置；erase 50 同理由 60 取代。insert 75 之後最長的路徑是 60 → 70 → 80 → 75，高度 4。

複習重點

C++：

#include <memory>；std::unique_ptr<T> 是「獨占」一個物件的智慧指標，用 std::make_unique<T>(建構子的參數) 建立
用起來和一般指標很像：p->value、*p、if (p)（是不是空的）、p = nullptr（釋放並變成空的）
unique_ptr 不能複製（不然兩個指標會 delete 同一個物件兩次），只能用 std::move 把擁有權轉移給另一個：a = std::move(b); 之後 b 變成空的，a 原本擁有的物件會被自動 delete
函式要修改「某個位置上的 unique_ptr」（例如把新節點接上去），參數寫成參考 std::unique_ptr<Node> &node
只想「看」節點、不擁有它時，用 p.get() 取得一般指標 const Node *；一般指標不負責釋放
RAII：把資源（記憶體、檔案……）的釋放寫在物件的解構子裡，物件離開範圍時自動釋放。std::vector、std::string、std::unique_ptr 都是這樣，所以平常寫 C++ 很少需要自己寫 delete
struct 的成員會在 struct 被銷毀時自動銷毀，所以 Node 不需要自己寫解構子

C 對照：

C 沒有解構子，第 17、18 題的每個 malloc 都要自己找地方 free；這一題的樹在 C 裡要寫一個遞迴的 free_tree，先釋放左右子樹，再釋放自己

提示 1：Node 和 insert 長什麼樣子？

struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) {}   // left、right 預設是空的
};

std::unique_ptr<Node> root;   // 空樹

void insert(std::unique_ptr<Node> &node, int x) {
    if (!node) {
        node = std::make_unique<Node>(x);   // 空的位置：接上新節點
        return;
    }
    // x 比較小就 insert(node->left, x)，比較大就 insert(node->right, x)
}

參數一定要是參考（&）：如果寫成 std::unique_ptr<Node> node，那是要求「複製」一個 unique_ptr，編譯器會報錯；就算改用 std::move 傳進去，新節點也只會接在函式裡的區域變數上，函式結束就被釋放了。

提示 2：find、inorder、height 只需要「看」

這三個操作不會改變樹，參數可以用一般指標 const Node *node，呼叫時傳 root.get()，往下走時用 node->left.get()。

height 和 inorder 用遞迴寫最自然：空樹（node == nullptr）是最簡單的情況，其他情況交給左右子樹處理。

提示 3：erase 怎麼「用子樹取代節點」？

erase 和 insert 一樣接收 std::unique_ptr<Node> &node。找到要刪的節點後，情況 1 只要一行：

node = std::move(node->right);

這一行會先把右子樹的擁有權從 node->right 拿出來，接到 node 這個位置上，然後自動 delete 原本的節點（這時它的 left、right 都已經是空的，所以不會連帶刪到子樹）。不需要、也不能寫 delete。

情況 3 不用真的搬動節點：只要把右子樹的最小值複製到 node->value，再呼叫 erase(node->right, 那個值) 就好。

如果不小心用到已經被 move 走的 unique_ptr（它已經是空的），就是在存取空指標。檢查的第一階段（Sanitizer）會報告 member access within null pointer of type 'Node'，並指出是哪一行。想看 heap 用量和有沒有洩漏，可以在終端機輸入：

run exercises\3-memory\19-unique-ptr-bst\main.cpp --mem --input exercises\3-memory\19-unique-ptr-bst\tests\01.in