用C++实现一个红黑树
时间: 2023-03-06 07:22:04 浏览: 29
好的,我可以给你一些关于红黑树的信息。
红黑树是一种自平衡二叉搜索树,具有以下性质:
1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点(NIL)是黑色。
4. 每个红色节点的两个子节点都是黑色。
5. 从任一节点到其叶子节点的所有路径都包含相同数目的黑色节点。
以下是一个用 C 语言实现的红黑树的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct _rbtree
{
int key;
char color;
struct _rbtree *left;
struct _rbtree *right;
struct _rbtree *parent;
} rbtree;
#define NIL &sentinel /* all leafs are sentinels */
rbtree sentinel = { 0, 'B', NIL, NIL, NIL };
void insert(rbtree *tree, int key);
void delete(rbtree *tree, int key);
void search(rbtree *tree, int key);
void rbtree_print(rbtree *tree);
int main(int argc, char **argv)
{
rbtree *root = NIL;
insert(root, 5);
insert(root, 10);
insert(root, 15);
insert(root, 20);
insert(root, 25);
rbtree_print(root);
delete(root, 15);
delete(root, 20);
rbtree_print(root);
search(root, 25);
search(root, 30);
return 0;
}
void insert(rbtree *tree, int key)
{
rbtree *current, *parent, *x;
/* find future parent */
current = tree;
parent = 0;
while (current != NIL)
{
if (key == current->key)
return;
parent = current;
current = key < current->key ? current->left : current->right;
}
/* setup new node */
if ((x = malloc (sizeof(*x))) == 0)
return;
x->key = key;