算法 - 查找算法（顺序、折半、红黑树、AVL树、B+树、散列）

查找

顺序查找

查找算法原理：
顺序查找是一种简单的查找方法，从数组的第一个元素开始，依次比较每个元素，直到找到目标元素或者数组结束为止。

实现步骤：

1. 从数组的第一个元素开始。
2. 逐一比较数组中的元素与目标值。
3. 如果找到目标值，返回其索引。
4. 如果遍历完整个数组仍未找到，返回-1。

C语言代码：

#include <stdio.h>int sequential_search(int arr[], int n, int target) {for (int i = 0; i < n; i++) {if (arr[i] == target) {return i;}}return -1;
}int main() {int arr[] = {2, 4, 6, 8, 10};int target = 6;int n = sizeof(arr) / sizeof(arr[0]);int result = sequential_search(arr, n, target);if (result != -1) {printf("Element found at index %d\n", result);} else {printf("Element not found\n");}return 0;
}

代码解释：

• int sequential_search(int arr[], int n, int target): 定义顺序查找函数，参数为数组、数组长度和目标值。
• for (int i = 0; i < n; i++): 遍历数组。
• if (arr[i] == target): 如果找到目标值。
• return i: 返回目标值的索引。
• return -1: 如果未找到目标值，返回-1。

折半查找（也称二分查找）

查找算法原理：
折半查找是一种在有序数组中查找目标值的高效方法。它通过不断将查找范围减半，直到找到目标值或范围为空为止。

实现步骤：

1. 确定查找范围的起始和结束索引。
2. 计算中间索引。
3. 比较中间元素与目标值。
4. 如果中间元素等于目标值，返回其索引。
5. 如果中间元素小于目标值，缩小查找范围至右半部分。
6. 如果中间元素大于目标值，缩小查找范围至左半部分。
7. 重复上述步骤直到找到目标值或范围为空。

C语言代码：

#include <stdio.h>int binary_search(int arr[], int n, int target) {int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;}if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}int main() {int arr[] = {2, 4, 6, 8, 10};int target = 6;int n = sizeof(arr) / sizeof(arr[0]);int result = binary_search(arr, n, target);if (result != -1) {printf("Element found at index %d\n", result);} else {printf("Element not found\n");}return 0;
}

代码解释：

• int binary_search(int arr[], int n, int target): 定义二分查找函数，参数为数组、数组长度和目标值。
• int left = 0, right = n - 1: 初始化左右索引。
• while (left <= right): 当查找范围有效时。
• int mid = left + (right - left) / 2: 计算中间索引。
• if (arr[mid] == target): 如果找到目标值。
• return mid: 返回目标值的索引。
• if (arr[mid] < target): 如果中间元素小于目标值。
• left = mid + 1: 调整左索引。
• else: 如果中间元素大于目标值。
• right = mid - 1: 调整右索引。
• return -1: 如果未找到目标值，返回-1。

分块查找

查找算法原理：
分块查找将数据分成若干块，并在每块中进行线性查找。首先找到目标值可能所在的块，然后在该块中进行顺序查找。

实现步骤：

1. 将数据分成若干块。
2. 在块索引中找到目标值可能所在的块。
3. 在该块中进行顺序查找。

C语言代码：

#include <stdio.h>int block_search(int arr[], int n, int target, int block_size) {int block_count = (n + block_size - 1) / block_size;for (int i = 0; i < block_count; i++) {int start = i * block_size;int end = start + block_size;if (end > n) end = n;if (arr[end - 1] >= target) {for (int j = start; j < end; j++) {if (arr[j] == target) {return j;}}return -1;}}return -1;
}int main() {int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18};int target = 10;int n = sizeof(arr) / sizeof(arr[0]);int block_size = 3;int result = block_search(arr, n, target, block_size);if (result != -1) {printf("Element found at index %d\n", result);} else {printf("Element not found\n");}return 0;
}

代码解释：

