Clone 模式在平衡二元樹與複雜資料結構中的深度應用

Clone 模式 (Prototype Pattern) 屬於建構型模式，核心意圖：「以原型實例指定建立物件的種類，並透過複製這些原型來建立新物件」。本文從基本實作切入，深入探討含循環參考、共享子物件等複雜結構的複製難題與解法。

一、基本介面與實作

class Prototype {
public:
    virtual ~Prototype() = default;
    virtual Prototype* clone() const = 0;
protected:
    Prototype() = default;
    Prototype(const Prototype&) = default;
};

class ConcretePrototype : public Prototype {
    Data datas_;
public:
    ConcretePrototype(const Data& d) : datas_(d) {}
    ConcretePrototype(const ConcretePrototype& other) : datas_(other.datas_) {}
    Prototype* clone() const override { return new ConcretePrototype(*this); }
};

二、兩大經典陷阱

1. 記憶體洩漏：clone() 回傳 new 物件，呼叫端若未接管即洩漏。
   → 解法：回傳智慧指標 (std::unique_ptr<Prototype> / std::shared_ptr<Prototype>)。
2. 遞迴複製爆炸：組合模式下，clone() 遞迴複製子物件；若存在循環參考 (如雙向鏈表、圖) 或共享子物件 (多父節點指向同一子節點)，會導致無限遞迴或重複複製。

三、解決循環參考：標記法

在每個節點加入 cloned 標記與 pclone 指標，記錄「已複製的對應新節點」。

class Node {
    Data data_;
    Node* next_;
    mutable bool cloned_ = false;
    mutable Node* pclone_ = nullptr;
public:
    Node(const Data& d, Node* n = nullptr) : data_(d), next_(n) {}
    Node* clone() const {
        if (cloned_) return pclone_;          // 已複製，直接回傳對應新節點
        cloned_ = true;
        Node* neo = new Node(data_);          // 複製自身資料
        pclone_ = neo;
        if (next_) neo->next_ = next_->clone(); // 遞迴複製下一個
        cloned_ = false;                      // 重置供下次 clone 使用
        return neo;
    }
};

此法適用於單向循環鏈表、樹狀結構含回指標等場景。

四、解決共享子物件：計數器法 (無需修改節點)

若不想汙染節點類別，可用靜態計數器 模擬「訪問世代」：

class Node {
    static int generation_;       // 全域世代計數
    int my_gen_ = 0;              // 節點被複製時的世代
    Node* my_clone_ = nullptr;    // 對應的新節點
    Data data_; Node* next_;
public:
    Node* clone() {
        if (my_gen_ == generation_) return my_clone_; // 本世代已複製
        my_gen_ = generation_;
        Node* neo = new Node(data_);
        my_clone_ = neo;
        if (next_) neo->next_ = next_->clone();
        return neo;
    }
    static Node* clone_for_call(Node* root) {
        ++generation_;            // 開啟新世代
        return root->clone();
    }
};
int Node::generation_ = 0;

優點：節點類別無須新增 cloned 欄位，執行緒不安全時需加鎖或改用 thread_local。

五、進階：深層複製與智慧指標的現代寫法

#include 
#include 

class Node {
    Data data_;
    std::shared_ptr next_;
public:
    Node(const Data& d) : data_(d) {}
    std::shared_ptr deep_clone() const {
        std::unordered_map> memo;
        return clone_impl(memo);
    }
private:
    std::shared_ptr clone_impl(
        std::unordered_map>& memo) const
    {
        auto it = memo.find(this);
        if (it != memo.end()) return it->second; // 循環/共享直接回傳
        auto neo = std::make_shared(data_);
        memo[this] = neo;                        // 先登記再遞迴，解決循環
        if (next_) neo->next_ = next_->clone_impl(memo);
        return neo;
    }
};

• 使用 std::shared_ptr 自動管理生命週期，消除記憶體洩漏。
• unordered_map 以原始節點位址為鍵，O(1) 查找已複製節點，完美處理循環與共享。
• 適用於任意圖狀結構 (AST、場景圖、網路拓樸等)。

六、在平衡二元樹 (AVL/Red-Black) 中的應用

樹節點通常無循環參考，但若需支援 持久化資料結構 (Persistent Data Structure)——即修改時保留舊版本——Clone 模式是核心：

std::shared_ptr insert(std::shared_ptr root, int key) {
    if (!root) return std::make_shared(key);
    auto neo = std::make_shared(*root); // 複製路徑上的節點
    if (key < neo->key) neo->left = insert(neo->left, key);
    else              neo->right = insert(neo->right, key);
    return rebalance(neo);
}

只複製從根到插入點的路徑 (O(log n) 節點)，其餘子樹共享，極大降低記憶體與時間開銷，是函數式程式語言與資料庫 MVCC 的常用技巧。

七、總結對照表

Clone 模式看似簡單，實則是處理物件圖複製的核心工具。掌握「標記法、世代計數、Hash Map 記錄、路徑複製」四大進階技巧，即可從容應對從單向鏈表到持久化平衡樹的各種複製挑戰。