今天來介紹五種Tree:
1.左偏樹(Leftist Tree)
2.通用樹(Generic Trees)
3.字典樹(Trie Tree)
4.線段樹 (Segment Tree)
5.區間樹 (Interval Tree)

左偏樹(Leftist Tree)

也稱為左堆(leftist heap)特別適用於實作優先權佇列（Priority Queue）。它的名稱來自於其特殊的性質，稱為「左偏性質」或「左傾性質」，這使得在執行合併操作時效能優於其他堆資料結構。

主要特點

1. 左偏性質：每個節點都滿足左子樹的零路徑長（null path length）大於或等於右子樹的零路徑長。這個性質確保了樹的左邊子樹比右邊子樹更深，因此被稱為「左偏」。
2. 優先權佇列：左偏樹常用於實作優先權佇列，其中每個節點具有一個優先權值，最小優先權值的節點位於樹的根節點。這使得提取最小值的操作非常高效，只需O(1)的時間複雜度。
3. 合併操作：最重要的操作之一是合併（Merge）操作，它用於將兩個左偏樹合併成一個新的左偏樹。合併操作遵循左偏性質，將較大的樹作為新樹的右子樹，然後遞迴合併。合併操作的時間複雜度通常是O(log N)，其中N是節點數量。
4. 插入和刪除操作：插入操作可以輕鬆地實現，只需建立包含一個節點的左偏樹，然後與現有樹合併。刪除操作通常是刪除最小值，它也可以通過提取最小值並將其子樹合併為一個新的左偏樹來實現。

基本操作

基本結構

首先，我們需要定義 Leftist Tree 節點的結構，包括節點值、左子樹、右子樹以及左偏值。

struct LeftistNode {
    int value;
    LeftistNode* left;
    LeftistNode* right;
    int dist;  // 左偏值，即左子樹的深度
    LeftistNode(int val) : value(val), left(nullptr), right(nullptr), dist(0) {}
};

插入（Insertion）

將一個新的節點插入到 Leftist Tree 中，通常插入操作可以簡單地視為將新節點當作一棵左偏樹，然後再進行合併操作。
操作的步驟如下：
a. 創建一個包含要插入的元素的左偏樹（可以視為只有一個節點的左偏樹）。
b. 將這個新的左偏樹與現有的 Leftist Tree 進行合併操作。

LeftistNode* insert(LeftistNode* root, int val) {
    LeftistNode* newNode = new LeftistNode(val);
    return merge(root, newNode);
}

刪除最小元素操作（Delete Min）

從 Leftist Tree 中刪除並返回具有最小優先級值的節點。
操作的步驟如下：
a. 找到具有最小優先級值的根節點，這通常是 Leftist Tree 的根節點。
b. 刪除這個根節點。
c. 合併根節點的左子樹和右子樹，得到新的 Leftist Tree。
d. 返回被刪除的節點作為最小值。

LeftistNode* deleteMin(LeftistNode* root) {
    if (!root) return nullptr;

    LeftistNode* leftChild = root->left;
    LeftistNode* rightChild = root->right;
    delete root;
    return merge(leftChild, rightChild);
}

合併（Merge）

合併操作是 Leftist Tree 最重要的操作之一，它用於將兩個 Leftist Trees 合併為一個新的 Leftist Tree。
操作的步驟如下：
a. 比較兩個 Leftist Trees 的根節點，將具有較小優先級值的節點設為新樹的根節點。
b. 將根節點的左子樹和右子樹分別合併，得到新的左子樹和右子樹。
c. 遞迴執行合併操作，直到確保左偏性質得以滿足。
d. 返回新的合併後的 Leftist Tree。

LeftistNode* merge(LeftistNode* a, LeftistNode* b) {
    if (!a) return b;
    if (!b) return a;

    // 確保 a 的值小於 b，如果不是，則交換 a 和 b
    if (a->value > b->value) {
        swap(a, b);
    }

    // 遞歸地合併 a 的右子樹和 b
    a->right = merge(a->right, b);

    // 更新左偏值，確保左子樹的左偏值不大於右子樹
    if (!a->left || a->left->dist < a->right->dist) {
        swap(a->left, a->right);
    }

    // 更新左偏值
    a->dist = (a->right ? a->right->dist + 1 : 0);
    return a;
}

優缺點

優點

1. 高效的合併操作：Leftist Tree 的最大優點是其高效的合併操作。合併兩個 Leftist Trees 的時間複雜度通常是 O(log N)，其中 N 是樹中的節點數量。這使得合併操作非常高效，特別適用於需要頻繁合併的情況，如合併多個優先級佇列。
2. 提取最小值高效：由於根節點總是包含最小值，因此提取最小值的操作效率高，只需要 O(1) 的時間複雜度。
3. 簡單的插入操作：插入新元素時，只需將其視為一個左偏樹，再與現有的 Leftist Tree 合併，因此插入操作相對簡單，時間複雜度通常是 O(log N)。
4. 左偏性質：左偏樹的左偏性質確保了左子樹的高度始終大於或等於右子樹的高度，這有助於保持樹的平衡性。

缺點

1. 優先級佇列限制：Leftist Tree 主要用於實現優先級佇列，而不適合用於其他一般性的堆操作，例如修改特定元素的優先級值。
2. 部分操作效能較差：儘管合併和提取最小值操作非常高效，但其他操作，如修改元素的優先級值，可能效能較差。這些操作可能需要搜索和調整整個樹結構，導致較高的時間複雜度。
3. 不適用於所有應用：Leftist Tree 不是適用於所有問題的最佳解決方案。對於某些應用場景，其他資料結構，如二元堆（Binary Heap）或斐波那契堆（Fibonacci Heap），可能具有更優越的效能。

