平衡二叉搜索树之 红黑 树的模拟实现【C++】

文章目录

  • 红黑树的简单介绍
    • 定义
    • 红黑树的特性
    • 红黑树的应用
  • 全部的实现代码放在了文章末尾
  • 准备工作
    • 包含头文件
    • 类的成员变量和红黑树节点的定义
  • 构造函数和拷贝构造
  • swap和赋值运算符重载
  • 析构函数
  • find
  • insert【重要】
    • 第一步:按照二叉搜索树的方式插入新节点
    • 第二步:调整颜色,维护红黑树的规则
      • 情况一:新插入的节点的父亲节点颜色为黑
      • 情况二:新插入的节点的父亲节点颜色为红,且叔叔节点不为空且为红
      • 情况三:新插入的节点的父亲节点颜色为红,且叔叔节点为空或者为黑
  • empty
  • size
  • 中序遍历
  • 红黑树和AVL树的比较
  • 全部代码

红黑树的简单介绍

定义

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,只能是Red或Black。
通过对任何一条从根到空节点的路径上各个结点着色方式的限制
红黑树确保没有一条路径会比其他路径长出俩倍,即最长路径的长度最多是最短路径长度的两倍,这样的话就能保证红黑树是接近平衡的树

在这里插入图片描述


红黑树的特性

红黑树通过以下特性来保持树的平衡,保证最长路径的长度最多是最短路径长度的两倍

  1. 节点颜色:每个节点只能是红色或黑色。

  2. 根节点:树的根节点是黑色。

  3. 红色规则:如果一个节点是红色,则它的两个子节点都是黑色(也就是说,一条路径不能有两个连续的红色节点)。

  4. 黑色高度:从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

  5. 空节点:所有的空节点(NIL节点,通常是叶子节点的子节点)都是黑色。

为什么满足上面的特性,红黑树就能保证:最长路径的长度最多是最短路径长度的两倍呢?

其实很好理解

因为
特性2:根节点是黑的

特性4:每条路径的黑色节点个数是相同的

特性5:所有的空节点(NIL节点,通常是叶子节点的子节点)都是黑色。

那么任何一个红黑树可能出现的最短路径就是只有黑色节点的路径,因为每条路径的黑色节点个数是相同的

而任何一个红黑树可能出现的最长路径就是一黑一红交替的路径

为什么?

因为
特性1:每个节点只能是红色或黑色

特性3:每一条路径都不可能出现连续的红色节点

特性4:每条路径的黑色节点个数是相同的
所以最短路径和最长路径的黑色节点个数一样

所以最长也只能是黑红节点交替出现

因此
可能的最短的路径,是全黑节点

可能的最长路径是一黑一红,交替出现的路径,红黑节点个数相同

所以
如果全黑节点的路径长度为h
那么一黑一红交替出现的路径长度最多只能是2*h


红黑树的应用

红黑树是一种高效的自平衡二叉搜索树,因其出色的性能和良好的平衡特性,在计算机科学中被广泛应用。以下是红黑树的一些主要应用场景:

  1. Java 和 C++ 中的集合和数据结构

    • 在 Java 中,红黑树被用于实现 TreeSetTreeMap,分别提供有序集合和有序映射的功能。
    • 在 C++ 中,红黑树是 std::setstd::multisetstd::mapstd::multimap 的底层数据结构。
  2. 数据库索引

    • 红黑树常用于数据库系统中,作为索引结构来提高数据查询和更新的效率。
      通过维持数据的有序性和快速搜索特性,红黑树能够有效地管理大量数据。
  3. 操作系统的内存管理

    • 在操作系统中,红黑树可用于管理内存分配。例如,在 Linux 的虚拟内存管理中,红黑树被用来维护页面分配的信息,确保内存的高效使用。
  4. 文件系统和文件管理

    • 在文件系统中,红黑树可以用来存储文件元数据,比如文件名、大小和修改时间等信息,以便快速检索和排序。
  5. 网络协议和算法

    • 在一些网络协议的实现中,红黑树可以用来管理连接状态或路由表,以实现高效的数据包转发和路由决策。
  6. 图形渲染和游戏开发

    • 在图形渲染和游戏开发中,红黑树可用于管理场景中的物体,通过快速搜索和排序来优化渲染列表。
  7. 科学计算和数据分析

    • 在科学计算和数据分析中,红黑树可以用于管理大量的有序数据,提供快速的搜索和更新操作,这对于时间序列数据的处理尤为重要。