• int block_search(int arr[], int n, int target, int block_size): 定义分块查找函数，参数为数组、数组长度、目标值和块大小。
• int block_count = (n + block_size - 1) / block_size: 计算块的数量。
• for (int i = 0; i < block_count; i++): 遍历每个块。
• int start = i * block_size: 计算当前块的起始索引。
• int end = start + block_size: 计算当前块的结束索引。
• if (end > n) end = n: 如果结束索引超过数组长度，调整结束索引。
• if (arr[end - 1] >= target): 如果目标值在当前块中。
• for (int j = start; j < end; j++): 在块中进行顺序查找。
• if (arr[j] == target): 如果找到目标值。
• return j: 返回目标值的索引。
• return -1: 如果未找到目标值，返回-1。

二叉排序树查找

查找算法原理：
二叉排序树（BST）是一种二叉树，每个节点的左子树所有值都小于该节点的值，右子树所有值都大于该节点的值。在BST中查找目标值时，通过比较当前节点值与目标值，决定在左子树或右子树中继续查找。

实现步骤：

1. 从根节点开始。
2. 比较当前节点值与目标值。
3. 如果相等，返回该节点。
4. 如果目标值小于当前节点值，在左子树中递归查找。
5. 如果目标值大于当前节点值，在右子树中递归查找。
6. 如果节点为空，返回未找到。

C语言代码：

#include <stdio.h>
#include <stdlib.h>struct TreeNode {int val;struct TreeNode *left, *right;
};struct TreeNode* create_node(int key) {struct TreeNode* new_node = (struct TreeNode*)malloc(sizeof(struct TreeNode));new_node->val = key;new_node->left = new_node->right = NULL;return new_node;
}struct TreeNode* insert(struct TreeNode* node, int key) {if (node == NULL) return create_node(key);if (key < node->val)node->left = insert(node->left, key);else if (key > node->val)node->right = insert(node->right, key);return node;
}struct TreeNode* search(struct TreeNode* root, int target) {if (root == NULL || root->val == target)return root;if (target < root->val)return search(root->left, target);return search(root->right, target);
}int main() {struct TreeNode* root = NULL;int keys[] = {20, 8, 22, 4, 12, 10, 14};int n = sizeof(keys) / sizeof(keys[0]);for (int i = 0; i < n; i++) {root = insert(root, keys[i]);}int target = 10;struct TreeNode* result = search(root, target);if (result != NULL) {printf("Element found: %d\n", result->val);} else {printf("Element not found\n");}return 0;
}

代码解释：

• struct TreeNode: 定义二叉排序树节点结构。
• struct TreeNode* create_node(int key): 创建新节点。
• struct TreeNode* insert(struct TreeNode* node, int key): 插入节点。
• struct TreeNode* search(struct TreeNode* root, int target): 查找节点。
• int main(): 主函数，演示插入和查找操作。

平衡二叉树（AVL树）

查找算法原理：
平衡二叉树是一种自平衡的二叉排序树，其左右子树的高度差最多为1，确保查找、插入、删除的时间复杂度为O(log n)。

实现步骤：

1. 插入节点后，通过旋转操作保持树的平衡。
2. 左旋和右旋操作用于重新平衡树。
3. 计算每个节点的高度以保持平衡。

C语言代码：