總結來說，Leftist Tree 在合併操作和提取最小值操作上表現出色，特別適用於需要高效處理優先級佇列的應用。然而，它的效能在其他操作上可能較差，並且不適用於所有應用情境。選擇使用 Leftist Tree 還是其他資料結構應取決於特定問題的需求和性能要求。

通用樹(Generic Trees)

又稱N元樹(N-ary Tree)，是一種樹狀資料結構，與二元樹不同，每個節點可以擁有多個子節點，而不僅僅是兩個。在N-ary Tree中，每個節點最多可以有N個子節點，其中N可以是任意正整數。這種資料結構具有多個有趣的特點和廣泛的應用。

特點

1. 多子節點： 每個N-ary Tree的節點可以擁有多個子節點，這使得它更能靈活地表示和組織資料。這與二元樹不同，二元樹中每個節點最多只能有兩個子節點。
2. 動態結構： N-ary Tree的結構是動態的，節點的數量和子節點的數量都可以根據需求動態增長，這使得它適用於多種不同的應用場景。
3. 多層次結構： 這種樹狀結構非常適合表示多層次結構的資料，例如組織結構、家譜、文件系統等。每個節點代表一個層次結構中的元素，並且可以有多個子元素，這使得層次性資料的表示變得自然而簡單。
4. 靈活的遍歷： 對N-ary Tree的遍歷可以是深度優先遍歷（例如前序、中序)

結構寫法

使用動態數組來儲存孩子的地址。我們可以隨機存取任何孩子的地址，向量的大小也不固定。

class TreeNode {
public:
    int val;  // 節點的數值
    std::vector<TreeNode*> children;  // 子節點的指針陣列

    TreeNode(int value) : val(value) {}
};

基本操作

1. 插入節點（Insertion）： 插入操作用於將新節點添加到樹中。要執行插入操作，首先要找到要插入的目標節點，然後將新節點添加為其子節點之一。
2. 刪除節點（Deletion）： 刪除操作用於從樹中刪除一個特定的節點。刪除節點時需要注意，必須同時處理該節點的子節點，以確保不破壞樹的結構。
3. 查找節點（Search）： 查找操作用於在N-ary Tree中查找特定的節點。通常使用深度優先搜索（DFS）或廣度優先搜索（BFS）等算法來實現查找操作。
4. 遍歷樹（Traversal）： 遍歷樹是訪問樹中所有節點的操作。常見的遍歷方式包括前序遍歷、中序遍歷、後序遍歷和層序遍歷。不同的遍歷方式用於不同的應用場景。
5. 計算高度（Height）： 計算樹的高度是一個常見的操作，它表示從根節點到最深葉節點的最長路徑上的節點數量。計算高度通常使用遞迴算法。
6. 合併（Merging）： 如果有兩個N-ary Trees，合併操作允許將它們合併成一個新的N-ary Tree。合併操作需要考慮如何合併根節點以及子樹的組合。
7. 分割（Splitting）： 分割操作與合併相反，它將一個N-ary Tree分成兩個或多個子樹。
8. 查詢（Query）： 查詢操作允許根據特定條件或屬性在N-ary Tree中查找節點。例如，查找滿足某個條件的所有節點。

優缺點

優點：

1. 靈活性： N-ary Tree非常靈活，每個節點可以擁有多個子節點，這使得它能夠有效地表示多層次結構的資訊，如組織結構、家譜、文件系統等。
2. 自然表示： 對於具有多層次結構的資料，N-ary Tree是一種自然的表示方式，容易理解和操作。這使得它在數據建模方面非常有用。
3. 動態結構： N-ary Tree的結構是動態的，節點的數量和子節點的數量都可以根據需求動態增長，這使得它適用於多種不同的應用場景。
4. 多應用性： N-ary Tree在多個領域都有廣泛的應用，包括檔案系統表示、XML和HTML解析、資料庫索引、組織結構等。

缺點

1. 空間需求： N-ary Tree通常需要比二叉樹更多的記憶體空間，因為每個節點可以擁有多個子節點，這可能會導致更大的記憶體使用量。
2. 尋找效率： 在N-ary Tree中查找特定節點可能需要遍歷多個子節點，特別是當樹的高度較深時。這可能會導致查找操作的效率較低。
3. 平衡性： 與二叉樹相比，N-ary Tree不具備平衡性質，可能導致不平衡的樹結構，進而影響某些操作的效能。
4. 實作複雜性： 與二叉樹相比，實作N-ary Tree的操作可能更複雜，特別是在插入和刪除節點時，需要處理多個子節點的情況。

應用

以下是一些常見的N-ary Tree的應用場景：

1. 檔案系統表示： N-ary Tree常用於表示檔案系統的層次結構，其中每個資料夾可以包含多個子資料夾和檔案。
2. XML和HTML解析： XML和HTML文件可以使用N-ary Tree來表示其層次結構，其中標籤和元素是樹的節點。
3. 資料庫索引： N-ary Tree可以用作資料庫索引結構，其中每個節點代表一個索引項，並且可以有多個子索引。
4. 組織結構： 用於表示組織結構，包括公司組織、學術機構結構等。
5. 家譜： 用於表示家族樹狀結構，包括家族成員的關係。

與Binary Tree之間的比較

1. 子節點數量
   • N-ary Tree：每個節點可以擁有多個子節點，子節點數量不受限制，通常用N表示最大子節點數。
   • Binary Tree：每個節點最多只能有兩個子節點，一個左子節點和一個右子節點。
