帮我写个红黑树的c代码
时间: 2023-05-19 09:04:33 浏览: 53
好的,以下是一个红黑树的C语言代码示例:
```
#include <stdio.h>
#include <stdlib.h>
enum Color { RED, BLACK };
struct Node {
int data;
Color color;
Node *left;
Node *right;
Node *parent;
};
Node *NIL;
Node *newNode(int data) {
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->color = RED;
node->left = NIL;
node->right = NIL;
node->parent = NIL;
return node;
}
void leftRotate(Node *&root, Node *&pt) {
Node *pt_right = pt->right;
pt->right = pt_right->left;
if (pt->right != NIL)
pt->right->parent = pt;
pt_right->parent = pt->parent;
if (pt->parent == NIL)
root = pt_right;
else if (pt == pt->parent->left)
pt->parent->left = pt_right;
else
pt->parent->right = pt_right;
pt_right->left = pt;
pt->parent = pt_right;
}
void rightRotate(Node *&root, Node *&pt) {
Node *pt_left = pt->left;
pt->left = pt_left->right;
if (pt->left != NIL)
pt->left->parent = pt;
pt_left->parent = pt->parent;
if (pt->parent == NIL)
root = pt_left;
else if (pt == pt->parent->left)
pt->parent->left = pt_left;
else
pt->parent->right = pt_left;
pt_left->right = pt;
pt->parent = pt_left;
}
void insertFixUp(Node *&root, Node *&pt) {
Node *parent_pt = NULL;
Node *grand_parent_pt = NULL;
while ((pt != root) && (pt->color != BLACK) &&
(pt->parent->color == RED)) {
parent_pt = pt->parent;
grand_parent_pt = pt->parent->parent;
if (parent_pt == grand_parent_pt->left) {
Node *uncle_pt = grand_parent_pt->right;
if (uncle_pt->color == RED) {
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
} else {
if (pt == parent_pt->right) {
leftRotate(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
rightRotate(root, grand_parent_pt);
Color color = parent_pt->color;
parent_pt
相关推荐
![](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)