红黑树可以确保数据结构的稳定性和效率,对于处理大量动态变化的数据集合尤为重要。


全部的实现代码放在了文章末尾

准备工作

创建两个文件,一个头文件RBTree.hpp,一个源文件test.cpp

【因为模板的声明和定义不能分处于不同的文件中,所以把成员函数的声明和定义放在了同一个文件RBTree.hpp中】

  1. RBTee.hpp:存放包含的头文件,命名空间的定义,成员函数和命名空间中的函数的定义

  2. test.cpp:存放main函数,以及测试代码


包含头文件

  • iostream:用于输入输出
  • cmath:提供数学函数

类的成员变量和红黑树节点的定义

红黑树类的成员变量只有一个,就是指向红黑树的根节点的指针

在这里插入图片描述

红黑树的节点类:
在这里插入图片描述
为什么红黑树新插入的节点【或者新节点】一定是红色的?

其实就是维护成本的问题:

1.如果新插入的节点为黑色

因为插入之前,这棵树一定是红黑树

所以他的每一条路径上的黑色节点个数都相同

但是因为你新插入了一个黑色的,这一条路径就会比其他路径多一个黑色节点,为了保持红黑树的规则(每一条路径上的黑色节点个数都相同

就得想办法让每一条路径也都增加一个黑色节点,维护成本太高了

2.如果新插入的节点为红色

① 新插入的节点的父亲为黑色,就可以直接结束了,因为满足红黑树的所有规则

②就算新插入的节点的父亲为红色,调整的情况也只有两种,维护成本更低


构造函数和拷贝构造

构造函数没什么好说的,默认构造就行了

RBTree() :_root(nullptr)
{}

拷贝构造:
因为节点都是从堆区new出来的,所以要深拷贝

使用递归实现深拷贝:
因为拷贝构造不能有多余的参数,但是递归函数又必须使用参数记录信息
在这里插入图片描述

然后在拷贝构造里面调用一下这个函数就行了

RBTree(const RBTree& obj)
{_root = Copy(obj._root, nullptr);
}

swap和赋值运算符重载

交换两颗红黑树的本质就是交换两颗数的资源(数据),而它们的资源都是从堆区申请来的,然后用指针指向这些资源
在这里插入图片描述

并不是把资源存储在了红黑树对象中

所以资源交换很简单,直接交换_root指针的指向即可

void Swap(RBTree& obj)
{std::swap(_root, obj._root);
}

赋值运算符重载

RBTree& operator=(RBTree obj)
{this->Swap(obj);return *this;
}

为什么上面的两句代码就可以完成深拷贝呢?
这是因为:

使用了传值传参,会在传参之前调用拷贝构造,再把拷贝构造出的临时对象作为参数传递进去

赋值运算符的左操作数,*this再与传入的临时对象obj交换,就直接完成了拷贝

在函数结束之后,存储在栈区的obj再函数结束之后,obj生命周期结束

obj调用析构函数,把指向的从*this那里交换来的不需要的空间销毁


析构函数

使用递归遍历,把所有从堆区申请的节点都释放掉:
因为析构函数不能有多余的参数,但是递归函数又必须使用参数记录信息
所以再封装一个成员函数,专门用来递归释放:

在这里插入图片描述

然后在拷贝构造里面调用一下这个函数就行了

~RBTree()
{Destroy(_root);_root = nullptr;
}

find

具体流程:
从根节点开始,将目标值(传入的key)与当前节点的key进行比较。
如果目标值小于当前节点值,则在左子树中继续查找;
如果目标值大于当前节点值,则在右子树中继续查找。

这个过程一直进行,直到找到与目标值或者到达空节点为止。

把上述过程转成代码:

在这里插入图片描述


insert【重要】

红黑树就是在二叉搜索树的基础上节点有了颜色,因此红黑树也可以看成是二叉搜索树。

那么AVL树的插入过程可以分为两步:

  1. 先按照二叉搜索树的方式插入新节点

  2. 再调整颜色,维护红黑树的规则


第一步:按照二叉搜索树的方式插入新节点

插入的具体过程如下:

  1. 树为空,则直接新增节点,赋值给二叉搜索树的成员变量_root指针

  2. 树不空,则按照查找(find)的逻辑找到新节点应该插入的位置

  3. 树不空,如果树中已经有了一个节点的key值与要插入的节点的key相同,就插入失败

这个过程一直进行,直到找到与传入的key相等的节点或者到达空节点为止。

把上述过程转成代码:

在这里插入图片描述

第二步:调整颜色,维护红黑树的规则

颜色调整分以下3种情况:

  1. 新插入的节点(cur)的父亲节点(parent)颜色为
  2. 新插入的节点(cur)的父亲节点(parent)颜色为,且叔叔(uncle)节点不为空且为红
  3. 新插入的节点(cur)的父亲节点(parent)颜色为,且叔叔(uncle)节点为空或者为黑

情况一:新插入的节点的父亲节点颜色为黑

此时插入节点,并没有违反任何红黑树规则,所以不需要调整颜色/树的结构

直接结束插入就行


情况二:新插入的节点的父亲节点颜色为红,且叔叔节点不为空且为红

请添加图片描述
(cur为新插入的节点,g是爷爷节点,u是父亲的兄弟节点;a,b,c,d,e是都是符合条件的红黑树)
cur的位置是不固定的
cur也可以是上图的c,d,e
cur的p,g,u相应的改变即可
最主要看的是cur和它的g,p,u的颜色,是否满足情况一

因为插入的节点的颜色为红色,而且它的父亲节点也是红色
那么它就违反了红黑树的第3条规则:同一路径不能出现连续的红色节点
所以必须进行调整。
因为叔叔节点不为空且为红,所以没有严重违反红黑树的规则,只需要对颜色进行调整即可

所以调整方案是:

把p,u都变黑,把g变红:这样就能让连续的红色节点去除,但是g(爷爷接节点)变成红色了,g的父亲节点也可能是红色
所以需要
再把g看作cur继续循环向上调整,再根据新的c,p,u,g节点的颜色,判断是情况一,情况二还是情况三

具体实现代码:
在这里插入图片描述


情况三:新插入的节点的父亲节点颜色为红,且叔叔节点为空或者为黑

请添加图片描述
此时cur的位置也是不固定的
cur也可以是上图的c,d,e
cur的p,g,u相应的改变即可
最主要看的是cur和它的g,p,u的颜色,是否满足情况二

因为插入的节点的颜色为红色,而且它的父亲节点也是红色
那么它就违反了红黑树的第3条规则:同一路径不能出现连续的红色节点
所以必须进行调整。
因为叔叔(uncle)节点为空或者为黑,所以严重违反红黑树的规则,需要调整红黑树的部分结构和调整颜色

所以此时的调整方案是:
先旋转[根据cur,p和g的相对位置,进行左旋,右旋,双旋],再变颜色
【如果不知道旋转是什么的话,可以看我这篇文章:平衡二叉搜索树之 AVL 树的模拟实现【C++】中的怎么旋转】

①单旋:p变黑,g变红
因为单旋之后, p就变成了c,p,g及其子树组成的这棵树的根节点
然后又因为g是黑色,所以他旋转下去的话,
那么c那条路径就会比其他路径少一个黑色节点
所以需要把作为新的根节点的p变黑,这样c那条路径的黑色节点数量才会与其他路径上的相同
但是这样又会让g那条路径比其他的路径多一个黑色节点
所以再把g变红
请添加图片描述
②双旋:c变黑,g变红
因为单旋之后, c就变成了c,p,g及其子树组成的这棵树的根节点
然后的推导就与单旋的类似了

具体代码实现:
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述


empty

bool Empty()
{如果_root为空,那么树就是空的return _root == nullptr;
}

size

使用递归实现二叉搜索树的节点个数统计:
因为我们经常使用的stl的容器的size都是没有参数的,但是递归函数又必须使用参数记录信息
所以再封装一个成员函数,专门用来递归:

在这里插入图片描述

然后再size里面调用一下就行了

size_t Size()
{return _Size(_root);
}

中序遍历

中序遍历的递归函数:
在这里插入图片描述

然后再调用递归函数

void InOrder()
{_InOrder(_root);
}

红黑树和AVL树的比较

红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)

