网站漂浮二维码,小黄猫传媒有限公司官方首页,沈阳网站页面设计公司,域名解析ip红黑树 C 语言的简单实现与代码解析
红黑树是计算机科学中一种重要的自平衡二叉搜索树。它确保了在最坏情况下#xff0c;基本的动态集合操作#xff08;如插入、删除和查找#xff09;具有对数时间复杂度。在这篇博客中#xff0c;我们将介绍一个简化的C语言红黑树实现基本的动态集合操作如插入、删除和查找具有对数时间复杂度。在这篇博客中我们将介绍一个简化的C语言红黑树实现并对代码进行详细解析。
1、示例代码
#include stdio.h
#include stdlib.htypedef enum { RED, BLACK } color_t;typedef struct Node {int data;color_t color;struct Node *left, *right, *parent;
} Node;typedef struct RedBlackTree {Node *root;
} RedBlackTree;// 创建新节点
Node* createNode(int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-left newNode-right newNode-parent NULL;newNode-color RED; // 默认为红色return newNode;
}// 左旋
void leftRotate(RedBlackTree* tree, Node* x) {Node* y x-right;x-right y-left;if (y-left ! NULL) y-left-parent x;y-parent x-parent;if (x-parent NULL) tree-root y;else if (x x-parent-left) x-parent-left y;else x-parent-right y;y-left x;x-parent y;
}// 右旋
void rightRotate(RedBlackTree* tree, Node* y) {Node* x y-left;y-left x-right;if (x-right ! NULL) x-right-parent y;x-parent y-parent;if (y-parent NULL) tree-root x;else if (y y-parent-left) y-parent-left x;else y-parent-right x;x-right y;y-parent x;
}// 插入修复操作
void insertFixup(RedBlackTree* tree, Node* z) {while (z-parent z-parent-color RED) {if (z-parent z-parent-parent-left) {Node* y z-parent-parent-right;if (y 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;leftRotate(tree, z);}z-parent-color BLACK;z-parent-parent-color RED;rightRotate(tree, z-parent-parent);}} else {// 类似地处理右侧情况// ...}}tree-root-color BLACK;
}// 插入节点
void insert(RedBlackTree* tree, int data) {Node* z createNode(data);Node* y NULL;Node* x tree-root;while (x ! NULL) {y x;if (z-data x-data) x x-left;else x x-right;}z-parent y;if (y NULL) tree-root z;else if (z-data y-data) y-left z;else y-right z;insertFixup(tree, z);
}// 其他操作如删除、查找等可以根据上述模式扩展int main() {RedBlackTree tree {NULL};int arr[] {7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13};int n sizeof(arr) / sizeof(arr[0]);for (int i 0; i n; i) {insert(tree, arr[i]);}// 执行其他操作或打印树结构return 0;
}2、代码解析
2.1. 基本结构
我们首先定义了两个基本结构Node 和 RedBlackTree。
typedef enum { RED, BLACK } color_t;typedef struct Node {int data;color_t color;struct Node *left, *right, *parent;
} Node;typedef struct RedBlackTree {Node *root;
} RedBlackTree;Node 结构包含一个整数数据、一个颜色红色或黑色以及左、右子节点和父节点的指针。RedBlackTree 结构只包含一个根节点指针。
2.2 左旋与右旋操作
红黑树的核心操作之一是旋转这有助于维护树的平衡性。
leftRotate 和 rightRotate 函数分别实现了左旋和右旋操作。
2.2 1. 左旋操作
左旋操作是为了将一个节点旋转到其右子节点的位置。这个操作旨在维护红黑树的平衡性。以下是左旋操作的步骤
选择节点假设要进行左旋的节点为 x并且其右子节点为 y。更新子节点将 x 的右子节点 y 的左子节点y 的左子节点作为 x 的新右子节点。更新父节点如果 x 有父节点更新其父节点以指向 y 而不是 x。更新 y 的左子节点将 y 的左子节点设置为 x。更新 x 的父节点将 y 的父节点设置为 x 的父节点。
2.2.2 右旋操作
右旋操作与左旋相反。它是为了将一个节点旋转到其左子节点的位置。以下是右旋操作的步骤
右旋步骤
选择节点假设要进行右旋的节点为 y并且其左子节点为 x。更新子节点将 y 的左子节点 x 的右子节点x 的右子节点作为 y 的新左子节点。更新父节点如果 y 有父节点更新其父节点以指向 x 而不是 y。更新 x 的右子节点将 x 的右子节点设置为 y。更新 y 的父节点将 x 的父节点设置为 y 的父节点。
3. 插入与修复操作
当向红黑树中插入新节点时可能会破坏红黑树的性质。因此我们需要进行修复操作。
insertFixup 函数实现了在插入后修复红黑树的逻辑。
4. 插入操作
为了简化我们只展示了如何向红黑树中插入新节点。其他操作如删除、查找等可以基于相似的原理进行扩展。
5. 示例
在主函数中我们展示了如何使用上述功能来创建和填充一个红黑树。
int main() {RedBlackTree tree {NULL};int arr[] {7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13};int n sizeof(arr) / sizeof(arr[0]);for (int i 0; i n; i) {insert(tree, arr[i]);}return 0;
}3、结论
虽然上述代码提供了一个基本的红黑树实现但实际上红黑树的设计和实现要复杂得多。在实际应用中需要考虑许多其他细节和情况。然而通过这个简化的示例我们可以更好地理解红黑树的基本原理和操作。
