【C语言】红黑树

简介: 【C语言】红黑树

红黑树

1.二叉查找树

首先要了解的是二叉查找树,也称为二叉排序树,优点是在节点均匀分布的情况下,查找效率更高,缺点是,如果节点分布在一侧,查找时间就会约等于数组从头到尾的去查找。

  • 二叉查找树的子树都是二叉查找树。
  • 左子树都小于根节点,右子树都大于根节点

2.平衡二叉查找树

其次,平衡二叉查找树,也称为AVL树,AVL是它的两个发明者的名字组成。它有一套插入,删除的平衡机制,让插入删除后使用相应的平衡算法,再次成为AVL树,这样可以让每次的最坏查找时间接近O(logn),缺点是用于平衡的开销太大。

  • AVL树的子树都是AVL树
  • 左右子树的高度差小于等于1

3.红黑树

红黑树(Red Black Tree)是一种 二叉查找树,它并不是严格意义上的平衡二叉树,因为它有自己的平衡规则,和平衡二叉树规则不一样。它的查找,插入,删除的时间复杂度都是O(logn),n是指树中元素的个数。因此它在查找,插入,删除的最坏情况下运行时间很好。

​ 为什么查找,插入,删除的复杂度都是O(logn),因为红黑树自己有一套规则,去保持红黑树插入删除后还是红黑树。红黑树的平衡次数,相对于普通平衡二叉树少,开销更小。

  • 结点是红色或黑色(一个节点要么是红色,要么是黑色)
  • 根结点是黑色
  • 所有叶子都是黑色。(叶子是NIL结点)
  • 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
  • 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

红黑树用在哪些地方:hashmap,cfs,epoll,定时器,nginx中

使用红黑树,

​ 第一,主要是使用它的(key,value)属性,使用key可以去树上查找相应的value

​ 第二,它是一个二叉排序树,中序遍历是顺序的,可以查一个范围,例如比某个key小的有哪些

1.定义一颗红黑树

typedef int KEY_TYPE;
//定义红黑树节点
typedef struct _rbtree_node
{
   
   
    KEY_TYPE key;
    void *value;
    struct _rbtree_node *right;
    struct _rbtree_node *left;
    struct _rbtree_node *parent;
    unsigned char color;
} rbtree_node;

//定义红黑树
typedef struct _rbtree
{
   
   
    //红黑树的根
    rbtree_node *root;
    //红黑树叶子节点
    rbtree_node *nil;
} rbtree;
AI 代码解读

2. 红黑树旋转

红黑树的插入,删除,会导致不平衡,需要旋转和变色
在这里插入图片描述

2.1 左旋

这里仅仅是旋转,是因为不满足上述5条红黑树性质而进行的旋转。与平衡二叉树的旋转不一样。

因此,只需要考虑旋转点与它的父节点之间的左旋。

// T是树根节点,x是旋转轴节点的父节点
void rbtree_left_rotate(rbtree *T, rbtree_node *x)
{
   
   
    //y为旋转轴节点
    rbtree_node *y = x->right; 

    x->right = y->left;
    if (y->left != T->nil)
    {
   
   
        y->left->parent = x;
    }

    y->parent = x->parent; 
    if (x->parent == T->nil)
    {
   
   
        T->root = y;
    }
    else if (x == x->parent->left)
    {
   
   
        x->parent->left = y;
    }
    else
    {
   
   
        x->parent->right = y;
    }

    y->left = x;
    x->parent = y;
}
AI 代码解读

2.2 右旋

将左旋代码的x改为y,left改为right即可

目录
打赏
0
4
5
0
21
分享
相关文章
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
140 1
|
9月前
|
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现(下)
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现
69 3
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现(上)
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现
69 0
|
9月前
|
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现(下)
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现
53 0
|
9月前
|
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现(上)
从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现
72 4
C语言 红黑树分析与实现
红黑树的资料网上资料很多,对红黑树的定义、性质、以及操作都做了详细的分析,这篇博文也参考了网上的部分文章,不过主要是学习了腾讯课堂-零声king老师的课之后,对红黑树的一些理解。肯定有一些错误的地方,如果觉得不对,可以给我指出
125 0
【C语言程序设计——函数】分数数列求和2(头歌实践教学平台习题)【合集】
函数首部:按照 C 语言语法,函数的定义首部表明这是一个自定义函数,函数名为fun,它接收一个整型参数n,用于指定要求阶乘的那个数,并且函数的返回值类型为float(在实际中如果阶乘结果数值较大,用float可能会有精度损失,也可以考虑使用double等更合适的数据类型,这里以float为例)。例如:// 函数体代码将放在这里函数体内部变量定义:在函数体中,首先需要定义一些变量来辅助完成阶乘的计算。比如需要定义一个变量(通常为float或double类型,这里假设用float。
37 3
【C语言程序设计——函数】分数数列求和1(头歌实践教学平台习题)【合集】
if 语句是最基础的形式,当条件为真时执行其内部的语句块;switch 语句则适用于针对一个表达式的多个固定值进行判断,根据表达式的值与各个 case 后的常量值匹配情况,执行相应 case 分支下的语句,直到遇到 break 语句跳出 switch 结构,若没有匹配值则执行 default 分支(可选)。例如,在判断一个数是否大于 10 的场景中,条件表达式为 “num> 10”,这里的 “num” 是程序中的变量,通过比较其值与 10 的大小关系来确定条件的真假。常量的值必须是唯一的,且在同一个。
20 2
|
1月前
|
【C语言程序设计——函数】递归求斐波那契数列的前n项(头歌实践教学平台习题)【合集】
本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括: 1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。 2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。 3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。 编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果
66 16
【C语言程序设计——函数】回文数判定(头歌实践教学平台习题)【合集】
算术运算于 C 语言仿若精密 “齿轮组”,驱动着数值处理流程。编写函数求区间[100,500]中所有的回文数,要求每行打印10个数。根据提示在右侧编辑器Begin--End之间的区域内补充必要的代码。如果操作数是浮点数,在 C 语言中是不允许直接进行。的结果是 -1,因为 -7 除以 3 商为 -2,余数为 -1;注意:每一个数据输出格式为 printf("%4d", i);的结果是 1,因为 7 除以 -3 商为 -2,余数为 1。取余运算要求两个操作数必须是整数类型,包括。开始你的任务吧,祝你成功!
52 1

热门文章

最新文章