【数据结构】红黑树的插入与验证

文章目录

  • 一、基本概念
    • 1.时代背景
    • 2. 基本概念
    • 3.基本性质
  • 二、实现原理
    • 1. 插入
      • 1.1变色
      • 1.2旋转+变色
        • ①左旋
        • ②右旋
        • ③右左双旋
        • ④左右双旋
    • 2.验证
  • 源码
  • 总结

一、基本概念

1.时代背景

  • 1972年鲁道夫·拜尔(Rudolf Bayer)发明了一种数据结构，这是一种特殊的B树4阶情况。这些树保持了从根到叶的所有路径，节点数量相同，创造了完美平衡的树。但是，它们不是二叉搜索树。拜耳在他的论文中称它们为“对称二元B树”。这是红黑树的起源。

在这里插入图片描述

  • 在1978年的一篇论文“平衡树的二色框架”中，列奥尼达斯·吉巴斯（Leonidas J. Guibas ）和罗伯特·塞奇威克（Robert Sedgewick）从对称的二元B树中推导出了红黑树。选择“红色”是因为它是作者在施乐PARC工作时可用的彩色激光打印机产生的最好看的颜色。吉巴斯的另一个回应说，这是因为他们可以使用红色和黑色的笔来画树。
    在这里插入图片描述
    在这里插入图片描述

第一张为——列奥尼达斯·吉巴斯，第二张为——罗伯特·塞奇威克。

  • 1993年，Arne Andersson引入了右倾树的想法，以简化插入和删除操作。
    在这里插入图片描述
  • 1999年，Chris Okasaki展示了如何使插入操作纯粹功能化。它的平衡功能只需要处理 4 个不平衡情况和一个默认平衡情况。
    在这里插入图片描述

详细请看：维基百科

2. 基本概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍，因而是接近平衡的。

  • 实现平衡的关键：最长路径小于等于最短路径的两倍。

3.基本性质

  1. 每个结点不是红色就是黑色
  2. 根节点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的(如果一个结点是黑色的，则其两个孩子可以是红的也可以是黑的。)
  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点）

强调：2，3，4点是有关联的，且是最关键的3点。

  • 假设根节点如果是红的，那么插入的结点就是只能是黑的（3），那么就违背了（4）。
  • 对于3分析，孩子结点为空，但空节点也被理解成黑色(5)，因此(5)是用来辅助(3)的。
  • 对于4分析，可推理出两个结论——
    1 . 插入结点必须为红色的。
    2 . 满足最长路径小于最短路径的两倍(概念)。对此点可以看做间隔问题，即n个数之间（不算头一个数），有n个间隔，即n个黑结点（不算根节点），之间最多有n个红结点。

二、实现原理

1. 插入

1.1变色

根本逻辑：基于每条路径的黑色结点不变。

第一种变色方式：
在这里插入图片描述
这样变，是不是每条路径的黑色结点数没变呢？

那这样变的前提是什么呢？

  • 黑色结点的左右孩子为红且不为空。

那什么时候发生变色呢？

  • 基于性质3，红色结点的两个孩子必须为黑，但由4我们可以推出每次插入结点必须为红，那这时候我们按照4的原则进行处理，使处理结果符合3即可，怎么处理，就是进行变色。

在这里插入图片描述
此时，parent的右边进行插入新节点，且parent在grandfather的左边。

在这里插入图片描述

此时在parent的右边进行插入，且parent为grandfather的左节点。

  • 总结
  1. 变色的前提是每条路径的黑色结点不变
  2. uncle非空且为红，且parent为红，变grandfather为红，parent与uncle为黑。

继续分析，如果grandfather为红，其父节点是否可能为红呢？

  • 答案是可能的。

因此我们需要继续往上更新：

  1. 更新cur为grandfather
  2. parent为cur的parent

接着分析，如果grandfather为根节点呢？

  • 由于性质2，我们需要再次修改根节点的颜色为黑。

1.2旋转+变色

前面我们分析了一种简单的只需变色的情况，我们下面接着分析另外一种情况。

第二种变色需要在旋转的基础上进行分类讨论，具体情况有四种。

①左旋

在这里插入图片描述

补充：当uncle为黑结点时，parent的左子树不为空且根节点为黑色，cur的左右子树同理，这里不过多分析了，因为具体情况过多分析容易提高理解难度。

  • 开始时parent在grandfather右边，且cur在parent的右边

