数据结构/C++：红黑树

数据结构/C++：红黑树

    • 概念
    • 实现
      • 基本结构
      • 插入
        • uncle为红色节点
        • uncle为黑色节点
    • 总代码展示

概念

红黑树是一种二叉搜索树，一般的二叉搜索会发送不平衡现象，导致搜索效率下降，于是学者们开始探索如何让二叉搜索树保持平衡，这种树叫做自平衡二叉搜索树。起初学者发明了AVL树，其通过一定算法保持了二叉搜索树的严格平衡，不久后Rudolf Bayer发明了红黑树，红黑树的平衡是较为宽泛的，为了保持平衡，红黑树付出的代价比AVL树更小。因此红黑树被更为广泛的使用，比如Java，C++，python中，使用的自平衡二叉搜索树都是红黑树，而不是AVL树。

如果想了解AVL树，可以看这篇博客：[数据结构/C++：AVL树]

红黑树的要求如下：

红黑树中，最长路径的长度不会超过最短路径的两倍

先解释一下路径的概念：从根走到nullptr。
有不少人认为路径是从根走到叶子节点，这是不正确的。

红黑树用了五条规则来限制一棵树，从而达到以上要求：

  1. 每个节点不是红色就是黑色
  2. 根节点一定是黑色
  3. 不可以出现连续的红色节点（黑色可以连续出现）
  4. 每一条路径都包含相同数目的黑色节点
  5. nullptr视为黑色节点

只要满足以上五个条件，那么这棵树就是一颗红黑树，而且满足最长路径的长度不会超过最短路径的两倍。为什么呢？

五条规则中，我标红了3，4两条规则：

  1. 不可以出现连续的红色节点（黑色可以连续出现）
  2. 每一条路径都包含相同数目的黑色节点

由于每一条路径都必须包含相同数目的黑色节点，现在我们假设一棵红黑树，所有路径的黑色节点数目都是x，那么最短的路径长度就是全为黑色节点，长度为x。
如果想让一条路径变长，那么就只能插入更多的红色节点（因为黑色节点数目相同），但是红色节点又不能连续出现，所以只能是黑红黑红黑红黑红黑红......这样排列，一个黑节点匹配一个红节点，因此最长路径的长度就是黑色节点的两倍2x。
可以发现，红黑树通过这两条核心规则，保证了二叉搜索树的平衡。

比如以下就是一颗红黑树：
在这里插入图片描述

其最短路径为最左侧的路径，长度为2，即两个黑节点。
其最长路径为最右侧的路径，长度为4，即一红一黑排列。

要注意的是：不是所有的红黑树都会出现以上的全黑路径，或者一红一黑路径的，这只是极端情况。

接下来我们通过实现红黑树，来了解红黑树是如何自平衡的：

实现

基本结构

首先我们要在节点中加入一个成员来表示节点的颜色，颜色有红黑和黑色两种状态，这里我使用枚举来区分两者：

enum Colour
{RED,BLACK
};

在某些红黑树的实现中，使用bool值来表示红黑颜色，这也是可以的，但是本博客以枚举来表示颜色。

节点类：

template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Colour _col;
};

_left：左子树
_right：右子树
_parent：父节点
_kv：节点存储的值
_col：该节点的颜色

节点类还需要一个构造函数进行初始化，现在的问题就是：新的节点要初始化为什么颜色？
先来考虑一下：插入红色节点和插入黑色节点，谁对红黑树影响大？
对于一棵红黑树，其所有路径的黑色节点数目都相同，如果我们在某一条路径末尾插入了黑色节点，那么整棵树的所有其它路径都会少一个黑节点。而插入红色节点只影响当前路径，所以新节点应该是红色节点。

构造函数：

RBTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)//初始化为红节点
{}

接着就是红黑树本体，类中只存储一个根节点_root：

template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
private:Node* _root = nullptr;
}

现在我们有了红黑树的基本结构，接下来就实现它的插入操作：

插入

那么我们先写出当基本的二叉搜索树的插入代码逻辑，既然要插入，那么就要先找到合适的位置插入，代码如下：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//保持根为黑节点}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//调整红黑树//......//......//......return true;
}

