深入解析二叉查找樹

二叉查找樹（Binary Search Tree，簡稱BST）是一種常用的數據結構，由於其高效的查找和刪除操作，在計算機科學領域得到了廣泛應用。它是一棵二叉樹，其每個節點都含有一條關鍵字，且節點的左子樹所有節點的關鍵字小於該節點，右子樹所有節點的關鍵字大於該節點。

一、BST的基本操作

BST的基本操作包括插入、查找和刪除操作。

1. 插入操作

/**
 * 插入操作
 * @param root 根節點
 * @param key 要插入的節點值
 * @return 插入後的根節點
 */
Node* insert(Node* root, int key) {
    if (root == nullptr) {
        return new Node(key);
    }
    if (key val) {
        root->left = insert(root->left, key);
    } else if (key > root->val) {
        root->right = insert(root->right, key);
    }
    return root;
}

在插入一個節點時，從根節點開始，比較要插入的節點值與該節點值的大小，若小於該節點則遞歸到左子樹插入，否則遞歸到右子樹插入，如果為空則新建該節點。

2. 查找操作

/**
 * 查找操作
 * @param root 根節點
 * @param key 要查找的節點值
 * @return 是否存在該節點
 */
bool search(Node* root, int key) {
    if (root == nullptr) {
        return false;
    }
    if (root->val == key) {
        return true;
    } else if (root->val right, key);
    } else {
        return search(root->left, key);
    }
}

在查找一個節點時，從根節點開始，比較要查找的節點值與該節點值的大小，若小於該節點則遞歸到左子樹查找，否則遞歸到右子樹查找，如果為空則該節點不存在。

3. 刪除操作

/**
 * 查找以node為根節點的最小節點
 * @param node 根節點
 * @return 最小節點
 */
Node* getMinNode(Node* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

/**
 * 刪除節點操作
 * @param root 根節點
 * @param key 要刪除的節點值
 * @return 刪除後的根節點
 */
Node* remove(Node* root, int key) {
    if (root == nullptr) {
        return nullptr;
    }
    if (key val) {
        root->left = remove(root->left, key);
    } else if (key > root->val) {
        root->right = remove(root->right, key);
    } else {
        if (root->left == nullptr) {
            Node* rightNode = root->right;
            delete root;
            return rightNode;
        }
        if (root->right == nullptr) {
            Node* leftNode = root->left;
            delete root;
            return leftNode;
        }
        Node* successor = getMinNode(root->right);
        successor->right = remove(root->right, successor->val);
        successor->left = root->left;
        delete root;
        return successor;
    }
    return root;
}

在刪除一個節點時，需要考慮其左子樹或右子樹為空、左右子樹都存在的情況，其中左右子樹都存在時，需要找到該節點右子樹的最小值作為該節點的後繼，將其刪除，再用該後繼替換該節點。

二、BST的實現

1. 遞歸實現

最常見的BST實現方式是遞歸實現，代碼比較簡單易懂：

class BST {
private:
    struct Node {
        int val;
        Node* left;
        Node* right;
        Node(int value) : val(value), left(nullptr), right(nullptr) {}
    };
    Node* root;
    // 插入節點
    Node* insertNode(Node* node, int key) {
        if (node == nullptr) {
            return new Node(key);
        }
        if (key val) {
            node->left = insertNode(node->left, key);
        } else if (key > node->val) {
            node->right = insertNode(node->right, key);
        }
        return node;
    }
    // 查找節點
    bool searchNode(Node* node, int key) {
        if (node == nullptr) {
            return false;
        }
        if (node->val == key) {
            return true;
        } else if (node->val right, key);
        } else {
            return searchNode(node->left, key);
        }
    }
    // 刪除節點
    Node* removeNode(Node* node, int key) {
        if (node == nullptr) {
            return nullptr;
        }
        if (key val) {
            node->left = removeNode(node->left, key);
        } else if (key > node->val) {
            node->right = removeNode(node->right, key);
        } else {
            if (node->left == nullptr) {
                Node* rightNode = node->right;
                delete node;
                return rightNode;
            }
            if (node->right == nullptr) {
                Node* leftNode = node->left;
                delete node;
                return leftNode;
            }
            Node* successor = getMinNode(node->right);
            successor->right = removeNode(node->right, successor->val);
            successor->left = node->left;
            delete node;
            return successor;
        }
        return node;
    }
    // 查找最小節點
    Node* getMinNode(Node* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }
public:
    BST() : root(nullptr) {}
    // 插入節點
    void insert(int key) {
        root = insertNode(root, key);
    }
    // 查找節點
    bool search(int key) {
        return searchNode(root, key);
    }
    // 刪除節點
    void remove(int key) {
        root = removeNode(root, key);
    }
};