红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,减少了旋转的次数

所以在经常进行增删的结构中性能比AVL树更优,而且红黑树实现比较简单
所以实际运用中红黑树更多


全部代码

#define _CRT_SECURE_NO_WARNINGS#include<iostream>
#include<cmath>
using namespace std;//定义枚举,枚举节点的颜色
enum Color
{RED,//红色BLACK//黑色
};template<class T>
struct RBTreeNode
{T _data;//节点中存储的数据RBTreeNode* _parent;//指向节点的父亲节点RBTreeNode* _left;//指向节点的左孩子RBTreeNode* _right;//指向节点的右孩子Color _color;//存储节点的颜色//默认构造RBTreeNode(const T& data = T()):_data(data),_parent(nullptr),_left(nullptr),_right(nullptr),_color(RED)//新节点的颜色默认是红色{}
};//模板参数T,就是节点中存储的数据的类型
template<class T>
class RBTree
{//给节点类重命名typedef RBTreeNode<T> Node;
private://指向红黑树的根节点的指针Node* _root = nullptr;public:RBTree():_root(nullptr){}RBTree(const RBTree& obj){_root = Copy(obj._root, nullptr);}RBTree& operator=(RBTree obj){this->Swap(obj);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}void Swap(RBTree& obj){std::swap(_root, obj._root);}bool Insert(const T& data){Node* newnode = new Node(data);if (_root == nullptr){_root = newnode;_root->_color = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_data < data){parent = cur;cur = cur->_right;}else if (cur->_data > data){parent = cur;cur = cur->_left;}else{return false;}}if (parent->_data > data){parent->_left = newnode;}else{parent->_right = newnode;}newnode->_parent = parent;cur = newnode;//如果新插入的节点的父节点的颜色是  黑色// 因为已经符合红黑树的规则了,直接结束插入if (parent->_color == BLACK)return true;//直接结束else//否则{Node* grandpa = parent->_parent;//爷爷节点Node* uncle = nullptr;//叔叔节点,即cur的父亲节点的  兄弟节点if (parent == grandpa->_left)//如果parent是左孩子{uncle = grandpa->_right;//那么它的兄弟节点就是右孩子}else//如果parent是右孩子{uncle = grandpa->_left;//那么它的兄弟节点就是左孩子}//情况二:// cur的父亲节点(parent)为红,且叔叔(uncle)节点不为空且为红//只需要继续  循环  向上调整while (parent->_color == RED && uncle && uncle->_color == RED){//调整颜色grandpa->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;//如果调整到根节点,就不需要再向上调整了if (grandpa == _root){//因为根节点只能是黑色//所以把爷爷节点(grandpa)的颜色调成黑色grandpa->_color = BLACK;return true;//直接结束}//重新赋值//继续向上调整cur = grandpa;//让原来的爷爷节点作为curparent = cur->_parent;//重新得出新的父亲节点//如果新的父亲节点为黑,就和刚插入节点时一样// 因为已经符合红黑树的规则了,直接结束插入if (parent->_color == BLACK)return true;//直接结束grandpa = parent->_parent;//重新得出新的爷爷节点//重新得出新的叔叔节点if (parent == grandpa->_left){uncle = grandpa->_right;}else{uncle = grandpa->_left;}}//情况三:// cur的父亲节点(parent)为红,且叔叔(uncle)节点为空或者为黑//就只能根据情况,旋转处理一次if (parent->_color == RED&&uncle == nullptr || uncle->_color == BLACK){if (parent == grandpa->_right && cur == parent->_right)//左单旋{RotateL(grandpa);//调整颜色parent->_color = BLACK;grandpa->_color = RED;}else if (parent == grandpa->_left && cur == parent->_left)//右单旋{RotateR(grandpa);//调整颜色parent->_color = BLACK;grandpa->_color = RED;}else if (parent == grandpa->_left && cur == parent->_right)//左右双旋{RotateL(parent);RotateR(grandpa);//调整颜色cur->_color = BLACK;grandpa->_color = RED;}else if (parent == grandpa->_right && cur == parent->_left)//右左双旋{RotateR(parent);RotateL(grandpa);//调整颜色cur->_color = BLACK;grandpa->_color = RED;}}}return true;}Node* Find(const T& data){Node* cur = _root;while (cur){if (cur->_data < data){cur = cur->_right;}else if (cur->_data > data){cur = cur->_left;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}bool Empty(){return _root == nullptr;}size_t Size(){return _Size(_root);}size_t Height(){return _Height(_root);}bool IsRBTree(){if (_root == nullptr)return true;if (_root->_color != BLACK)return false;int count = 0;Node* cur = _root;while (cur){if (cur->_color == BLACK)count++;cur = cur->_left;}return _IsRBTree(_root, count, 0);}
private:bool _IsRBTree(const Node* root, const int& total, int count){if (root == nullptr){if (count != total)return false;elsereturn true;}if (root->_color == RED && root->_parent->_color == RED)return false;if (root->_color == BLACK)count++;if (_IsRBTree(root->_left, total, count) == false)return false;if (_IsRBTree(root->_right, total, count) == false)return false;return true;}size_t _Height(Node* root){if (root == nullptr)return 0;int left = _Height(root->_left);int right = _Height(root->_right);return left > right ? left + 1 : right + 1;}// 左单旋void RotateL(Node* parent){//记录一下PR和PRLNode* PR = parent->_right;Node* PRL = PR->_left;//把PRL链接在parent的右边parent->_right = PRL;//因为PRL可能为空,为了防止空指针访问,必须判断一下if (PRL != nullptr){//PRL不为空,就把它的父亲节点变成parentPRL->_parent = parent;}//把parent链接在PR的左边PR->_left = parent;//更改PR的父亲节点PR->_parent = parent->_parent;//只有AVL树的根节点的父亲节点为空//所以parent是根节点if (parent->_parent == nullptr){//PR变成了这颗子树的根,替代了原来parent的位置//所以得把AVL树的根节点更新一下_root = PR;}else//如果parent不是根节点{//PR还是要带替parent的位置//所以parent在父亲的左,PR就在左//parent在父亲的右,PR就在右if (parent == parent->_parent->_left)parent->_parent->_left = PR;elseparent->_parent->_right = PR;}//更新一下parent的父亲节点parent->_parent = PR;}// 右单旋void RotateR(Node* parent){//记录一下PL和PLRNode* PL = parent->_left;Node* PLR = PL->_right;//把PLR链接在parent的右边parent->_left = PLR;//因为PLR可能为空,为了防止空指针访问,必须判断一下if (PLR != nullptr){//不为空,就把它的父亲节点变成parentPLR->_parent = parent;}//把parent链接在PL的左边PL->_right = parent;//更新PL的父亲节点PL->_parent = parent->_parent;//只有AVL树的根节点的父亲节点为空//所以parent是根节点if (parent->_parent == nullptr){//PL变成了这颗子树的根,替代了原来parent的位置//所以得把AVL树的根节点更新一下_root = PL;}else//如果parent不是根节点{//PL还是要带替parent的位置//所以parent在父亲的左,PL就在左//parent在父亲的右,PL就在右if (parent == parent->_parent->_left)parent->_parent->_left = PL;elseparent->_parent->_right = PL;}//更新一下parent的父亲节点parent->_parent = PL;}//因为无法直接获取到父亲节点的地址//所以需要传参传进来Node* Copy(Node* root, Node* parent){//空节点不需要拷贝,直接返回nullptrif (root == nullptr)return nullptr;//从堆区申请空间,并初始化节点Node* newnode = new Node(root->_data);//连接上传入函数的父亲节点newnode->_parent = parent;//拷贝颜色newnode->_color = root->_color;//递归拷贝左右子树newnode->_left = Copy(root->_left, newnode);newnode->_right = Copy(root->_right, newnode);return newnode;//返回新节点}//使用后序遍历进行释放void Destroy(Node* root){//空节点if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data << "  ";_InOrder(root->_right);}size_t _Size(Node* root){if (root == nullptr)return 0;int left = _Size(root->_left);int right = _Size(root->_right);return left + right + 1;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/17390.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【设计模式】行为型模式(四):备忘录模式、中介者模式

行为型模式&#xff08;四&#xff09;&#xff1a;备忘录模式、中介者模式 7.备忘录模式&#xff08;Memento&#xff09;7.1 通俗易懂的解释7.2 具体步骤7.3 代码示例7.3.1 定义发起人7.3.2 定义备忘录7.3.3 定义管理者7.3.4 客户端7.3.5 输出 7.4 总结 8.中介者模式&#xf…

Thinkpad E15 在linux下升级 bios

安装xubuntu 24.04后&#xff0c;发现键盘的Fn按键全都无法使用&#xff0c;在Windows环境下是正常的&#xff0c;按说是驱动的问题&#xff0c;网上也有说可以通过升级BIOS解决&#xff0c;所以打算升级看看&#xff0c;升级有风险。 参考&#xff1a; https://blog.stigok.c…

Java学习Day61:薄纱王灵官!(Nginx review)

1.Nginx是什么 Nginx是一款轻量级、高性能&#xff0c;并发性好的HTTP和反向代理服务器 2.功能 2.1反向代理 正向代理是指客户端向代理服务器发送请求&#xff0c;代理服务器代表客户端去访问目标服务器。简单来说&#xff0c;正向代理是客户端的代理&#xff0c;客户端通过…

MATLAB用到的矩阵基础知识(矩阵的乘和矩阵的逆)

1. 矩阵乘法 方法: 设第一个矩阵为 A A A,第二个矩阵为 B B B,则 A A A的第一行乘 B B B的第一列,先想乘再相加,作为目标矩阵的一个元素。 前提条件: 所以我们可以看到矩阵相乘的前提条件:第一个矩阵的列数等于第二个矩阵的行数。否则,我们就无法进行行和列的相乘。 最…

Oracle OCP认证考试考点详解082系列22

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 105. 第105题&#xff1a; 题目 解析及答案&#xff1a; 题目翻译&#xff1a; 关于Oracle数据库中的事务请选择两个正确的陈述&#xf…

【ict基础软件赛道】真题-50%openGauss

题目取自赛前测试链接 OpenGauss安装前使用哪个工具检查环境是否符合安装哪个功能不是gs_guc工具提供的opengauss数据库逻辑复制的特点描述正确的是opengauss的全密态数据库等值查询能力描述正确的是哪个不属于ssh客户端工具opengauss三权分立说法正确的是opengauss wdr snapsh…

MDK5(Keil5)工具设置及技巧

设置&#xff1a; 1点击扳手&#xff08;设置&#xff09; 2文字设置为GB2312简体 3勾选显示空格 4按一下TAB键移动4个空格 修改keil中数字大小及颜色&#xff08;增加对比&#xff09; 勾选全部 1提示结构体 2提示函数参数 3打上几个英文符号后开始提示 4TAB作为填充字符 5打开…

4G模组Air780E对json数据处理的基本方法~

4G模组Air780E在数据传输和处理中扮演着越来越重要的角色。在实际应用中&#xff0c;JSON作为一种轻量级的数据交换格式&#xff0c;被广泛应用于网络数据传输和存储。本文将详细介绍4G模组Air780E对JSON数据处理的基本方法&#xff0c;以帮助开发者更好地利用这一模组进行数据…

学习使用LVGL,依赖官方网址

LVGL Basics — LVGL documentation LVGL基础知识 LVGL是一个开源的图形库&#xff0c;提供创建嵌入式GUI的一切 LVGL数据流 您为每个物理显示面板 创建一个显示器 (lv_display) &#xff0c;在其上创建屏幕小部件&#xff0c;将小部件添加到这些屏幕上。要处理触摸、鼠标、…

【数据库】组合索引生效规则及索引失效

文章目录 索引演示示例组合索引索引失效 索引演示示例 # 创建表结构 CREATE TABLE Employees (EmployeeID INT PRIMARY KEY,FirstName VARCHAR(50),LastName VARCHAR(50),DepartmentID INT,Salary DECIMAL(10, 2),HireDate DATE );# 插入示例数据 INSERT INTO Employees (Empl…

力扣 LeetCode 145. 二叉树的后序遍历(Day6:二叉树)

解题思路&#xff1a; 方法一&#xff1a;递归&#xff08;左右中&#xff09; class Solution {List<Integer> res new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {recur(root);return res;}public void recur(TreeNode ro…

用指针遍历数组

#include<stdio.h> int main() {//定义一个二维数组int arr[3][4] {{1,2,3,4},{2,3,4,5},{3,4,5,6},};//获取二维数组的指针int (*p)[4] arr;//二维数组里存的是一维数组int[4]for (int i 0; i < 3; i){//遍历一维数组for (int j 0; j <4; j){printf("%d &…

[HCTF 2018]Warmup 详细题解

知识点: 目录穿越_文件包含 static静态方法 参数传递引用 mb_strpos函数 mb_substr函数 正文: 页面有一张 滑稽 的表情包,查看一下页面源代码,发现提示 那就访问/source.php 得到源码 <?phphighlight_file(__FILE__);class emmm{public static function checkFil…

从0-1训练自己的数据集实现火焰检测

随着工业、建筑、交通等领域的快速发展,火灾作为一种常见的灾难性事件,对生命财产安全造成了严重威胁。为了提高火灾的预警能力,减少火灾损失,火焰检测技术应运而生,成为火灾监控和预防的有效手段之一。 传统的火灾检测方法,如烟雾探测器、温度传感器等,存在响应时间慢…

小程序20-样式:自适应尺寸单位 rpx

手机设备的宽度逐渐多元化&#xff0c;也就需要开发者开发过程中&#xff0c;去适配不同屏幕宽度的手机&#xff0c;为了解决屏幕适配问题&#xff0c;微信小程序推出了 rpx 单位 rpx&#xff1a;小程序新增的自适应单位&#xff0c;可以根据不同设备的屏幕宽度进行自适应缩放 …

在Ubuntu系统中,默认情况下会安装`apt`作为包管理工具(Advanced Package Tool)

文章目录 方法一&#xff1a;使用命令行检查apt是否存在方法二&#xff1a;尝试运行一个apt命令方法三&#xff1a;查看包列表如果apt没有安装主要功能高级用法注意事项 在Ubuntu系统中&#xff0c;默认情况下会安装 apt作为包管理工具。你可以通过以下几种方法来检查系统中是…

Github 2024-11-16Rust开源项目日报 Top10

根据Github Trendings的统计,今日(2024-11-16统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Rust项目10Go项目1Python项目1Lapce:用 Rust 编写的极快且强大的代码编辑器 创建周期:2181 天开发语言:Rust协议类型:Apache License 2.0St…

C++:基于红黑树封装map和set

目录 红黑树的修改 红黑树节点 红黑树结构 红黑树的迭代器 红黑树Insert函数 红黑树的默认成员函数 修改后完整的红黑树 set、map的模拟实现 set map 测试封装的set和map 红黑树的修改 想要用红黑树封装map和set&#xff0c;需要对之前实现的key-value红黑树进行修…

LeetCode 3240.最少翻转次数使二进制矩阵回文 II:分类讨论

【LetMeFly】3240.最少翻转次数使二进制矩阵回文 II&#xff1a;分类讨论 力扣题目链接&#xff1a;https://leetcode.cn/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-ii/ 给你一个 m x n 的二进制矩阵 grid 。 如果矩阵中一行或者一列从前往后与从后…

在kile 5中一个新工程的创建

这两天博主学习到了在kile5中创建一个工程&#xff0c;当然博主不会忘了小伙伴们的&#xff0c;这就和你们分享。 本次创建以STM32F103C8为例 创建过程&#xff1a; 1首先创建文件 名字随意&#xff0c;但也不要太随意&#xff0c;因为是外国软件&#xff0c;所以多少对中文…