6、樹表查找

6.1、基本原理

樹表查找（Tree-based Search）通常是一種利用有序樹結構進行查找的算法，基于二叉搜索樹（BST）或其它平衡二叉搜索樹（如AVL樹、紅黑樹）等數據結構實現的查找算法。其基本原理是將查找值與樹中的某個節點進行比較，根據比較結果，沿著樹的某個分支繼續向下查找，直到查找到目標節點或者發現目標節點不存在為止。

樹表查找的優點是查找效率高，時間復雜度為 O(log n)，其中 n 是節點的總數。它的主要缺點是需要維護樹的平衡性，增加和刪除節點會導致樹的平衡性被破壞，需要進行旋轉操作來恢復平衡，這樣會增加操作的時間復雜度。

實現樹表查找算法，需要定義一個樹結構，每個節點包括一個鍵和一個值。鍵用于比較大小，值是存儲的數據。具體實現可以使用遞歸或者迭代的方式，對于每個節點進行比較，并根據比較結果決定向左子樹或者右子樹繼續查找，直到找到目標節點或者發現目標節點不存在為止。

6.2、代碼示例

方法一：基于BST實現

#include 
#include 


// 定義二叉搜索樹節點結構體
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};


// BST的插入操作
struct TreeNode* insert(struct TreeNode* root, int val) {
    if (root == NULL) {
        struct TreeNode* new_node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        new_node->val = val;
        new_node->left = NULL;
        new_node->right = NULL;
        return new_node;
    } else {
        if (val < root->val) {
            root->left = insert(root->left, val);
        } else if (val > root->val) {
            root->right = insert(root->right, val);
        }
        return root;
    }
}


// BST的查找操作
struct TreeNode* search(struct TreeNode* root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    } else if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}


// 中序遍歷BST（用于驗證BST的正確性）
void inorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->val);
        inorderTraversal(root->right);
    }
}


int main() {
    struct TreeNode* root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 6);
    root = insert(root, 8);


    inorderTraversal(root); // 輸出：2 3 4 5 6 7 8


    struct TreeNode* node = search(root, 6);
    if (node != NULL) {
        printf("找到了：%d\\n", node->val); // 輸出：找到了：6
    } else {
        printf("未找到\\n");
    }


    return 0;
}

該代碼定義了一個二叉搜索樹的結構體TreeNode，包含了該節點的值val、左子節點指針left、右子節點指針right。同時，實現了BST的插入和查找操作，其中插入操作是遞歸實現的，查找操作也是遞歸實現的。最后，利用中序遍歷函數inorderTraversal驗證了BST的正確性，以及利用查找函數search查找了節點6。

方法二：基于紅黑樹

基于紅黑樹實現的樹表查找，也稱為紅黑樹查找，是一種高效的查找算法。紅黑樹是一種自平衡二叉查找樹，它具有以下特點：

1. 每個節點都有顏色，紅色或黑色；
2. 根節點和葉子節點都是黑色；
3. 如果一個節點是紅色，則它的子節點必須是黑色；
4. 任何一條從根節點到葉子節點的路徑上，黑色節點的個數必須相同。

基于紅黑樹實現的樹表查找的實現過程如下：

1. 構建紅黑樹，將要查找的元素插入到紅黑樹中；
2. 對紅黑樹進行遍歷，查找需要的元素；
3. 如果查找成功，返回該元素的位置；
4. 如果查找失敗，返回空指針。

紅黑樹的插入和刪除操作都會改變樹的結構，因此在進行插入和刪除操作時需要對紅黑樹進行重新平衡。具體的平衡方法包括左旋、右旋、變色等操作，這些操作的目的是保持紅黑樹的平衡性和有序性。在進行查找操作時，根據紅黑樹的特點可以快速定位到目標元素，從而實現高效的查找。

rbtree.h

#ifndef _RED_BLACK_TREE_H_
#define _RED_BLACK_TREE_H_


#define RED        0    // 紅色節點
#define BLACK    1    // 黑色節點


typedef int Type;


// 紅黑樹的節點
typedef struct RBTreeNode{
    unsigned char color;        // 顏色(RED 或 BLACK)
    Type   key;                    // 關鍵字(鍵值)
    struct RBTreeNode *left;    // 左孩子
    struct RBTreeNode *right;    // 右孩子
    struct RBTreeNode *parent;    // 父結點
}Node, *RBTree;


// 紅黑樹的根
typedef struct rb_root{
    Node *node;
}RBRoot;


// 創建紅黑樹，返回"紅黑樹的根"！
RBRoot* create_rbtree();


// 銷毀紅黑樹
void destroy_rbtree(RBRoot *root);


// 將結點插入到紅黑樹中。插入成功，返回0；失敗返回-1。
int insert_rbtree(RBRoot *root, Type key);


// 刪除結點(key為節點的值)
void delete_rbtree(RBRoot *root, Type key);




// 前序遍歷"紅黑樹"
void preorder_rbtree(RBRoot *root);
// 中序遍歷"紅黑樹"
void inorder_rbtree(RBRoot *root);
// 后序遍歷"紅黑樹"
void postorder_rbtree(RBRoot *root);


// (遞歸實現)查找"紅黑樹"中鍵值為key的節點。找到的話，返回0；否則，返回-1。
int rbtree_search(RBRoot *root, Type key);
// (非遞歸實現)查找"紅黑樹"中鍵值為key的節點。找到的話，返回0；否則，返回-1。
int iterative_rbtree_search(RBRoot *root, Type key);


// 返回最小結點的值(將值保存到val中)。找到的話，返回0；否則返回-1。
int rbtree_minimum(RBRoot *root, int *val);
// 返回最大結點的值(將值保存到val中)。找到的話，返回0；否則返回-1。
int rbtree_maximum(RBRoot *root, int *val);


// 打印紅黑樹
void print_rbtree(RBRoot *root);


#endif