②右旋

在这里插入图片描述
对uncle的补充同左旋

  • 开始时parent在grandfather左边，且cur在parent的左边

③右左双旋

在这里插入图片描述
对uncle的补充同左旋

  • 开始时parent在grandfather的右边，且cur在parent的左边

④左右双旋

在这里插入图片描述
对uncle的补充同左旋

  • 开始时parent在grandfather的左边，且cur在parent的右边

  • 总结
    根据parent的位置我们可以大致分为两种情况：

  1. parent在grandfather的左边
    在这里插入图片描述

  2. parent在grand的右边
    在这里插入图片描述
    其实不难看出，AVL和红黑树都会进行旋转，只是AVL树旋转后处理的是平衡因子，红黑树旋转后处理的是变色，归根结底终究都是为了让树达到平衡。

  • 核心代码

//判断是否要进行旋转变色
//当父节点为红色说明要进行判断
while (parent && parent->_col == RED)
{//爷爷结点Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//如果uncle存在且为红色{//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上迭代进行分析cur = grandfather;parent = cur->_parent;}else//如果uncle不存在或者为黑色{//旋转if (parent->_left == cur){RotateR(grandfather);parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;parent->_col = grandfather->_col = RED;}break;}}else//grandfather->_right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//变色grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//往上更新cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur){//旋转RotateL(grandfather);//变色parent->_col = BLACK;grandfather->_col = cur->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = parent->_col = RED;}break;}}
}
  • 插入代码
bool insert(const pair<Key, Val>& val)
{//第一步：插入操作//如果根节点为空if (_root == nullptr){_root = new Node(val);_root->_col = BLACK;return true;}else{Node* cur = _root, * parent = _root;while (cur){if (cur->_key > val.first){parent = cur;cur = cur->_left;}else if (cur->_key < val.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(val);if (parent->_key > val.first){parent->_left = cur;}else{parent->_right = cur;}//更新新增结点的_parentcur->_parent = parent;//判断是否要进行旋转变色//当父节点为红色说明要进行判断while (parent && parent->_col == RED){//爷爷结点Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//如果uncle存在且为红色{//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上迭代进行分析cur = grandfather;parent = cur->_parent;}else//如果uncle不存在或者为黑色{//旋转if (parent->_left == cur){RotateR(grandfather);parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;parent->_col = grandfather->_col = RED;}break;}}else//grandfather->_right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//变色grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//往上更新cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur){//旋转RotateL(grandfather);//变色parent->_col = BLACK;grandfather->_col = cur->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = parent->_col = RED;}break;}}}//根节点可能为红色,不管红色还是黑色都弄成黑色_root->_col = BLACK;return true;}
}

2.验证

  • 原理
  1. 根节点不能为红
  2. 每条路径的黑色结点数相同
  3. 每条路径不能出现连续的红色结点。
  • 代码