2. 非遞歸實現

遞歸實現雖然簡單，但是過多的函數調用會導致性能下降。因此，BST也可以用非遞歸方式實現。

class BST {
private:
    struct Node {
        int val;
        Node* left;
        Node* right;
        Node(int value) : val(value), left(nullptr), right(nullptr) {}
    };
    Node* root;
public:
    BST() : root(nullptr) {}
    // 插入節點
    void insert(int key) {
        Node* curr = root, *prev = nullptr;
        while (curr != nullptr) {
            prev = curr;
            if (key val) {
                curr = curr->left;
            } else if (key > curr->val) {
                curr = curr->right;
            } else {
                return;
            }
        }
        if (prev == nullptr) {
            root = new Node(key);
            return;
        }
        if (key val) {
            prev->left = new Node(key);
        } else {
            prev->right = new Node(key);
        }
    }
    // 查找節點
    bool search(int key) {
        Node* curr = root;
        while (curr != nullptr) {
            if (curr->val == key) {
                return true;
            } else if (curr->val right;
            } else {
                curr = curr->left;
            }
        }
        return false;
    }
    // 刪除節點
    void remove(int key) {
        Node* curr = root, *prev = nullptr;
        while (curr != nullptr && curr->val != key) {
            prev = curr;
            if (curr->val right;
            } else {
                curr = curr->left;
            }
        }
        if (curr == nullptr) {
            return;
        }
        if (curr->left == nullptr) {
            if (prev == nullptr) {
                root = curr->right;
            } else if (prev->left == curr) {
                prev->left = curr->right;
            } else {
                prev->right = curr->right;
            }
            delete curr;
        } else if (curr->right == nullptr) {
            if (prev == nullptr) {
                root = curr->left;
            } else if (prev->left == curr) {
                prev->left = curr->left;
            } else {
                prev->right = curr->left;
            }
            delete curr;
        } else {
            Node* prev2 = curr, *curr2 = curr->right;
            while (curr2->left != nullptr) {
                prev2 = curr2;
                curr2 = curr2->left;
            }
            if (prev2->left == curr2) {
                prev2->left = curr2->right;
            } else {
                prev2->right = curr2->right;
            }
            curr->val = curr2->val;
            delete curr2;
        }
    }
};

三、BST的應用

1. 排序

BST的中序遍歷得到的元素就是排好序的。

/**
 * BST中序遍歷
 * @param root 根節點
 * @return 排序後的數組
 */
vector inorderTraversal(Node* root) {
    vector res;
    inorder(root, res);
    return res;
}
void inorder(Node* root, vector& res) {
    if (root == nullptr) {
        return;
    }
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

2. 前綴匹配

給定一個字元串集合，使用BST可以實現前綴匹配功能，即查找所有以某個字元串為前綴的字元串。

class Trie {
private:
    struct TrieNode {
        bool isEnd;
        unordered_map children;
        TrieNode() : isEnd(false) {}
    };
    TrieNode* root;
    void dfs(TrieNode* node, string& word, vector& res) {
        if (node->isEnd) {
            res.push_back(word);
        }
        for (auto& p : node->children) {
            word.push_back(p.first);
            dfs(p.second, word, res);
            word.pop_back();
        }
    }
public:
    Trie() : root(new TrieNode()) {}
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEnd = true;
    }
    vector searchByPrefix(string prefix) {
        vector res;
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children.count(c)) {
                return res;
            }
            node = node->children[c];
        }
        dfs(node, prefix, res);
        return res;
    }
};

在Trie樹中，用BST作為每個節點的子節點存儲字元，查找所有以某個字元串為前綴的字元串時，只需要查找該前綴的所有子節點並進行DFS即可。

四、BST的優化與擴展

1. 平衡二叉樹

由於BST可能退化成鏈表，因此需要保證其平衡，即左右子樹高度差不超過1。常見的平衡二叉樹包括AVL樹、紅黑樹等。

2. B樹和B+樹

與平衡二叉樹類似，B樹和B+樹是一種使用平衡的數據結構，用於存儲大量的數據，通常被應用於文件系統、資料庫系統等領域。

3. 可持久化BST

可持久化BST是一種可以支持歷史版本查詢的數據結構，每次修改節點時都會創建一個新版本。常使用函數式編程或複製-on-write等技術實現。

五、總結

原創文章，作者：GJKEC，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/372364.html