#include <stdio.h>
#include <stdlib.h>struct TreeNode {int val;struct TreeNode *left, *right;int height;
};int max(int a, int b) {return (a > b) ? a : b;
}int height(struct TreeNode *N) {return (N == NULL) ? 0 : N->height;
}struct TreeNode* create_node(int key) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = key;node->left = node->right = NULL;node->height = 1;return node;
}struct TreeNode* right_rotate(struct TreeNode *y) {struct TreeNode *x = y->left;struct TreeNode *T2 = x->right;x->right = y;y->left = T2;y->height = max(height(y->left), height(y->right)) + 1;x->height = max(height(x->left), height(x->right)) + 1;return x;
}struct TreeNode* left_rotate(struct TreeNode *x) {struct TreeNode *y = x->right;struct TreeNode *T2 = y->left;y->left = x;x->right = T2;x->height = max(height(x->left), height(x->right)) + 1;y->height = max(height(y->left), height(y->right)) + 1;return y;
}int get_balance(struct TreeNode *N) {return (N == NULL) ? 0 : height(N->left) - height(N->right);
}struct TreeNode* insert(struct TreeNode* node, int key) {if (node == NULL)return create_node(key);if (key < node->val)node->left = insert(node->left, key);else if (key > node->val)node->right = insert(node->right, key);elsereturn node;node->height = 1 + max(height(node->left), height(node->right));int balance = get_balance(node);if (balance > 1 && key < node->left->val)return right_rotate(node);if (balance < -1 && key > node->right->val)return left_rotate(node);if (balance > 1 && key > node->left->val) {node->left = left_rotate(node->left);return right_rotate(node);}if (balance < -1 && key < node->right->val) {node->right = right_rotate(node->right);return left_rotate(node);}return node;
}struct TreeNode* search(struct TreeNode* root, int target) {if (root == NULL || root->val == target)return root;if (target < root->val)return search(root->left, target);return search(root->right, target);
}int main() {struct TreeNode* root = NULL;int keys[] = {20, 8, 22, 4, 12, 10, 14};int n = sizeof(keys) / sizeof(keys[0]);for (int i = 0; i < n; i++) {root = insert(root, keys[i]);}int target = 10;struct TreeNode* result = search(root, target);if (result != NULL) {printf("Element found: %d\n", result->val);} else {printf("Element not found\n");}return 0;
}

代码解释：

• 定义AVL树节点结构，包含节点值、左子树、右子树和节点高度。
• create_node 函数用于创建新节点。
• right_rotate 和 left_rotate 函数用于保持树的平衡。
• get_balance 函数用于计算节点的平衡因子。
• insert 函数用于插入节点并保持树的平衡。
• search 函数用于查找节点。

红黑树

查找算法原理：
红黑树是一种自平衡的二叉查找树，每个节点包含一个颜色（红色或黑色）。通过节点颜色和旋转操作保持树的平衡，确保查找、插入、删除操作的时间复杂度为O(log n)。

实现步骤：

1. 插入节点后通过颜色调整和旋转操作保持树的平衡。
2. 左旋和右旋操作用于重新平衡树。
3. 确保树的性质：根节点是黑色，红色节点的子节点是黑色，从任一节点到叶子节点的路径上黑色节点数相同。

C语言代码：