2. 結構靈活性
   • N-ary Tree：由於子節點數量不受限制，具有更大的靈活性，可以更自然地表示多層次結構。
   • Binary Tree：結構相對較固定，每個節點只有兩個分支，不如N-ary Tree靈活。
3. 空間需求
   • N-ary Tree：通常需要更多的記憶體空間，因為每個節點可以擁有多個子節點。
   • Binary Tree：相對節約記憶體，因為每個節點最多只有兩個子節點。
4. 尋找效率
   • N-ary Tree：查找節點時，可能需要遍歷多個子節點，特別是在樹的高度較深時，查找效率較低。
   • Binary Tree：查找效率通常比N-ary Tree高，因為每個節點最多只有兩個子節點，樹的高度相對較低。
5. 平衡性
   • N-ary Tree：不具備平衡性質，可能導致不平衡的樹結構，影響某些操作的效能。
   • Binary Tree：可以實現平衡二叉樹，例如AVL樹和紅黑樹，這些平衡二叉樹保證操作的時間複雜度。
6. 實作複雜性
   • N-ary Tree：在實作時，需要處理多個子節點的情況，可能複雜一些。
   • Binary Tree：相對較容易實作，因為每個節點只有兩個子節點。

如果需要表示多層次結構的資料，N-ary Tree可能更適合。如果需要高效的查找操作和平衡性，則可能更適合使用Binary Tree，尤其是平衡二叉樹實現。

字典樹(Trie Tree)

也被稱為字典樹（Dictionary Tree）或前綴樹（Prefix Tree），是一種獨特的樹狀資料結構，專門用於高效地儲存、檢索和查找以字串形式表示的資訊。它的名稱"trie"源自英文單字"retrieval"的倒寫，強調了它在字串搜尋方面的優越性。

字典樹（Trie）是一種特殊的樹狀數據結構，有時也稱為單詞搜尋樹，類似於一本強大的字典，能夠迅速地插入、查找和處理字符串數據，尤其在處理大量字符串的情況下表現出色。

Trie最引人注目的特點在於它精妙地利用了字串的特性，將每個字串的共同前綴作為儲存和檢索的基礎，這樣可以節省儲存空間並加速檢索操作。 Trie以樹狀結構表示，每個節點（Node）代表一個字母（或字母的一部分）。整棵樹的高度取決於最長的字串的長度，再加上根節點。

當我們從根節點開始沿著樹的分支向下遍歷時，每個節點都代表了一個可能的字串。不同於一般的二元樹，Trie不僅限於葉子節點才包含字符串信息，每個節點都可以表示一個或多個字符串的共同前綴，這使得我們既能節省內存，又能迅速查找字符串。

Trie Tree的優勢體現在前綴匹配方面，它能夠迅速檢索帶有特定前綴的字串，這對於字典、自動完成、拼字檢查以及相似字串的查找非常重要。在Trie中，每個節點最多有字母表大小的子節點，這使得它非常適合處理字串資料。

Trie Tree是一種強大且高效的資料結構，特別適用於處理字串資料。它在字典、搜尋建議、自動完成、拼字檢查以及其他與字串相關的應用領域中具有廣泛的應用。需要注意的是，雖然Trie Tree非常強大，但在某些情況下可能會佔用較多的記憶體。為了優化記憶體使用，可以使用一些技巧，如壓縮Trie或Radix Tree等。

主要特點

1.高效的字串檢索：Trie Tree 以其出色的前綴匹配能力而著稱，能夠快速查找帶有特定前綴的字串，適用於字典、搜尋建議和拼字檢查等應用程式。
2.儲存共同前綴：Trie Tree 利用字串的共同前綴來儲存數據，這有助於節省儲存空間，因為共同前綴只需儲存一次。
3.多元樹結構：Trie Tree 是一種多元樹，每個節點可以有多個子節點，代表不同的字元或字元的一部分。
4.根節點：Trie Tree 的根節點代表空字串或空前綴，是整棵樹的起點。
5.高度：Trie Tree 的高度取決於最長的字串的長度，這有助於快速找到和插入。
6.高效率的插入和刪除操作：將字串插入 Trie Tree 是相對簡單的操作，刪除操作也可以執行，特別是需要刪除不再需要的字串時。

基本操作

結構

首先，定義 Trie Tree 節點結構，通常包括子節點指針數組、是否為結束節點的標記等。

struct TrieNode {
    TrieNode* children[26]; // 子節點，假定處理小寫字母
    bool isEndOfWord;       // 是否是字串結尾
    TrieNode() {
        memset(children, 0, sizeof(children));
        isEndOfWord = false;
    }
};

插入（Insert）

插入操作用於將一個字串插入 Trie Tree 中。我們遍歷字串的每個字符，從 Trie Tree 的根節點開始，依次插入字符對應的節點。如果某個節點不存在，則創建一個新的節點。最後，在字串的最後一個字符節點上設置結尾標誌。

void insert(TrieNode* root, string word) {
    TrieNode* node = root;
    for (char ch : word) {
        int index = ch - 'a'; // 假定處理小寫字母
        if (!node->children[index]) {
            node->children[index] = new TrieNode();
        }
        node = node->children[index];
    }
    node->isEndOfWord = true;
}

搜尋字串（Search）

從根節點開始，依照字串的字元順序依序遍歷Trie。如果在遍歷過程中遇到不存在的字元節點，或是最後一個字元節點沒有標記字串結束的標誌，就表示字串不存在於Trie中。

bool search(TrieNode* root, string word) {
    TrieNode* node = root;
    for (char ch : word) {
        int index = ch - 'a'; // 假定處理小寫字母
        if (!node->children[index]) {
            return false;
        }
        node = node->children[index];
    }
    return node->isEndOfWord;
}

