红黑树的基本操作有哪些
时间: 2023-11-11 18:36:59 浏览: 50
红黑树的基本操作包括插入、删除和查找。
插入操作:
1. 在红黑树中插入新节点,并将其颜色设为红色。
2. 根据红黑树的性质进行调整,确保插入后仍然满足红黑树的性质。
删除操作:
1. 找到要删除的节点,并将其删除。
2. 根据红黑树的性质进行调整,确保删除后仍然满足红黑树的性质。
查找操作:
在红黑树中查找指定的节点,并返回其值。
除了这些基本操作,还有一些其他的操作,如旋转操作等,它们也是红黑树的重要操作。
相关问题
c语言红黑树基本操作,请用代码展示
以下是C语言红黑树的基本操作代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef enum { RED, BLACK } nodeColor;
typedef struct _node {
int key;
nodeColor color;
struct _node *left;
struct _node *right;
struct _node *parent;
} node;
node *root = NULL;
node *createNode(int key) {
node *newNode = (node *)malloc(sizeof(node));
newNode->key = key;
newNode->color = RED;
newNode->left = NULL;
newNode->right = NULL;
newNode->parent = NULL;
return newNode;
}
void rotateLeft(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) {
root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void rotateRight(node *x) {
node *y = x->left;
x->left = y->right;
if (y->right != NULL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
root = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
void fixInsert(node *z) {
while (z->parent != NULL && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
node *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;
rotateLeft(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rotateRight(z->parent->parent);
}
} else {
node *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;
rotateRight(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rotateLeft(z->parent->parent);
}
}
}
root->color = BLACK;
}
void insert(int key) {
node *z = createNode(key);
node *y = NULL;
node *x = root;
while (x != NULL) {
y = x;
if (z->key < x->key) {
x = x->left;
} else {
x = x->right;
}
}
z->parent = y;
if (y == NULL) {
root = z;
} else if (z->key < y->key) {
y->left = z;
} else {
y->right = z;
}
fixInsert(z);
}
void inorderTraversal(node *x) {
if (x != NULL) {
inorderTraversal(x->left);
printf("%d ", x->key);
inorderTraversal(x->right);
}
}
int main() {
insert(10);
insert(20);
insert(30);
insert(15);
insert(18);
insert(25);
insert(40);
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");
return 0;
}
```
以上代码实现了红黑树的插入操作,并且在插入节点后进行了修复操作,以保证红黑树的性质。
红黑树的左旋和右旋操作
红黑树是一种自平衡的二叉搜索树,在插入或删除节点时会进行旋转操作来保持平衡。左旋和右旋是两种基本的旋转操作。
左旋操作是将一个节点的右子节点变为其父节点,同时将该右子节点的左子节点变为该节点的右子节点。这样可以保持二叉搜索树的性质,即右子节点的值大于该节点的值,同时更新相关节点的父节点、左右子节点和子树大小等属性。
右旋操作则是左旋操作的镜像对称操作,将一个节点的左子节点变为其父节点,同时将该左子节点的右子节点变为该节点的左子节点。同样可以保持二叉搜索树的性质,并更新相关属性。
左旋和右旋操作在红黑树中起到调整树结构和保持平衡的作用,通过这些操作可以使得红黑树保持高度平衡,提高了查找、插入和删除等操作的效率。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)