bool _IsRBTree(Node* root)
{if (root == nullptr)return true;//根节点是黑色的if (root->_col == RED)return false;//各个路径的黑色结点数是相同的，因此设立一个基准进行比较合适，//再对树进行遍历求每个路径的黑色结点的数量，最后比较即可。int benchmark = 0;Node* cur = root;while (cur){if (cur->_col == BLACK)benchmark++;cur = cur->_left;}return Check(root);
}
bool Check(Node* root, int BCount,int benchmark)
{if (root == nullptr){//验证基准值是否等于黑色结点数//只要有一个不是，即不是红黑树。if (BCount != benchmark)return false;return true;}//求每条黑色结点的个数if (root->_col == BLACK)BCount++;//验证性质3，即不能有连续的红色结点。if (root->_col == RED && root->_parent && root->_parent->_col == RED){return false;}return Check(root->_left,BCount,benchmark) && Check(root->_right, BCount, benchmark);
}

源码

#pragma once
#include<iostream>
using namespace std;
namespace MY_STL
{enum Color{RED = 0,BLACK = 1};template<class Key,class Val>struct RBTreeNode{typedef RBTreeNode<Key, Val> Node;RBTreeNode(const pair<Key,Val>& key):_key(key.first),_val(key.second),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED){}Node* _right;Node* _left;Node* _parent;Key _key;Val _val;Color _col;};template<class Key,class Val>class RBTree{typedef RBTreeNode<Key, Val> Node;public:bool insert(const pair<Key, Val>& val){//第一步：插入操作//如果根节点为空if (_root == nullptr){_root = new Node(val);_root->_col = BLACK;return true;}else{Node* cur = _root, * parent = _root;while (cur){if (cur->_key > val.first){parent = cur;cur = cur->_left;}else if (cur->_key < val.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(val);if (parent->_key > val.first){parent->_left = cur;}else{parent->_right = cur;}//更新新增结点的_parentcur->_parent = parent;//判断是否要进行旋转变色//当父节点为红色说明要进行判断while (parent && parent->_col == RED){//爷爷结点Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//如果uncle存在且为红色{//变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上迭代进行分析cur = grandfather;parent = cur->_parent;}else//如果uncle不存在或者为黑色{//旋转if (parent->_left == cur){RotateR(grandfather);RotateCount++;parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);RotateCount+=2;cur->_col = BLACK;parent->_col = grandfather->_col= RED;}break;}}else//grandfather->_right == parent{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//变色grandfather->_col = RED;parent->_col = uncle->_col = BLACK;//往上更新cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur){//旋转RotateL(grandfather);RotateCount++;//变色parent->_col = BLACK;grandfather->_col = cur->_col = RED;}else{RotateR(parent);RotateL(grandfather);RotateCount += 2;cur->_col = BLACK;grandfather->_col = parent->_col = RED;}break;}}}//根节点可能为红色,不管红色还是黑色都弄成黑色_root->_col = BLACK;return true;}}bool IsRBTree(){return _IsRBTree(_root);}size_t Height(){return Height(_root);}private:size_t Height(Node* root){if (root == nullptr){return 0;}int LHeight = Height(root->_left);int RHeight = Height(root->_right);return max(LHeight, RHeight) + 1;}bool _IsRBTree(Node* root){if (root == nullptr)return true;//根节点是黑色的if (root->_col == RED)return false;//各个路径的黑色结点数是相同的，因此设立一个基准进行比较int benchmark = 0;Node* cur = root;while (cur){if (cur->_col == BLACK)benchmark++;cur = cur->_left;}return Check(root,0,benchmark);}bool Check(Node* root, int BCount,int benchmark){if (root == nullptr){//验证基准值是否等于黑色结点数//只要有一个不是，即不是红黑树。if (BCount != benchmark)return false;return true;}//求每条黑色结点的个数if (root->_col == BLACK)BCount++;//验证性质3，即不能有连续的红色结点。if (root->_col == RED && root->_parent && root->_parent->_col == RED){return false;}return Check(root->_left,BCount,benchmark) && Check(root->_right, BCount, benchmark);}void RotateL(Node* parent){//画图分析：//操作的结点有cur,cur_left,ppnodeNode* cur = parent->_right;Node* cur_left = cur->_left;//将parent的右节点改为cur_leftparent->_right = cur_left;//改变cur_left父节点的转向//cur_left可能为空if (cur_left != nullptr){cur_left->_parent = parent;}//将parent链接在cur的左边//为了更新cur的parent需要保存parent的父节点Node* ppnode = parent->_parent;cur->_left = parent;parent->_parent = cur;//ppnode可能为空if (ppnode == nullptr){//需要修改根节点_root = cur;cur->_parent = nullptr;}else{//改变ppnode的指向if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){//操作的结点Node* cur = parent->_left;Node* cur_right = cur->_right;//第一步：将cur_right链接到parent的leftparent->_left = cur_right;//更改cur_right的父节点//注意：cur_right可能为空if (cur_right != nullptr){cur_right->_parent = parent;}//第二步：将parent链接到cur的右结点。//先保存一下parent的父节点Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;//ppnode为空说明需要修改根节点if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}Node* _root = nullptr;public:size_t RotateCount = 0;};
};

总结

 红黑树的理解较AVL树抽象，需要画图分析，不过有了AVL树旋转的基础，这里的难度要下降不少。还是与之前一样，只要图画的好，代码跑不了，所以这里的关键就在于画图。
 总之，今天的分享到这里就结束了，如果感觉有所帮助，不妨点个赞鼓励一下吧！

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

在Photoshop上标小图标的操作记录

在Photoshop上标小图标的操作记录

1、做小图标 收集背景图 的背景的rgb值 把这个rgb值记下来&#xff0c;上面的背景要用。 2、统一图标大小 宽度、高度&#xff0c;都设置成1.52 3、把图标往地图上拖 拖到背景图上&#xff0c;可以用上下左右键调整位置 4、在图片上写字 右键这个&#xff0c;就可以写字了。…
阅读更多...
使用Smartctl脚本输入当前所有磁盘的状态

使用Smartctl脚本输入当前所有磁盘的状态

一、安装Smartctl yum install smartmontools 二、写一个脚本输出当前所有磁盘的状态并且按名称分别写入到文件中 #!/bin/bashfor dev in $(lsblk -l | grep disk | awk {print $1}) doecho "检测磁盘 $dev"smartctl -a /dev/$dev > $dev.smartctl done 以下是这…
阅读更多...
025-从零搭建微服务-文件服务（一）

025-从零搭建微服务-文件服务（一）

写在最前 如果这个项目让你有所收获&#xff0c;记得 Star 关注哦&#xff0c;这对我是非常不错的鼓励与支持。 源码地址&#xff08;后端&#xff09;&#xff1a;https://gitee.com/csps/mingyue 源码地址&#xff08;前端&#xff09;&#xff1a;https://gitee.com/csps…
阅读更多...
c#查看代码的执行耗时( Stopwatch )

c#查看代码的执行耗时( Stopwatch )

我们如果需要看某段代码的执行耗时&#xff0c;会通过如下的方式进行查看 using System.Diagnostics; private void button1_Click(object sender, EventArgs e){Stopwatch sw Stopwatch.StartNew();//sw.Start();StringBuilder sb new StringBuilder();for(int i 0; i <…
阅读更多...
楼顶空地适合建造气膜体育馆吗？

楼顶空地适合建造气膜体育馆吗？

众所周知&#xff0c;传统建筑的荷载太大&#xff0c;出于安全考虑&#xff0c;是不适合继续在楼顶加盖传统结构体育馆的&#xff0c;但是&#xff0c;气膜体育馆作为一种装配式建筑&#xff0c;它是可以在城市高空上建造一个轻盈又新颖独特的全天候气膜馆。 气膜体育馆作为一种…
阅读更多...
Pixillion Pro for Mac：将您的图像转换为艺术佳作

Pixillion Pro for Mac：将您的图像转换为艺术佳作

Pixillion for Mac有着非常强大的图像转换功能和简单的使用方法&#xff0c;帮助你快速完成大批量图像转换的工作&#xff0c;支持一键转换jpeg、jpg、bmp、png、gif、raf、heic等各种格式的图像文件&#xff0c;同时pixillion mac激活版还提供了图像旋转、添加水印、调整图像大…
阅读更多...
原型-设计模式

原型-设计模式

原型设计模式 原型模式应用场景&#xff1a;创建一个对象比较复杂&#xff0c;当前存在一个和需要创建的对象极其相似&#xff0c;我们就可以采用原型模式&#xff0c;在原来的对象上进行一个修改。 修改方案&#xff1a;在原来的基础上进行拷贝&#xff0c;在进行部分的修改。…
阅读更多...
Spring Boot 中的 @CacheEvict 注解使用

Spring Boot 中的 @CacheEvict 注解使用

Spring Boot 中的 CacheEvict 注解 在 Spring Boot 中&#xff0c;缓存是提高应用性能的重要手段。为了更好地管理缓存&#xff0c;Spring Boot 提供了一系列的缓存注解&#xff0c;其中 CacheEvict 注解用于清空缓存。 本文将介绍 CacheEvict 注解的含义、原理以及如何使用。…
阅读更多...
【LeetCode-中等题】34. 在排序数组中查找元素的第一个和最后一个位置

【LeetCode-中等题】34. 在排序数组中查找元素的第一个和最后一个位置

文章目录 题目方法一&#xff1a;二分查找&#xff08;先找到mid&#xff0c;在根据mid确定左右区间&#xff09;方法二&#xff1a;分两次二分查找&#xff0c;一次用于找左区间&#xff0c;一次用于找右区间 题目 方法一&#xff1a;二分查找&#xff08;先找到mid&#xff0…
阅读更多...
Apache HTTPD 多后缀名解析漏洞复现

Apache HTTPD 多后缀名解析漏洞复现

什么是多后缀名解析漏洞加粗样式: 多后缀名解析漏洞&#xff08;Multiple Extension Handling Vulnerability&#xff09;指的是一种安全漏洞&#xff0c;发生在某些操作系统或网络服务中的文件扩展名处理机制中。 这种漏洞的本质是当文件具有多个后缀名&#xff08;例如file.…
阅读更多...
MT4移动端应用指南：随时随地进行交易

MT4移动端应用指南：随时随地进行交易

如今&#xff0c;随着科技的不断发展&#xff0c;我们可以随时随地通过手机进行各种操作&#xff0c;包括进行金融交易。本文将为大家介绍一款优秀的金融交易软件——MT4&#xff08;可在mtw.so/6gwPno这点下&#xff09;移动端应用&#xff0c;并提供详细的使用指南&#xff0…
阅读更多...
合宙Air724UG LuatOS-Air LVGL API控件-加载器(Spinner)

合宙Air724UG LuatOS-Air LVGL API控件-加载器(Spinner)

加载器(Spinner) 示例代码 spinner lvgl.spinner_create(lvgl.scr_act(), nil) lvgl.obj_set_size(spinner, 100, 100) lvgl.obj_align(spinner, nil, lvgl.ALIGN_CENTER, 0, 0) 创建 通过 lvgl.spinner_create 就可创建一个加载器&#xff0c;本身自带动画效果。 spinner …
阅读更多...
同步FIFO的verilog实现（2）——高位扩展法

同步FIFO的verilog实现（2）——高位扩展法

一、前言 在之前的文章中&#xff0c;我们介绍了同步FIFO的verilog的一种实现方法&#xff1a;计数法。其核心在于&#xff1a;在同步FIFO中&#xff0c;我们可以很容易的使用计数来判断FIFO中还剩下多少可读的数据&#xff0c;从而可以判断空、满。 关于计数法实现同步FIFO的详…
阅读更多...
【数据库】MySQL基础知识全解

【数据库】MySQL基础知识全解

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于拓跋阿秀、小林coding等大佬博客进行的&#xff0c;每个知识点的修…
阅读更多...
企业架构LNMP学习笔记30

企业架构LNMP学习笔记30

1、upstream 中server的关键字&#xff1a;语法&#xff1a; upstream中的分发之后的几个关键字&#xff1a; 1&#xff09;backup 备 其他的没有backup标识的都不可用了&#xff0c;才分发到backup&#xff1b; 2&#xff09;down 此条配置&#xff0c;不会被分发到。 syst…
阅读更多...
OmniGraffle Pro for Mac 中文正式版(附注册码) 苹果电脑 思维导图软件

OmniGraffle Pro for Mac 中文正式版(附注册码) 苹果电脑 思维导图软件

OmniGraffle Pro是OmniGraffle的高级版本&#xff0c;它提供了更多的功能和工具&#xff0c;可以帮助用户创建更为复杂和高级的图表和流程图。OmniGraffle Pro支持自定义形状、图形、线条和箭头等&#xff0c;可以让用户创建出更加精细的图表。此外&#xff0c;OmniGraffle Pro…
阅读更多...
字符编码（idea)

字符编码（idea)