刪除（Delete）

首先，需要執行查找操作以確定字串是否存在於Trie中。然後，從根節點開始，按照字串的字元順序依次遍歷Trie，找到字串的最後一個字元節點，並將其結束標誌清除。如果這個節點沒有其他子節點，可以將其從Trie中刪除。接著，遞歸地檢查父節點，如果發現沒有其他子節點，也可以刪除父節點，以此類推，直到不再有可以刪除的節點。

bool deleteWord(TrieNode* root, string word, int depth) {
    if (!root) {
        return false;
    }
    if (depth == word.length()) {
        if (root->isEndOfWord) {
            root->isEndOfWord = false;
            return true;
        }
        return false;
    }
    int index = word[depth] - 'a'; // 假定處理小寫字母
    bool canDelete = deleteWord(root->children[index], word, depth + 1);
    if (canDelete) {
        delete root->children[index];
        root->children[index] = nullptr;
        return !root->isEndOfWord && isEmptyNode(root);
    }
    return false;
}

bool isEmptyNode(TrieNode* node) {
    for (int i = 0; i < 26; ++i) {
        if (node->children[i]) {
            return false;
        }
    }
    return true;
}

前綴匹配（Prefix Matching）

1. 遍歷以特定前綴為起點的 Trie Tree 子樹：

首先，我們需要確定 Trie Tree 中是否存在以特定前綴為起點的子樹。這可以通過查詢 Trie Tree 中是否存在該前綴的最後一個字符所對應的節點來實現。如果該節點存在，則表示該前綴存在於 Trie Tree 中。

bool isPrefixExists(TrieNode* root, string prefix) {
    TrieNode* node = root;
    for (char ch : prefix) {
        int index = ch - 'a'; // 假定處理小寫字母
        if (!node->children[index]) {
            return false; // 前綴不存在
        }
        node = node->children[index];
    }
    return true; // 前綴存在
}

2. 遍歷以特定前綴為起點的所有字串
   一旦確定前綴存在於 Trie Tree 中，我們可以遍歷以該前綴為起點的所有字串。這可以通過深度優先搜索（DFS）方法實現。

void findAllWithPrefix(TrieNode* node, string currentWord, vector<string>& result) {
    if (!node) {
        return;
    }
    if (node->isEndOfWord) {
        result.push_back(currentWord);
    }
    for (int i = 0; i < 26; ++i) { // 假定處理小寫字母
        if (node->children[i]) {
            char ch = 'a' + i;
            findAllWithPrefix(node->children[i], currentWord + ch, result);
        }
    }
}

vector<string> findAllWordsWithPrefix(TrieNode* root, string prefix) {
    vector<string> result;
    TrieNode* node = root;
    for (char ch : prefix) {
        int index = ch - 'a'; // 假定處理小寫字母
        if (!node->children[index]) {
            return result; // 前綴不存在，返回空列表
        }
        node = node->children[index];
    }
    // 遍歷以前綴為起點的所有字串
    findAllWithPrefix(node, prefix, result);
    return result;
}

遍歷（Traversal）

遍歷操作可以用於取得Trie中儲存的所有字串。通常使用深度優先搜尋或廣度優先搜尋來遍歷Trie，以檢索或列舉所有字串。

Trie是一種強大的資料結構，特別適用於處理大量字串資料和實作字串搜尋相關的功能。它常用於搜尋引擎、拼字檢查、自動完成、字典、路由表和許多其他應用中。理解Trie的基本原理和操作可以幫助解決與字串相關的問題。

與N-ary Tree 的比較

需要注意的是，Trie Tree 主要用於處理字串數據，特別擅長在字典、搜尋建議和拼字檢查等應用程式中，而 N-ary Tree 可以更通用地用於多種資料類型和領域。兩者都是多元樹結構，但 Trie Tree 通常在節點分支數和字串處理方面有一些特殊化的優勢。在選擇使用哪種資料結構時，應根據特定的應用需求和資料類型來決定。

三元搜尋樹(Ternary Search Tree)

三元搜尋樹是一種特殊的字典樹
三元搜尋樹的表示：
與 trie（標準）資料結構的每個節點包含 26 個子節點指標不同，三元搜尋樹中的每個節點僅包含 3 個指標：

1. left指標指向值小於目前節點中值的節點。
2. equal指標指向其值等於目前節點中的值的節點。
3. 右指標指向值大於目前節點中值的節點。
   除了上述三個指標之外，每個節點還有一個欄位來指示資料（字典情況下為字元）和另一個欄位來標記字串的結尾。

主要特點

結構

Ternary Search Tree的每個節點代表一個字元，不同於BST的二元性質。每個節點都有三個子節點，通常稱為"左"、"中"和"右"子節點，代表當前字元小於、等於和大於節點所代表的字元情況。這種三分支的結構有助於有效地處理字串相關操作。

// 定義 Ternary Search Tree 的節點結構
struct TernaryNode {
    char data;               // 節點的字元值
    bool isEndOfWord;        // 標記是否為字串結尾
    TernaryNode* left;       // 左子樹（小於當前字元的節點）
    TernaryNode* middle;     // 中間子樹（等於當前字元的節點）
    TernaryNode* right;      // 右子樹（大於當前字元的節點）
    
    TernaryNode(char c) {
        data = c;
        isEndOfWord = false;
        left = middle = right = nullptr;
    }
};

自平衡性

Ternary Search Tree通常具有自平衡性質，確保樹的高度相對較小，這有助於保持高效的查找性能。在插入新的字串時，樹會自動調整以維護平衡。