#include <stdio.h>
#include <stdlib.h>enum Color { RED, BLACK };struct TreeNode {int val;enum Color color;struct TreeNode *left, *right, *parent;
};struct TreeNode* create_node(int key) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = key;node->color = RED;node->left = node->right = node->parent = NULL;return node;
}void left_rotate(struct TreeNode** root, struct TreeNode* x) {struct TreeNode* y = x->right;x->right = y->left;if (y->left != NULL) y->left->parent = x;y->parent = x->parent;if (x->parent == NULL)*root = y;else if (x == x->parent->left)x->parent->left = y;elsex->parent->right = y;y->left = x;x->parent = y;
}void right_rotate(struct TreeNode** root, struct TreeNode* y) {struct TreeNode* x = y->left;y->left = x->right;if (x->right != NULL) x->right->parent = y;x->parent = y->parent;if (y->parent == NULL)*root = x;else if (y == y->parent->left)y->parent->left = x;elsey->parent->right = x;x->right = y;y->parent = x;
}void insert_fixup(struct TreeNode** root, struct TreeNode* z) {while (z->parent != NULL && z->parent->color == RED) {if (z->parent == z->parent->parent->left) {struct TreeNode* y = z->parent->parent->right;if (y != NULL && y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->right) {z = z->parent;left_rotate(root, z);}z->parent->color = BLACK;z->parent->parent->color = RED;right_rotate(root, z->parent->parent);}} else {struct TreeNode* y = z->parent->parent->left;if (y != NULL && y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->left) {z = z->parent;right_rotate(root, z);}z->parent->color = BLACK;z->parent->parent->color = RED;left_rotate(root, z->parent->parent);}}}(*root)->color = BLACK;
}void insert(struct TreeNode** root, int key) {struct TreeNode* z = create_node(key);struct TreeNode* y = NULL;struct TreeNode* x = *root;while (x != NULL) {y = x;if (z->val < x->val)x = x->left;elsex = x->right;}z->parent = y;if (y == NULL)*root = z;else if (z->val < y->val)y->left = z;elsey->right = z;insert_fixup(root, z);
}struct TreeNode* search(struct TreeNode* root, int target) {while (root != NULL && root->val != target) {if (target < root->val)root= root->left;elseroot = root->right;}return root;
}int main() {struct TreeNode* root = NULL;int keys[] = {20, 8, 22, 4, 12, 10, 14};int n = sizeof(keys) / sizeof(keys[0]);for (int i = 0; i < n; i++) {insert(&root, keys[i]);}int target = 10;struct TreeNode* result = search(root, target);if (result != NULL) {printf("Element found: %d\n", result->val);} else {printf("Element not found\n");}return 0;
}

代码解释：

• 定义红黑树节点结构，包含节点值、颜色、左子树、右子树和父节点。
• create_node 函数用于创建新节点。
• left_rotate 和 right_rotate 函数用于保持树的平衡。
• insert_fixup 函数用于插入节点后的颜色调整和旋转操作。
• insert 函数用于插入节点并保持树的平衡。
• search 函数用于查找节点。

B树

查找算法原理：
B树是一种自平衡的树数据结构，广泛应用于数据库和文件系统中。B树节点可以有多个子节点和关键字，确保查找、插入、删除操作的时间复杂度为O(log n)。

实现步骤：

1. B树的每个节点可以包含多个关键字和子节点。
2. 关键字和子节点根据值进行分布。
3. 插入和删除操作需要保持树的平衡，通过节点分裂和合并操作实现。

C语言代码：

#include <stdio.h>
#include <stdlib.h>#define T 3struct BTreeNode {int *keys;int t;struct BTreeNode **C;int n;int leaf;
};struct BTreeNode* create_node(int t, int leaf) {struct BTreeNode* node = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));node->t = t;node->leaf = leaf;node->keys = (int*)malloc((2*t-1) * sizeof(int));node->C = (struct BTreeNode**)malloc((2*t) * sizeof(struct BTreeNode*));node->n = 0;return node;
}void traverse(struct BTreeNode* root) {int i;for (i = 0; i < root->n; i++) {if (!root->leaf)traverse(root->C[i]);printf(" %d", root->keys[i]);}if (!root->leaf)traverse(root->C[i]);
}struct BTreeNode* search(struct BTreeNode* root, int k) {int i = 0;while (i < root->n && k > root->keys[i])i++;if (root->keys[i] == k)return root;if (root->leaf)return NULL;return search(root->C[i], k);
}void insert_non_full(struct BTreeNode* x, int k);
void split_child(struct BTreeNode* x, int i, struct BTreeNode* y);void insert(struct BTreeNode** root, int k) {struct BTreeNode* r = *root;if (r->n == 2*T-1) {struct BTreeNode* s = create_node(r->t, 0);s->C[0] = r;split_child(s, 0, r);int i = 0;if (s->keys[0] < k)i++;insert_non_full(s->C[i], k);*root = s;} else {insert_non_full(r, k);}
}void split_child(struct BTreeNode* x, int i, struct BTreeNode* y) {struct BTreeNode* z = create_node(y->t, y->leaf);z->n = T - 1;for (int j = 0; j < T-1; j++)z->keys[j] = y->keys[j+T];if (!y->leaf) {for (int j = 0; j < T; j++)z->C[j] = y->C[j+T];}y->n = T - 1;for (int j = x->n; j >= i+1; j--)x->C[j+1] = x->C[j];x->C[i+1] = z;for (int j = x->n-1; j >= i; j--)x->keys[j+1] = x->keys[j];x->keys[i] = y->keys[T-1];x->n = x->n + 1;
}void insert_non_full(struct BTreeNode* x, int k) {int i = x->n - 1;if (x->leaf) {while (i >= 0 && x->keys[i] > k) {x->keys[i+1] = x->keys[i];i--;}x->keys[i+1] = k;x->n = x->n + 1;} else {while (i >= 0 && x->keys[i] > k)i--;if (x->C[i+1]->n == 2*T-1) {split_child(x, i+1, x->C[i+1]);if (x->keys[i+1] < k)i++;}insert_non_full(x->C[i+1], k);}
}int main() {struct BTreeNode* root = create_node(T, 1);int keys[] = {10, 20, 5, 6, 12, 30, 7, 17};int n = sizeof(keys) / sizeof(keys[0]);for (int i = 0; i < n; i++) {insert(&root, keys[i]);}printf("Traversal of the constructed tree is ");traverse(root);int target = 6;struct BTreeNode* result = search(root, target);if (result != NULL) {printf("\nElement found");} else {printf("\nElement not found");}return 0;
}

