C语言实现一个logn的map
时间: 2024-06-14 13:07:54 浏览: 9
在C语言中,要实现一个logn的map,可以使用平衡二叉搜索树(AVL树)来实现。AVL树是一种自平衡的二叉搜索树,它的插入、删除和查找操作的时间复杂度都是O(logn)。
以下是一个简单的C语言实现AVL树的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// AVL树节点结构
typedef struct Node {
int key;
struct Node* left;
struct Node* right;
int height;
} Node;
// 获取节点的高度
int getHeight(Node* node) {
if (node == NULL) {
return 0;
}
return node->height;
}
// 获取两个数中较大的数
int max(int a, int b) {
return (a > b) ? a : b;
}
// 创建一个新节点
Node* createNode(int key) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1;
return newNode;
}
// 右旋操作
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
// 执行旋转
x->right = y;
y->left = T2;
// 更新节点高度
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
// 左旋操作
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
// 执行旋转
y->left = x;
x->right = T2;
// 更新节点高度
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
// 获取节点的平衡因子
int getBalanceFactor(Node* node) {
if (node == NULL) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
// 插入节点
Node* insertNode(Node* node, int key) {
// 执行标准的BST插入
if (node == NULL) {
return createNode(key);
}
if (key < node->key) {
node->left = insertNode(node->left, key);
} else if (key > node->key) {
node->right = insertNode(node->right, key);
} else {
// 不允许插入相同的键值
return node;
}
// 更新节点高度
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
// 获取节点的平衡因子
int balanceFactor = getBalanceFactor(node);
// 平衡维护
// 左左情况,进行右旋操作
if (balanceFactor > 1 && key < node->left->key) {
return rightRotate(node);
}
// 右右情况,进行左旋操作
if (balanceFactor < -1 && key > node->right->key) {
return leftRotate(node);
}
// 左右情况,先进行左旋操作,再进行右旋操作
if (balanceFactor > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// 右左情况,先进行右旋操作,再进行左旋操作
if (balanceFactor < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 中序遍历AVL树
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->key);
inorderTraversal(root->right);
}
}
int main() {
Node* root = NULL;
// 插入节点
root = insertNode(root, 10);
root = insertNode(root, 20);
root = insertNode(root, 30);
root = insertNode(root, 40);
root = insertNode(root, 50);
root = insertNode(root, 25);
// 中序遍历AVL树
printf("AVL树中序遍历结果:");
inorderTraversal(root);
return 0;
}
```
以上代码实现了一个简单的AVL树,可以实现logn的插入、删除和查找操作。你可以根据需要修改代码来适应你的具体需求。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)