記憶體效率

相對於其他資料結構如哈希表，Ternary Search Tree具有更好的記憶體效率，因為它不需要為每個鍵分配記憶體，而是利用樹的結構儲存字串。

基本操作

插入操作

插入新的字串是一個遞歸的過程，我們從樹的根節點開始，根據當前字元的大小關係，選擇向左、中間或右子樹分支。如果節點不存在，則創建一個新節點。在插入過程中，我們不僅要插入字元，還要設置isEnd標誌以指示字串的結尾。

TSTNode* insert(TSTNode* root, const char* word) {
    char currentChar = *word;
    if (!root) {
        root = new TSTNode;
        root->data = currentChar;
    }
    
    if (currentChar < root->data) {
        root->left = insert(root->left, word);
    } else if (currentChar > root->data) {
        root->right = insert(root->right, word);
    } else {
        if (*word == '\0') {
            root->isEnd = true; // 標記字串結尾
        } else {
            root->mid = insert(root->mid, word + 1);
        }
    }
    
    return root;
}

搜尋操作

搜尋操作也是一個遞歸過程，我們根據當前字元的大小關係，選擇向左、中間或右子樹分支，直到找到完全匹配的字串或查詢不到匹配的字串。

bool search(TSTNode* root, const char* word) {
    char currentChar = *word;
    if (!root) {
        return false;
    }
    
    if (currentChar < root->data) {
        return search(root->left, word);
    } else if (currentChar > root->data) {
        return search(root->right, word);
    } else {
        if (*word == '\0' && root->isEnd) {
            return true; // 找到完全匹配的字串
        } else {
            return search(root->mid, word + 1);
        }
    }
}

前綴搜尋

沿著"中"子樹移動，直到找到前綴匹配的位置，然後繼續搜索子樹。

void prefixSearch(TSTNode* root, const char* prefix, std::string currentWord) {
    if (!root) {
        return;
    }
    
    char currentChar = *prefix;
    
    if (currentChar < root->data) {
        prefixSearch(root->left, prefix, currentWord);
    } else if (currentChar > root->data) {
        prefixSearch(root->right, prefix, currentWord);
    } else {
        if (*prefix == '\0') {
            // 找到前綴匹配，繼續搜索子樹
            traverse(root->mid, currentWord + root->data);
        } else {
            prefixSearch(root->mid, prefix + 1, currentWord + root->data);
        }
    }
}

優缺點

優點

• 和前綴搜尋操作： Ternary Search Tree非常適合執行搜尋和前綴搜尋操作，特別是在字串相關的應用中。由於它的結構，可以快速地找到與目標字串匹配的內容，這對於自動完成、拼寫檢查和模糊搜尋等應用非常有用。
• 節點的自平衡性： Ternary Search Tree通常具有自平衡性質，確保樹的高度相對較小，因此查找性能良好。
• 記憶體效率： 相對於其他資料結構（如哈希表），Ternary Search Tree具有較好的記憶體效率。它僅在需要時為每個字串分配記憶體，不需要預先分配大量的空間。
• 支援範圍搜索： Ternary Search Tree可以支援查詢一定範圍內的所有字串，這對某些應用（例如搜索引擎）非常有用。

缺點

• 消耗： Ternary Search Tree的結構相對複雜，每個節點都需要多個指針（通常是3個），這可能導致較高的空間消耗，尤其是當儲存大量字串時。
• 樹的建構難度： 構建Ternary Search Tree需要遞歸操作，這可能導致對於大型字典的初始化較慢。
• 不適用於所有情況： 雖然Ternary Search Tree在字串相關的操作上非常高效，但對於一般的數值型資料或其他資料結構可能不如其他資料結構（如二元搜尋樹或散列表）高效。

應用

1. 三元搜尋樹對於「給定一個單詞，在字典中查找下一個單字（近鄰查找）」或「尋找以9342 開頭的所有電話號碼」或「在網路瀏覽器中鍵入幾個起始字元會顯示所有網站」等查詢非常有效帶有此前綴的名稱「（自動完成功能）」。
   2.用於拼字檢查：三元搜尋樹可以用作字典來儲存所有單字。在編輯器中輸入單字後，可以在三元搜尋樹中並行搜尋該單字以檢查拼字是否正確。

總的來說，Ternary Search Tree是一個強大的字串相關操作工具，特別適用於需要快速查詢、前綴搜尋和模糊搜尋的情況。然而，它的空間需求較高，且不適用於所有類型的資料，因此在選擇使用它時需要根據應用需求來考慮其優缺點。

線段樹 (Segment Tree)

線段樹（Segment Tree 或 Seg Tree）是一種獨特的二叉搜索樹，它專門用於儲存和處理關於「線段」或「區間」的性質。儘管這兩個術語有時會與另一種資料結構，即區間樹（Interval Tree）混淆使用，但線段樹和區間樹在本質上有重要區別。線段樹的主要應用包括查詢某區間被多少個線段覆蓋、計算區間內的極值等，並且能夠高效地維護這些性質，即使在資料集經常更動的情況下。

線段樹的核心概念是「分割」。普通的二叉搜索樹（BST）根據數據值進行分割，而線段樹則專注於處理線段。它能夠有效地分割和合併線段，使其能夠執行一些普通 BST 難以實現的操作。此外，線段樹的時間和空間複雜度也與普通 BST 不同。

主要應用

Segment Tree（線段樹）是一種用於高效處理區間查詢問題的資料結構，主要應用於以下情境：

1. 區間查詢：尋找給定區間內的某個數值或計算區間內的某個數值屬性。