代码解释：

• 定义B树节点结构，包含关键字、子节点、关键字数量和是否为叶子节点。
• create_node 函数用于创建新节点。
• traverse 函数用于遍历B树。
• search 函数用于查找节点。
• insert 函数用于插入节点。
• split_child 函数用于分裂节点。
• insert_non_full 函数用于在非满节点中插入关键字。

B+树

查找算法原理：
B+树是B树的一种变种，所有数据都存储在叶子节点中，并且叶子节点通过链表相连。B+树的非叶子节点只存储索引，便于范围查找。

实现步骤：

1. B+树的每个节点可以包含多个关键字和子节点。
2. 关键字和子节点根据值进行分布。
3. 插入和删除操作需要保持树的平衡，通过节点分裂和合并操作实现。

C语言代码：

#include <stdio.h>
#include <stdlib.h>#define T 3struct BPlusTreeNode {int *keys;struct BPlusTreeNode **C;struct BPlusTreeNode *next;int n;int leaf;
};struct BPlusTreeNode* create_node(int leaf) {struct BPlusTreeNode* node = (struct BPlusTreeNode*)malloc(sizeof(struct BPlusTreeNode));node->keys = (int*)malloc((2*T-1) * sizeof(int));node->C = (struct BPlusTreeNode**)malloc((2*T) * sizeof(struct BPlusTreeNode*));node->next = NULL;node->n = 0;node->leaf = leaf;return node;
}void traverse(struct BPlusTreeNode* root) {struct BPlusTreeNode* current = root;while (!current->leaf)current = current->C[0];while (current) {for (int i = 0; i < current->n; i++)printf(" %d", current->keys[i]);current = current->next;}
}struct BPlusTreeNode* search(struct BPlusTreeNode* root, int k) {int i = 0;while (i < root->n && k > root->keys[i])i++;if (i < root->n && root->keys[i] == k)return root;if (root->leaf)return NULL;return search(root->C[i], k);
}void insert_non_full(struct BPlusTreeNode* x, int k);
void split_child(struct BPlusTreeNode* x, int i, struct BPlusTreeNode* y);void insert(struct BPlusTreeNode** root, int k) {struct BPlusTreeNode* r = *root;if (r->n == 2*T-1) {struct BPlusTreeNode* s = create_node(0);s->C[0] = r;split_child(s, 0, r);int i = 0;if (s->keys[0] < k)i++;insert_non_full(s->C[i], k);*root = s;} else {insert_non_full(r, k);}
}void split_child(struct BPlusTreeNode* x, int i, struct BPlusTreeNode* y) {struct BPlusTreeNode* z = create_node(y->leaf);z->n = T - 1;for (int j = 0; j < T-1; j++)z->keys[j] = y->keys[j+T];if (!y->leaf) {for (int j = 0; j < T; j++)z->C[j] = y->C[j+T];} else {z->next = y->next;y->next = z;}y->n = T - 1;for (int j = x->n; j >= i+1; j--)x->C[j+1] = x->C[j];x->C[i+1] = z;for (int j = x->n-1; j >= i; j--)x->keys[j+1] = x->keys[j];x->keys[i] = y->keys[T-1];x->n = x->n + 1;
}void insert_non_full(struct BPlusTreeNode* x, int k) {int i = x->n - 1;if (x->leaf) {while (i >= 0 && x->keys[i] > k) {x->keys[i+1] = x->keys[i];i--;}x->keys[i+1] = k;x->n = x->n + 1;} else {while (i >= 0 && x->keys[i] > k)i--;if (x->C[i+1]->n == 2*T-1) {split_child(x, i+1, x->C[i+1]);if (x->keys[i+1] < k)i++;}insert_non_full(x->C[i+1], k);}
}int main() {struct BPlusTreeNode* root = create_node(1);int keys[] = {10, 20, 5, 6, 12, 30, 7, 17};int n = sizeof(keys) / sizeof(keys[0]);for (int i = 0; i < n; i++) {insert(&root, keys[i]);}printf("Traversal of the constructed B+ tree is ");traverse(root);int target = 6;struct BPlusTreeNode* result = search(root, target);if (result != NULL) {printf("\nElement found");} else {printf("\nElement not found");}return 0;
}