接下来，我先解析以上代码的逻辑：

if (_root == nullptr)
{_root = new Node(kv);_root->_col = BLACK;//保持根为黑节点
}

如果我们插入节点时，根节点_root为空，说明当前整棵树都为空，那么我们直接插入值作为根节点即可，但是根节点必须是黑色节点，而我们新插入的节点是红色，所以要将其调整为黑色节点。

while (cur)
{if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}
}

以上代码，是在找到合适的插入位置，当key大于当前节点cur->_kv.first < kv.first，那么cur就向左寻找，反之向右寻找。如果当前节点值等于key，那么说明该节点已经存在，返回false代表插入失败。当我们的cur为空指针，说明已经找到了插入的节点，此时跳出循环进行插入。

cur = new Node(kv);if (parent->_kv.first > kv.first)parent->_left = cur;
elseparent->_right = cur;cur->_parent = parent;

到达此处，说明前面已经找到插入的位置了，而parent节点就是插入位置的父亲节点。根据key的大小，来判断插入到左边还是右边，插入完成后，再让新节点的_parent指向parent。

至此我们就完成了插入操作，接下来就要根据不同情况对红黑树进行调整。

对于红黑树的插入，我们需要关注新节点的父亲parent，祖父grandfather，叔叔uncle三个节点：
在这里插入图片描述

  1. 先根据父亲节点的颜色，来判断是否需要调整

父亲节点为黑色：
在这里插入图片描述
新插入的节点默认为红色，所以新插入节点不会影响路径上黑色节点的数目，而parent是黑节点，我们也没有出现连续的红色节点，所以这种情况无需任何调整，直接插入就可以。

父亲节点为红色：
在这里插入图片描述
如果父亲节点为红色，我们就会出现连续的红色节点，这时我们就需要进行调整了

以上两种情况总结为：

当parent为黑色，直接插入
当parent为红色，插入后需要进行调整

当前的代码为：

在这里插入代码片

当parent为红色，我们就需要再根据uncle的颜色，将插入分类两类：uncle为红色以及uncle为黑色。
在这里插入图片描述
值得注意的是：由于parent是红色节点，此时的grandfather一定是黑色节点，因为不能出现连续红色节点
这两种情况的操作不同，我们先看到uncle为红色的情况：

uncle为红色节点

当uncle节点为红色，此时需要进行变色

变色如下：
在这里插入图片描述

由于新插入了红色的cur节点，此时parent与cur出现了连续的红色节点，于是我们将parent改为黑色。但是此时以parent为根的所有路径就会多出一个黑节点，于是把grandfather变为红色，来抵消这个新增的黑节点。但是此时以uncle为根的路径又会少一个黑节点，于是把uncle变黑。

但是我们将grandfather变为了红色，这有可能会影响到上一层节点，比如这样：
在这里插入图片描述
我们把grandfather变红之后，又出现了两个红色节点相连的情况，所以我们要写一个while循环，来反复向上检查。

当前代码如下：