File----------settings-------------Editor------------File Encodings
阅读更多...
详细解析如何用“双指针“解题（面试必备，小白一看就会系类）

详细解析如何用“双指针“解题（面试必备，小白一看就会系类）

一、前言 大家在平时的训练和交流中肯定多少都会听过或者见过用"双指针"去快速的解题&#xff0c;那么大家有没有想过&#xff0c;为什么要用"双指针"呢&#xff1f;这里的"双指针"和我们平时了解的指针一样吗&#xff1f; 其实&#xff0c;这里…
阅读更多...
永辉上半年净利润扭亏为盈，是“科技重启”的功劳吗？

永辉上半年净利润扭亏为盈，是“科技重启”的功劳吗？

你有多久没逛超市了&#xff1f;你记忆中的超市是怎样的&#xff1f;现在逛超市的原因又是什么&#xff1f; 其实&#xff0c;对于很多年轻人来说&#xff0c;现在的“快递点”就是“新时代超市”。而传统“超市”“大卖场”被新型超市、电商抢走不少人流量后&#xff0c;逐渐…
阅读更多...
个人主页网站动态星空背景源码（带后台版本）

个人主页网站动态星空背景源码（带后台版本）

动态星空背景个人主页网站源码是一种用于创建个人主页的开源项目。它具有一个令人印象深刻的动态星空背景&#xff0c;为用户提供了一个独特而吸引人的网页设计。此源码还包含一个后台版本&#xff0c;使用户能够轻松管理和更新他们的个人主页内容。 通过该源码&#xff0c;用…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023