代码解释：

• 定义B+树节点结构，包含关键字、子节点、下一个节点、关键字数量和是否为叶子节点。
• create_node 函数用于创建新节点。
• traverse 函数用于遍历B+树。
• search 函数用于查找节点。
• insert 函数用于插入节点。
• split_child 函数用于分裂节点。
• insert_non_full 函数用于在非满节点中插入关键字。

散列查找

查找算法原理：
散列查找通过散列函数将关键字映射到数组中的位置。使用链地址法处理散列冲突，每个数组位置存储一个链表，链表中的每个节点包含具有相同散列值的关键字。

实现步骤：

1. 使用散列函数计算关键字的散列值。
2. 根据散列值将关键字插入对应位置的链表中。
3. 查找时，计算关键字的散列值，然后在链表中查找目标值。

C语言代码：

#include <stdio.h>
#include <stdlib.h>#define TABLE_SIZE 10struct Node {int key;struct Node* next;
};struct Node* hash_table[TABLE_SIZE];unsigned int hash(int key) {return key % TABLE_SIZE;
}void insert(int key) {unsigned int index = hash(key);struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));new_node->key = key;new_node->next = hash_table[index];hash_table[index] = new_node;
}struct Node* search(int key) {unsigned int index = hash(key);struct Node* current = hash_table[index];while (current != NULL) {if (current->key == key)return current;current = current->next;}return NULL;
}void display() {for (int i = 0; i < TABLE_SIZE; i++) {struct Node* current = hash_table[i];printf("hash_table[%d]: ", i);while (current != NULL) {printf("%d -> ", current->key);current = current->next;}printf("NULL\n");}
}int main() {insert(10);insert(20);insert(15);insert(7);insert(32);display();int target = 15;struct Node* result = search(target);if (result != NULL) {printf("Element found: %d\n", result->key);} else {printf("Element not found\n");}return 0;
}

代码解释：

• 定义链表节点结构，包含关键字和下一个节点指针。
• 定义哈希表为链表节点指针数组。
• hash 函数用于计算关键字的散列值。
• insert 函数用于插入关键字到哈希表。
• search 函数用于查找关键字。
• display 函数用于显示哈希表的内容。