6、樹(shù)表查找

6.1、基本原理

樹(shù)表查找（Tree-based Search）通常是一種利用有序樹(shù)結(jié)構(gòu)進(jìn)行查找的算法，基于二叉搜索樹(shù)（BST）或其它平衡二叉搜索樹(shù)（如AVL樹(shù)、紅黑樹(shù)）等數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的查找算法。其基本原理是將查找值與樹(shù)中的某個(gè)節(jié)點(diǎn)進(jìn)行比較，根據(jù)比較結(jié)果，沿著樹(shù)的某個(gè)分支繼續(xù)向下查找，直到查找到目標(biāo)節(jié)點(diǎn)或者發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)不存在為止。

樹(shù)表查找的優(yōu)點(diǎn)是查找效率高，時(shí)間復(fù)雜度為 O(log n)，其中 n 是節(jié)點(diǎn)的總數(shù)。它的主要缺點(diǎn)是需要維護(hù)樹(shù)的平衡性，增加和刪除節(jié)點(diǎn)會(huì)導(dǎo)致樹(shù)的平衡性被破壞，需要進(jìn)行旋轉(zhuǎn)操作來(lái)恢復(fù)平衡，這樣會(huì)增加操作的時(shí)間復(fù)雜度。

實(shí)現(xiàn)樹(shù)表查找算法，需要定義一個(gè)樹(shù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)包括一個(gè)鍵和一個(gè)值。鍵用于比較大小，值是存儲(chǔ)的數(shù)據(jù)。具體實(shí)現(xiàn)可以使用遞歸或者迭代的方式，對(duì)于每個(gè)節(jié)點(diǎn)進(jìn)行比較，并根據(jù)比較結(jié)果決定向左子樹(shù)或者右子樹(shù)繼續(xù)查找，直到找到目標(biāo)節(jié)點(diǎn)或者發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)不存在為止。

6.2、代碼示例

方法一：基于BST實(shí)現(xiàn)

#include 
#include 


// 定義二叉搜索樹(shù)節(jié)點(diǎn)結(jié)構(gòu)體
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（用于驗(yàn)證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;
}

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

方法二：基于紅黑樹(shù)

基于紅黑樹(shù)實(shí)現(xiàn)的樹(shù)表查找，也稱為紅黑樹(shù)查找，是一種高效的查找算法。紅黑樹(shù)是一種自平衡二叉查找樹(shù)，它具有以下特點(diǎn)：

1. 每個(gè)節(jié)點(diǎn)都有顏色，紅色或黑色；
2. 根節(jié)點(diǎn)和葉子節(jié)點(diǎn)都是黑色；
3. 如果一個(gè)節(jié)點(diǎn)是紅色，則它的子節(jié)點(diǎn)必須是黑色；
4. 任何一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上，黑色節(jié)點(diǎn)的個(gè)數(shù)必須相同。

基于紅黑樹(shù)實(shí)現(xiàn)的樹(shù)表查找的實(shí)現(xiàn)過(guò)程如下：

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

紅黑樹(shù)的插入和刪除操作都會(huì)改變樹(shù)的結(jié)構(gòu)，因此在進(jìn)行插入和刪除操作時(shí)需要對(duì)紅黑樹(shù)進(jìn)行重新平衡。具體的平衡方法包括左旋、右旋、變色等操作，這些操作的目的是保持紅黑樹(shù)的平衡性和有序性。在進(jìn)行查找操作時(shí)，根據(jù)紅黑樹(shù)的特點(diǎn)可以快速定位到目標(biāo)元素，從而實(shí)現(xiàn)高效的查找。

rbtree.h

#ifndef _RED_BLACK_TREE_H_
#define _RED_BLACK_TREE_H_


#define RED        0    // 紅色節(jié)點(diǎn)
#define BLACK    1    // 黑色節(jié)點(diǎn)


typedef int Type;


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


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


// 創(chuàng)建紅黑樹(shù)，返回"紅黑樹(shù)的根"！
RBRoot* create_rbtree();


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


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


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




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


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


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


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


#endif