2. 單點更新：對資料集中的一個元素的值進行更新。

特性

線段樹（Segment Tree）具有以下關鍵特性：

1. 分治性質：線段樹是一種分治資料結構，它將一個陣列分割為一組相鄰的區間，並在每個節點中維護這些區間的匯總資訊。這種分治性質使得線段樹非常適合處理區間查詢問題。
2. 完全二元樹結構：通常，線段樹是一個完全二元樹，這表示它的每一層（除了可能的最後一層）都是滿的。這樣的結構確保了線段樹的高度是對數級別，因此區間查詢和更新操作的時間複雜度為 O(log N)，其中 N 是數組的大小。
3. 區間表示：每個線段樹節點代表原始陣列中的一個區間。根節點表示整個數組，而每個子節點表示數組的子區間。這種區間表示方式使得線段樹能夠有效地處理區間查詢操作，例如區間最小值、區間總和等。
4. 匯總資訊：線段樹的每個節點儲存了其所代表區間的匯總資訊，這可以是區間內元素的最小值、最大值、總和等，具體取決於問題需求。這些匯總資訊使得線段樹能夠快速執行區間查詢操作。
5. 單點更新：線段樹支援單點更新操作，這意味著您可以有效地修改原始數組中的一個元素，並相應地更新整個線段樹中的相關節點以反映此更改。
6. 高效的時間複雜度：由於線段樹的高度是對數級別，所以區間查詢和單點更新操作的時間複雜度均為 O(log N)。這使得線段樹成為處理大規模區間操作問題的有效工具。
7. 可擴展性：線段樹可以輕鬆擴展以應對不同類型的問題，只需定義適當的節點匯總資訊和查詢操作即可。這使得它適用於各種不同的應用場景。

結構特徵

線段樹（Segment Tree）的結構特徵如下：

1. 節點表示區間：線段樹的每個節點表示一個原始陣列中的區間。根節點表示整個數組，而每個子節點表示數組的一個子區間。這些區間按照一種自頂向下的方式遞歸劃分。
2. 根節點包含全範圍：根節點包含整個原始陣列的範圍，這個範圍通常由左邊界和右邊界表示。
3. 子節點的區間劃分：每個節點的子節點依照中間位置將其區間分成兩半。例如，如果一個節點的區間範圍是[l, r]，那麼其左子節點的區間是[l, (l+r)/2]，右子節點的區間是[(l+r)/2+ 1, r]。
4. 葉子節點：線段樹的葉子節點對應於原始數組中的單一元素，因此葉子節點的區間大小為 1。
5. 樹高度：線段樹的高度通常為 log2(N)，其中 N 是原始陣列的大小。這是因為每個節點都會將其區間劃分成兩半，使得樹的高度以對數等級成長。
6. 儲存匯總資訊：每個節點儲存了其所代表的區間範圍內的某種匯總信息，例如最小值、最大值、總和等，這個匯總資訊用於支援區間查詢操作。
7. 完全二元樹結構：雖然線段樹不一定要求是完全二元樹，但通常為了保持平衡性，會將不滿的葉子節點補充成完全二元樹，或使用陣列來表示線段樹。

基本操作

定義線段樹節點結構

struct SegmentTreeNode {
    int start, end;
    int sum; // 存儲區間的總和，可以根據需要更改為其他操作
    SegmentTreeNode* left;
    SegmentTreeNode* right;
    
    SegmentTreeNode(int s, int e) : start(s), end(e), sum(0), left(nullptr), right(nullptr) {}
};

建立線段樹

• 首先，確定原始數組的大小（通常是2的冪，以確保線段樹的平衡性）。
• 建立一個陣列來表示線段樹，陣列大小為原始陣列大小的4倍，以容納線段樹的節點。
• 使用遞歸方式，從根節點開始將原始陣列分割成子區間，建立整個線段樹。

// 建立線段樹
void build(int node, int left, int right) {
    if (left == right) {
        // 叶子节点，将原始数组的值存储到线段树中
        segmentTree[node] = arr[left];
    } else {
        int mid = (left + right) / 2;
        // 递归构建左子树和右子树
        build(2 * node, left, mid);
        build(2 * node + 1, mid + 1, right);
        // 在此处合并左右子树的信息（例如，求和、找最大值等）
        segmentTree[node] = merge(segmentTree[2 * node], segmentTree[2 * node + 1]);
    }
}

查詢操作

• 要查詢一個區間 [L, R] 的信息，從根節點開始，遞歸地檢查每個節點的區間範圍與待查詢區間的關係。
• 如果待查詢區間完全包含了目前節點的區間範圍，則直接傳回該節點儲存的資訊。
• 否則，繼續向下遞歸查詢左子樹和右子樹。

// 查詢操作
int query(int node, int left, int right, int L, int R) {
    if (R < left || L > right) {
        // 待查詢區間與當前節點區間無交集
        return 0;  // 或其他適當的初始值，視具體問題而定
    } else if (L <= left && right <= R) {
        // 當前節點區間完全包含在待查詢區間內
        return segmentTree[node];
    } else {
        int mid = (left + right) / 2;
        // 否則，分別查詢左子樹和右子樹
        int leftResult = query(2 * node, left, mid, L, R);
        int rightResult = query(2 * node + 1, mid + 1, right, L, R);
        // 在此處合併左右子樹的結果（例如，求和、找最大值等）
        return merge(leftResult, rightResult);
    }
}

更新操作

若要更新原始陣列中的某個元素，請先在線段樹中找到對應的葉子節點。
更新葉子節點的值，並逐級向上更新父節點，以確保線段樹的資訊仍然有效。

