常见的查找算法汇总（含详细代码）3

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