while (parent && parent->_col == RED)//只有parent为红，才更新 (parent可能不存在)
{Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle为黑节点 {//其它处理}}else{Node* uncle = grandfather->_left;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle为黑节点 {//其它处理}}
}_root->_col = BLACK;//在循环内部不判断root情况，统一处理

代码解析：

while (parent && parent->_col == RED)

该代码用于检测cur的parent的颜色，通过我们前面的推导，如果parent为红色才需要调整，因此进入循环的条件之一是parent为红色。另外的parent有可能为nullptr，此时我们要避免访问空指针，所以空指针也不能进循环

if (parent == grandfather->_left)
{  }
else
{ }

这一段代码是在检测parent 节点是grandfather的左子树还是右子树，这将涉及到我们如何找uncle以及下一种情况的调整，此时我们要分类讨论。当parent == grandfather->_left成立，那么uncle就是grandfather的右子树：Node* uncle = grandfather->_right;，反之就是左子树

if (uncle && uncle->_col == RED)
{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;
}

我们找到uncle后，如果uncle是红色，那么直接进行变色操作，把parent和uncle的颜色变为黑色，grandfather变为红色。
随后由于我们的变色操作可能会影响上一层，此时调整节点，进入下一次while循环

在整个while循环外侧，还有一句代码：

_root->_col = BLACK;

这是因为我们在先前的while循环中，有可能出现对_root节点的操作，导致_root的颜色改变，而_root需要保持黑色。如果我们在循环内部，每一次都检测_root有点麻烦了，于是我们直接在每一次调整完节点后，把_root强行矫正为黑色

至此我们就讨论完了uncle为红色节点的情况，接下来我们就讨论uncle为黑色节点：

uncle为黑色节点

由于红黑树中，nullptr也算作黑色节点，所以uncle为黑色分为以下两种情况：

  1. uncle为空指针
  2. uncle不为空指针

图示如下：
在这里插入图片描述

如果 uncle为空指针，那么cur一定是新插入的节点。

因为如果cur不是新插入的节点，那么cur和parent一定有一个原先是黑色节点，不然会出现连续的红色节点。但是如果cur和parent有一个是黑色节点，那么grandfather的左子树就比右子树多出一个黑节点，这就违背了红黑树规则。无论怎样，原先的树都不可能符合规则，所以cur一定是新插入的节点，破坏了规则。

如果 uncle不为空指针，那么cur一定是从黑色节点变成的红色节点（不是新插入的）。

因为如果uncle存在，那么grandfather的右子树就存在一个黑节点，而parent是红节点，所以cur和parent的右子树中都至少有一个黑节点，才能保证每一条路径黑节点数目相同。因此cur原先一定是黑节点，是因为cur下层插入了新节点，然后通过while循环向上走，影响到了当前层。

对于这种uncle为黑色的情况，我们需要通过旋转+变色来维持红黑树。

旋转又分为单旋和双旋：

当cur与parent的关系和parent与grandfather的关系一致时，需要进行单旋

比如我们刚刚的情况：
在这里插入图片描述
cur是parent的左子树，parent是grandfather的左子树，关系一致。
我们需要对其进行右单旋+变色：
在这里插入图片描述
这个旋转的算法在此我就不过多讲解了，可以去AVL树的博客中了解。我重点讲解一下变色和旋转的合理性：

一次插入过程中，走到这一步，说明前面一定经过了uncle为红色的情况，而对uncle为红色的情况进行变色并不会对任何路径的黑色节点数目造成影响，因此目前还是符合黑色节点数目相同规则的。
同为parent的子树，以cur和C为根的路径，黑节点数目相同
同为grandfather的子树，以parent和uncle为根的路径黑节点数目相同
而parent是红色节点，所以cur，C以及uncle为根的路径，黑节点数目都相同

进行单旋，会把c树交给grandfather做子树，而c与uncle为根的路径黑节点数目相同，不违背规则（旋转的合理性）

旋转后，parent作新根，grandfather与cur作为左右子树grandfather为根的路径，整体上就会比以cur为根的路径多出一个黑节点(即grandfather本身)
因此，将grandfather改为红节点，来平衡parent左右子树的黑节点
而红色节点不能连续出现，再把parent改为黑节点

当cur与parent的关系和parent与grandfather的关系不一致时，需要进行双旋

在这里插入图片描述
以上结构中，cur是parent的左子树，parent是grandfather的右子树，关系不一致，要进行双旋。
同样的，讲解一下变色和旋转的合理性：

一次插入过程中，走到这一步，说明前面一定经过了uncle为红色的情况，而对uncle为红色的情况进行变色并不会对任何路径的黑色节点数目造成影响，因此目前还是符合黑色节点数目相同规则的。
同为parent的子树，以cur和A为根的路径，黑节点数目相同
同为cur的子树，以B和C为根的路径，黑节点数目相同
由于cur是红节点，所以以A，B，C为根的路径，黑节点数目相同
相同的手段，由于parent是红节点，所以A与uncle为根的路径的黑节点数目相同
因此A，B，C，uncle为根的路径，黑节点数目都相同

进行双旋，会把C子树交给grandfather做子树，而C与uncle黑节点数目相同，不违背规则也会把B交给parent做子树
A与B黑节点数目相同，不违背规则
旋转后，cur作新根，grandfather与parent作为左右子树grandfather为根的路径，整体上就会比以parent为根的路径多出一个黑节点(grandfather本身)
因此，将grandfather改为红节点，来平衡cur左右子树的黑节点而红色节点不能连续出现，再把cur改为黑节点

以上单旋和双旋的变色，看似复杂，其实最后都是把新根的颜色变为黑色，新根的左右子树变为红色。由于我们旋转后，新根都是黑节点，所以不会影响上层，可以直接跳出循环。

代码如下：

当parent == grandfather->_left：

else//uncle为黑节点 (旋转)
{if (cur == parent->_left){RotateR(grandfather);//右单旋parent->_col = BLACK;//变色grandfather->_col = RED;//变色}else{RotateL(parent);//左右双旋 - 左单旋RotateR(grandfather);//左右双旋 - 右单旋cur->_col = BLACK;//变色grandfather->_col = RED;//变色}break;//旋转后一定平衡
}

当parent == grandfather->_right：

else//uncle为黑节点 (旋转)
{if (cur == parent->_right){RotateL(grandfather);//左单旋parent->_col = BLACK;//变色grandfather->_col = RED;//变色}else{RotateR(parent);//右左双旋 - 右单旋RotateL(grandfather);//右左双旋 - 左单旋cur->_col = BLACK;//变色grandfather->_col = RED;//变色}break;//旋转后一定平衡
}

insert总代码：

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//保持根为黑节点}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;while (parent && parent->_col == RED)//只有parent为红，才更新 (parent可能不存在){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或为黑节点 (旋转){if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后一定平衡}}else{Node* uncle = grandfather->_left;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或为黑节点 (旋转){if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后一定平衡}}}_root->_col = BLACK;//在循环内部不判断root情况，统一处理return true;
}

总代码展示

红黑树总代码：
RBTree.h：

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;//保持根为黑节点}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;while (parent && parent->_col == RED)//只有parent为红，才更新 (parent可能不存在){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或为黑节点 (旋转){if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后一定平衡}}else{Node* uncle = grandfather->_left;//uncle存在且为红节点if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或为黑节点 (旋转){if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;//旋转后一定平衡}}}_root->_col = BLACK;//在循环内部不判断root情况，统一处理return true;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}}size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == nullptr)return 0;;return _Size(root->_left) + _Size(root->_right) + 1;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}//中序void InOrder(){_InOrder(_root);cout << "end" << endl;}int Height(){return _Height(_root);}private://中序void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " - ";_InOrder(root->_right);}//求高度int _Height(Node* root){if (root == nullptr)return 0;return max(Height(root->_left), Height(root->_right)) + 1;}Node* _root = nullptr;
};

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

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

相关文章

【大模型系列】问答理解定位(Qwen-VL/Llama2/GPT)

【大模型系列】问答理解定位(Qwen-VL/Llama2/GPT)

文章目录 1 Qwen-VL(2023, Alibaba)1.1 网络结构1.2 模型训练 2 Llama2(2023, Meta)2.1 网络结构2.1.1 MHA/GQA/MQA2.1.2 RoPE(Rotary Position Embedding, 旋转式位置编码)2.1.3 RMSNorm 2.2 推理2.2.1 集束搜索(beam search)2.2.2 RoPE外推 3 GPT系列(OpenAI) 1 Qwen-VL(2023…
阅读更多...
论文篇00-【历年论文真题考点汇总】与【历年论文原题2009~2023年文字版记录】（2024年软考高级系统架构设计师冲刺知识点总结-论文篇-先导篇）

论文篇00-【历年论文真题考点汇总】与【历年论文原题2009~2023年文字版记录】（2024年软考高级系统架构设计师冲刺知识点总结-论文篇-先导篇）

专栏系列文章推荐： 案例分析篇00-【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】 综合知识篇00-综合知识考点汇总目录 ...... 历年真题论文题考点汇总 历年软考系统架构设计师论文原题（2009-2022年） 因最新的2023年目前仅能搜索到回忆版，等楼主搜集到…
阅读更多...
macbook删除软件只需几次点击即可彻底完成？macbook删除软件没有叉 苹果笔记本MacBook电脑怎么卸载软件? cleanmymac x怎么卸载

macbook删除软件只需几次点击即可彻底完成？macbook删除软件没有叉 苹果笔记本MacBook电脑怎么卸载软件? cleanmymac x怎么卸载

在MacBook的使用过程中&#xff0c;软件安装和卸载是我们经常需要进行的操作。然而&#xff0c;不少用户在尝试删除不再需要的软件时&#xff0c;常常发现这个过程既复杂又耗时。尽管MacOS提供了一些基本的macbook删除软件方法&#xff0c;但很多时候这些方法并不能彻底卸载软件…
阅读更多...
Oracle Primavera P6 数据库升级

Oracle Primavera P6 数据库升级

前言 为了模拟各种P6测试&#xff0c;我常常会安装各种不同版本的p6系统&#xff0c;无论是P6服务&#xff0c;亦或是P6客户端工具Professional&#xff0c;在今天操作p6使用时&#xff0c;无意识到安装在本地的P6 数据库&#xff08;21.12&#xff09;出现了与Professional软…
阅读更多...
Linux系统——Session ID（负载均衡如何保持会话）

Linux系统——Session ID（负载均衡如何保持会话）

目录 一、实验环境搭建 二、部署Nginx代理服务器配置 三、部署后端真是服务器Tomcat配置 四、配置Tomcat的Session ID会话保持 五、测试 此次实验是Tomcat后端服务器如何做Session ID会话保持 一、实验环境搭建 [rootlocalhost ~]#systemctl stop firewalld [rootlocalho…
阅读更多...
【Machine Learning】Suitable Learning Rate in Machine Learning

【Machine Learning】Suitable Learning Rate in Machine Learning

一、The cases of different learning rates: In the gradient descent algorithm model: is the learning rate of the demand, how to determine the learning rate, and what impact does it have if it is too large or too small? We will analyze it through the follow…
阅读更多...
ROS 语音交互（三） tts

ROS 语音交互（三） tts

目录 一、模型选择 二、流程 三、核心代码展示 一、模型选择 科大讯飞超拟人识别 二、流程 超拟⼈合成协议 | 讯飞开放平台文档中心 (xfyun.cn) 三、核心代码展示 # coding: utf-8 import _thread as thread import os import time import base64import base64 import …
阅读更多...
【LeetCode热题100】148. 排序链表（链表）

【LeetCode热题100】148. 排序链表（链表）

一.题目要求 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 二.题目难度 中等 三.输入样例 示例 1&#xff1a; 输入&#xff1a;head [4,2,1,3] 输出&#xff1a;[1,2,3,4] 示例 2&#xff1a; 输入&#xff1a;head [-1,5,3,4,0] 输…
阅读更多...
CSS中如何设置单行或多行内容超出后，显示省略号

CSS中如何设置单行或多行内容超出后，显示省略号

1. 设置超出显示省略号 css设置超出显示省略号可分两种情况&#xff1a; 单行文本溢出显示省略号…多行文本溢出显示省略号… 但使用的核心代码是一样的&#xff1a;需要先使用 overflow:hidden;来把超出的部分隐藏&#xff0c;然后使用text-overflow:ellipsis;当文本超出时…
阅读更多...
NVENC 视频编码器 API 编程指南 ( 中文转译 )

NVENC 视频编码器 API 编程指南 ( 中文转译 )

基于 NVIDIA Kepler™ 和更高版本 GPU 架构的 NVIDIA GPU 包含基于硬件的 H.264/HEVC/AV1 视频编码器&#xff08;以下简称 NVENC&#xff09;。NVENC 硬件采用 YUV/RGB 作为输入&#xff0c;并生成符合H.264/HEVC/AV1 标准的视频比特流。可以使用 NVIDIA 视频编解码器 SDK 中提…
阅读更多...
Git管理远程仓库以及 git push 中遇到的问题

Git管理远程仓库以及 git push 中遇到的问题

Git管理远程仓库 从git 到GitHub问题问题1问题描述解决方法&#xff1a; 问题2问题描述解决方法 从git 到GitHub // 直接push git push //如果不行 //step 1 git remote add origin <URL> //step 2 git remote -v //step 3 git branch //step 4 git push origin main问题…
阅读更多...
吴恩达deeplearning.ai:使用多个决策树随机森林

吴恩达deeplearning.ai:使用多个决策树随机森林

以下内容有任何不理解可以翻看我之前的博客哦&#xff1a;吴恩达deeplearning.ai专栏 文章目录 为什么要使用树集合使用多个决策树(Tree Ensemble)有放回抽样随机森林XGBoost(eXtream Gradient Boosting)XGBoost的库实现何时使用决策树决策树和树集合神经网络 使用单个决策树的…
阅读更多...
redis中List和hash数据类型

redis中List和hash数据类型

list类型是用来存储多个有序的字符串的&#xff0c;列表当中的每一个字符看做一个元素&#xff0c;一个列表当中可以存储一个或者多个元素&#xff0c;redis的list支持存储2^32-1个元素。redis可以从列表的两端进行插入&#xff08;pubsh&#xff09;和弹出&#xff08;pop&…
阅读更多...
[长城杯 2021 院校组]funny_js

[长城杯 2021 院校组]funny_js

[长城杯 2021 院校组]funny_js 审题 根据题名提示为js&#xff0c;再在ida中查看&#xff0c;基本可以确定为quickjs题 QuickJS 是一个快速、灵活且易于嵌入的 JavaScript 引擎&#xff0c;适用于需要在资源受限环境下运行 JavaScript 代码的场景。 工具准备 来到Linux&…
阅读更多...
python入门（二）

python入门（二）

python的安装很方便&#xff0c;我们这里就不再进行讲解&#xff0c;大家可以自己去搜索视频。下面分享一下Python的入门知识点。 执行命令的方式 在安装好python后&#xff0c;有两种方式可以执行命令&#xff1a; 命令行程序文件&#xff0c;后缀名为.py 对于命令行&…
阅读更多...
Golang协程详解

Golang协程详解

一.协程的引入 1.通过案例文章引入并发,协程概念 见:[go学习笔记.第十四章.协程和管道] 1.协程的引入,调度模型&#xff0c;协程资源竞争问题 通过上面文章可以总结出Go并发编程原理: 在一个处理进程中通过关键字 go 启用多个协程&#xff0c;然后在不同的协程中完成不同的子任…
阅读更多...
Tomcat Session 集群 ---------会话保持

Tomcat Session 集群 ---------会话保持

一、 负载均衡、反向代理 环境搭建&#xff1a; nginx服务器192.168.246.7 tomcat 1服务器192.168.246.8 tomcat 2服务器192.168.246.9 7-1 nginx服务器搭建 [rootzzcentos1 ~]#systemctl stop firewalld [rootzzcentos1 ~]#setenforce 0 [rootzzcentos1 ~]#yum install …
阅读更多...
Spark-Scala语言实战（1）

Spark-Scala语言实战（1）

在之前的文章中&#xff0c;我们学习了如何在Linux安装Spark以及Scala&#xff0c;想了解的朋友可以查看这篇文章。同时&#xff0c;希望我的文章能帮助到你&#xff0c;如果觉得我的文章写的不错&#xff0c;请留下你宝贵的点赞&#xff0c;谢谢。 Spark及Scala的安装https:/…
阅读更多...
python基础——字符串的常见操作方法【下标索引，index，count，len，replace，split，strip】

python基础——字符串的常见操作方法【下标索引，index，count，len，replace，split，strip】

&#x1f4dd;前言&#xff1a; 字符串是一种有序的&#xff0c;允许重复字符串存在的&#xff0c;不可修改的序列 这篇文章主要总结一下python中有关字符串的部分相关知识&#xff0c;以及字符串的常见操作方法&#xff1a; 1&#xff0c;和其他序列极其类似的操作方法 2&…
阅读更多...
【C语言】打印素数

【C语言】打印素数

写一个代码&#xff1a;打印100~200之间的素数 素数定义&#xff1a;只能被1和本⾝整除的数字 判断方法&#xff1a; 1&#xff0c;拿2~i-1之间的数字去试除i&#xff0c;需要产生2~i-1之间的数字。 2&#xff0c; 如果2~i-1之间有数字能整除i&#xff0c;则i不是素数&#x…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023