// 更新操作
void update(int node, int left, int right, int index, int newValue) {
    if (left == right) {
        // 找到叶子节点，更新其值
        segmentTree[node] = newValue;
    } else {
        int mid = (left + right) / 2;
        if (index <= mid) {
            // 如果要更新的元素在左子树中
            update(2 * node, left, mid, index, newValue);
        } else {
            // 如果要更新的元素在右子树中
            update(2 * node + 1, mid + 1, right, index, newValue);
        }
        // 在此處合併左右子樹的信息（例如，求和、找最大值等）
        segmentTree[node] = merge(segmentTree[2 * node], segmentTree[2 * node + 1]);
    }
}

優缺點

優點

• 高效率的區間查詢：Segment Tree 能夠以 O(log N) 的時間複雜度執行區間查詢操作，這使得它非常適用於需要頻繁進行區間查詢的問題，如區間最小值、區間和、區間最大值等。
• 單點更新：Segment Tree 支援單點更新操作，即可以有效地修改原始數組中的一個元素，並在需要時更新整個 Segment Tree 中的相關節點，以確保資訊的準確性。
• 可擴展性：Segment Tree 可以輕鬆擴展以適應不同類型的問題，只需適當定義節點的總結資訊和查詢操作。這使得它在解決多種問題時非常靈活。
• 處理靜態資料集：對於不經常變更的資料集，Segment Tree 是一個非常有效的選擇，因為它在建置之後能夠提供快速的查詢操作，而且更新操作的次數較少。

缺點

• 佔用空間：Segment Tree 在某些情況下可能佔用大量內存，尤其是對於大型原始數組。每個節點都需要額外的空間來儲存總結訊息，因此在處理大規模資料時可能會導致記憶體佔用問題。
• 建置時間開銷：建置 Segment Tree 的過程需要 O(N) 的時間，其中 N 是原始陣列的大小。對於非常大的資料集，建置時間可能會較長。
• 不適用於動態資料集：如果資料集經常變化，即使是單點更新操作也可能導致效能下降。因為每次更新都需要重新建構相關節點，而這可能需要較長的時間。

Segment Tree 是一個強大的資料結構，適用於解決多種區間查詢問題。但它也有一些限制，特別是在記憶體佔用和資料集頻繁變化的情況下。在選擇使用 Segment Tree 時，需要權衡其優點和缺點，並考慮問題的特定要求。

區間樹 (Interval Tree)

Interval Tree（區間樹）是一種用於處理區間重疊和查詢相關問題的樹狀資料結構。它主要用於儲存和檢索一維區間的資料，並提供有效的方法來解決許多與區間有關的問題，包括區間查詢、重疊區間檢測、日程安排和時間表問題等。

主要特點

1. 結構： Interval Tree的結構類似於二叉搜索樹（BST），但每個節點代表一個區間，通常由左邊界和右邊界定義。此外，每個節點可能包含其他與區間相關的資訊，如最大值、最小值或區間的屬性。
2. 建置： Interval Tree的建置通常是一個遞歸的過程。根節點表示包含所有區間的範圍，然後將區間分為左子樹和右子樹，並將子區間插入對應的子樹中。這確保了樹的平衡性。

主要操作

定義結構

首先，我們需要定義Interval Tree的結構。通常，每個節點都包含以下信息：

struct Interval {
    int low;    // 區間的左端點
    int high;   // 區間的右端點
    // 其他與區間相關的資訊
};

struct IntervalTreeNode {
    Interval interval;  // 節點所代表的區間
    int maxHigh;        // 子樹中的最大右端點
    IntervalTreeNode* left;
    IntervalTreeNode* right;
};

建立

建立Interval Tree的過程通常是遞迴的。我們可以按照以下步驟來建立：

1. 選擇一個根節點，通常是根據區間中點的值選擇。
2. 將區間分為左子樹和右子樹，分別包含小於中點值和大於中點值的區間。
3. 遞迴建立左子樹和右子樹。

IntervalTreeNode* buildIntervalTree(vector<Interval>& intervals) {
    if (intervals.empty()) {
        return nullptr;
    }

    // 找到區間中點
    int mid = intervals.size() / 2;
    
    // 根據中點建立根節點
    IntervalTreeNode* root = new IntervalTreeNode;
    root->interval = intervals[mid];
    
    // 分割區間，遞迴建立左子樹和右子樹
    vector<Interval> leftIntervals(intervals.begin(), intervals.begin() + mid);
    vector<Interval> rightIntervals(intervals.begin() + mid + 1, intervals.end());
    
    root->left = buildIntervalTree(leftIntervals);
    root->right = buildIntervalTree(rightIntervals);

    // 更新子樹中的最大右端點
    root->maxHigh = max(root->interval.high, max(root->left ? root->left->maxHigh : INT_MIN, root->right ? root->right->maxHigh : INT_MIN));

    return root;
}

查詢

Interval Tree的主要功能是執行區間查詢。給定一個查詢區間，Interval Tree可以有效地找到與該區間重疊的所有區間。這可以幫助解決許多與時間區間、日程安排和資料篩選相關的問題。

vector<Interval> searchIntervalTree(IntervalTreeNode* root, Interval& queryInterval) {
    vector<Interval> result;

    if (root == nullptr) {
        return result;
    }

    // 如果查詢區間與根節點的區間重疊，則將根節點加入結果
    if (doOverlap(root->interval, queryInterval)) {
        result.push_back(root->interval);
    }

    // 如果左子樹中的最大右端點大於查詢區間的左端點，則遞迴查詢左子樹
    if (root->left && root->left->maxHigh >= queryInterval.low) {
        vector<Interval> leftResult = searchIntervalTree(root->left, queryInterval);
        result.insert(result.end(), leftResult.begin(), leftResult.end());
    }

    // 遞迴查詢右子樹
    vector<Interval> rightResult = searchIntervalTree(root->right, queryInterval);
    result.insert(result.end(), rightResult.begin(), rightResult.end());

    return result;
}

插入

插入操作用於將一個新的區間插入到Interval Tree中，並保持樹的平衡性。以下是插入操作的步驟解釋：

• 從根節點開始，遞歸地選擇適當的子樹（左子樹或右子樹）以插入新的區間。插入過程中，我們需要根據區間的左邊界或右邊界來決定是進入左子樹還是右子樹。
• 將新區間插入到選定的子樹中。如果新區間重疊了現有區間，則可能需要進行合併操作。
• 確保Interval Tree保持平衡，可以使用旋轉操作進行平衡調整。

// 插入操作
Node* insert(Node* root, Interval new_interval) {
    if (root == nullptr) {
        return new Node(new_interval);
    }

    // 更新子樹的最大結束點
    if (new_interval.end > root->max_end) {
        root->max_end = new_interval.end;
    }

    // 遞迴插入左子樹或右子樹
    if (new_interval.start < root->interval.start) {
        root->left = insert(root->left, new_interval);
    } else {
        root->right = insert(root->right, new_interval);
    }

    return root;
}

刪除

刪除操作允許您從Interval Tree中移除一個指定的區間

IntervalTreeNode* deleteInterval(IntervalTreeNode* root, Interval target) {
    if (root == nullptr) {
        return root;
    }

    // 遞迴地搜尋要刪除的區間
    if (target.low < root->interval.low) {
        root->left = deleteInterval(root->left, target);
    } else if (target.low > root->interval.low) {
        root->right = deleteInterval(root->right, target);
    } else {
        // 找到要刪除的區間
        if (root->left == nullptr) {
            IntervalTreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            IntervalTreeNode* temp = root->left;
            delete root;
            return temp;
        }

        // 如果有兩個子節點，找到右子樹的最小節點
        IntervalTreeNode* minValueNode = root->right;
        while (minValueNode->left != nullptr) {
            minValueNode = minValueNode->left;
        }

        // 將右子樹的最小節點複製到當前節點
        root->interval = minValueNode->interval;

        // 刪除右子樹的最小節點
        root->right = deleteInterval(root->right, minValueNode->interval);
    }

    // 更新maxHigh
    if (root != nullptr) {
        root->maxHigh = max(root->interval.high, max(
            (root->left != nullptr) ? root->left->maxHigh : INT_MIN,
            (root->right != nullptr) ? root->right->maxHigh : INT_MIN
        ));
    }

    return root;
}

重疊檢測

Interval Tree可用於檢測新插入的區間是否與現有區間重疊。這可以避免插入重複的區間。

// 檢查兩個區間是否重疊
bool isOverlap(Interval a, Interval b) {
    return (a.low <= b.high && b.low <= a.high);
}

// 在Interval Tree中查找重疊的區間
void findOverlap(IntervalTreeNode* root, Interval interval) {
    if (root == nullptr) 
        return;

    // 檢查根節點是否重疊
    if (isOverlap(root->interval, interval)) {
        std::cout << "重疊區間：[" << root->interval.low << ", " << root->interval.high << "]" << std::endl;
    }

    // 如果左子樹存在且其最大右端點大於查詢區間的左端點，則可能有重疊
    if (root->left != nullptr && root->left->maxHigh >= interval.low) {
        findOverlap(root->left, interval);
    }

    // 同理，如果右子樹存在且其最小左端點小於查詢區間的右端點，則可能有重疊
    if (root->right != nullptr && root->right->interval.low <= interval.high) {
        findOverlap(root->right, interval);
    }
}

優缺點

優點

• 高效的區間查詢：Interval Tree具有高效的查詢操作，可以快速找到與給定查詢區間重疊的所有區間。這使得它適用於解決許多需要區間查詢的問題，如日程管理、時間表問題、重疊檢測等。
• 高效的插入和刪除：Interval Tree支援區間的插入和刪除操作，並且可以在維持平衡的情況下進行這些操作。這使得它適用於需要不斷更新區間的應用，而不需要重新構建整個結構。
• 平衡性：正確實現的Interval Tree通常是平衡的，這意味著查詢操作的時間複雜度保持在較低的水平，通常是O(log n + k)，其中n是區間數，k是與查詢區間重疊的區間數。
• 應用廣泛：Interval Tree在許多領域都有廣泛的應用，包括計劃和日程管理、資料庫管理系統、地理資訊系統、任務調度、網路路由和碰撞檢測等。

缺點

• 實作複雜：正確實現Interval Tree需要較多的程式碼和複雜的邏輯，包括插入、刪除和重疊檢測等操作。這可能需要一些時間和努力，以確保正確性和效能。
• 記憶體使用：Interval Tree的資料結構相對複雜，可能需要較多的記憶體，特別是當存儲大量區間時。這可能會在內存有限的情況下成為一個問題。
• 不適用於一維點查詢：Interval Tree主要用於處理一維區間查詢，如果您需要處理單一點的查詢，則Interval Tree可能不是最佳選擇。

總結來說，Interval Tree是一個強大的資料結構，特別適用於解決一維區間查詢和相關問題。儘管它有一些實作上的複雜性和記憶體使用的問題，但在適當的應用場景中，它可以提供高效的解決方案。

不要輕言放棄，多堅持一下，也許你會發現更美麗的世界。(又要面臨連假的考驗了，加油!