数据结构/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;
    else
        parent->_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;
else
	parent->_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;
    else
        parent->_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;
        else
            parent->_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;
            else
                ppNode->_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;
            else
                ppNode->_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;
};

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

字符函数以及字符串函数

字符函数以及字符串函数

1.strlen的使用和模拟实现 • 字符串以 \0 作为结束标志&#xff0c;strlen函数返回的是在字符串中 \0 前⾯出现的字符个数&#xff08;不包 含 \0 )。 • 参数指向的字符串必须要以 \0 结束。 • 注意函数的返回值为size_t&#xff0c;是⽆符号的&#xff08; 易错 &#xff…
阅读更多...
springboot基于Hadoop技术下的校园二手交易系统的设计与实现

springboot基于Hadoop技术下的校园二手交易系统的设计与实现

摘 要 自从新冠疫情爆发以来&#xff0c;各个线下实体越来越难做&#xff0c;线下购物的人也越来越少&#xff0c;随之带来的是一些不必要的浪费&#xff0c;尤其是即将毕业的大学生&#xff0c;各种用品不方便携带走导致被遗弃&#xff0c;造成大量的浪费。本系统目的就是让毕…
阅读更多...
引领人工智能时代的应用安全

引领人工智能时代的应用安全

当生成式人工智能开始展现其编程能力时&#xff0c;开发人员自然会求助于它来帮助他们高效地编写代码。但随着大量人工智能生成的代码首次进入代码库&#xff0c;安全领导者现在正面临着人工智能对整体安全态势的潜在影响。 无论是人工智能被用来将恶意代码插入开源项目&#…
阅读更多...
自定义协议

自定义协议

应用层 有许多现成的协议(HTTP协议做网站必备),也有许多需要程序员自定义的协议. 1.自定义协议 自定义协议: 1.明确传递的信息是什么 2.约定好信息按照什么样的格式来组织成二进制字符串 举个例子: 当我们点外卖时,打开软件,会显示商家列表,列表中有很多项,每一项都包含了一…
阅读更多...
SQLiteC/C++接口详细介绍之sqlite3类（十四）

SQLiteC/C++接口详细介绍之sqlite3类（十四）

返回目录&#xff1a;SQLite—免费开源数据库系列文章目录 上一篇&#xff1a;SQLiteC/C接口详细介绍之sqlite3类&#xff08;十三&#xff09; 下一篇&#xff1a;SQLiteC/C接口详细介绍之sqlite3类&#xff08;十五&#xff09; 43.sqlite3_preupdate_hook sqlite3_preup…
阅读更多...
ClickHouse：一款高效且强大的列式数据库管理系统

ClickHouse：一款高效且强大的列式数据库管理系统

ClickHouse是一款开源的列式数据库管理系统&#xff0c;专为大规模数据仓库和数据分析应用而设计。它允许用户快速地存储和处理海量数据&#xff0c;同时提供了简单易用的SQL接口。本文将介绍ClickHouse的概念、技术原理以及使用案例&#xff0c;并探讨其优势和挑战。 一、引言…
阅读更多...
【leetcode热题】 分数到小数

【leetcode热题】 分数到小数

给定两个整数&#xff0c;分别表示分数的分子 numerator 和分母 denominator&#xff0c;以 字符串形式返回小数 。 如果小数部分为循环小数&#xff0c;则将循环的部分括在括号内。 如果存在多个答案&#xff0c;只需返回 任意一个 。 对于所有给定的输入&#xff0c;保证 …
阅读更多...
数字电子技术实验（五）

数字电子技术实验（五）

单选题 1.基本RS触发器&#xff08;与非门组成&#xff09;的状态是哪一个端口的状态&#xff1f; 答案&#xff1a;C 评语&#xff1a;10分 单选题 2. D触发器&#xff08;74LS 74&#xff09;状态方程的成立条件&#xff1f; A. CP端口高电平。 B. CP端口低电平。 C. C…
阅读更多...
C#操作MySQL从入门到精通(4)——连接MySQL数据库

C#操作MySQL从入门到精通(4)——连接MySQL数据库

前言 我们创建好数据库、建立好数据库的表以后&#xff0c;我们就需要访问数据库了&#xff0c;比如将数据插入数据库的某张表中等一系列操作&#xff0c;在进行这些操作之前我们需要连接上数据库&#xff0c;本文就是详细讲解如何连接MySQL数据库的。 1、使用Navicat Premiu…
阅读更多...
Visual Studio项目模板的创建与使用

Visual Studio项目模板的创建与使用

Visual Studio项目模板的创建、使用、删除 创建模板项目模板的使用模板的删除 创建模板 点击项目&#xff0c;点击导出模板 选择你要创建哪个项目的项目模板&#xff0c;点击下一步 输入你的模板名称并添加模板说明&#xff0c;方便记忆 项目模板的使用 点击创建新项目 输入刚刚…
阅读更多...
Linux-centos如何搭建yum源仓库

Linux-centos如何搭建yum源仓库

1.本地搭建&#xff08;无需连接外网&#xff09; 1.1检查网络配置&#xff0c;及网络连接 打开虚拟机&#xff0c;点击【编辑——虚拟网络编辑器】 点击【仅主机模式】查看子网段是否和局内IP匹配 进入局内&#xff0c;查看网络IP是否在你上述设置的网段内&#xff0c;如果不…
阅读更多...
MyBatis plus自动生成代码

MyBatis plus自动生成代码

1.pom文件配置 <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.3</version> </dependency> <dependency><groupId>com.baomidou</groupId>…
阅读更多...
VLC抓取m3u8视频

VLC抓取m3u8视频

前言 最近想看一些网络视频&#xff0c;但是很多时候网页上是m3u8推流的&#xff0c;如果在线看&#xff0c;速度又慢&#xff0c;所以就想下载下来&#xff0c;就想到了VLC的推流&#xff0c;转换能力&#xff0c;查阅资料&#xff0c;加上实践&#xff0c;总结心得。 设置中…
阅读更多...
＜Linux＞ 线程的同步与互斥

＜Linux＞ 线程的同步与互斥

目录 前言&#xff1a; 一、资源共享问题 &#xff08;一&#xff09;多线程并发访问 &#xff08;二&#xff09;临界资源与临界区 &#xff08;三&#xff09;“锁” 是什么 二、多线程抢票场景 &#xff08;一&#xff09;并发抢票 &#xff08;二&#xff09;并发访…
阅读更多...
flink1.18.0 自定义函数 接收row类型的参数

flink1.18.0 自定义函数 接收row类型的参数

比如sql中某字段类型 array<row<f1 string,f2 string,f3 string,f4 bigint>> 现在需要编写 tableFunction 需要接受的参数如上 解决方案 用户定义函数|阿帕奇弗林克 --- User-defined Functions | Apache Flink
阅读更多...
React 实现下拉刷新效果

React 实现下拉刷新效果

简介 本文基于react实现下拉刷新效果&#xff0c;在下拉的时候会进入loading状态。 实现效果 效果如上图所示&#xff0c;在下拉到底部时候&#xff0c;会出现loading条&#xff0c;在处理完成后loading条消失。 具体代码 布局 & 逻辑 import {useRef, useState} from …
阅读更多...
基于Java+Springmvc+vue+element实现高校心理健康系统详细设计和实现

基于Java+Springmvc+vue+element实现高校心理健康系统详细设计和实现

基于JavaSpringmvcvueelement实现高校心理健康系统详细设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐…
阅读更多...
Docker 笔记（五）--链接

Docker 笔记（五）--链接

这篇笔记记录了Docker 的Link。 官方文档&#xff1a; Legacy container links - Communication across links 目录 参考Legacy container linksConnect using network port mappingConnect with the linking systemThe importance of naming Communication across linksEnviro…
阅读更多...
java多线程学习（二）

java多线程学习（二）

多线程学习&#xff08;一&#xff09;&#xff1a;http://t.csdnimg.cn/o3ygn 目录 一、线程安全 二、线程同步 三、加锁的实现方式一&#xff1a;同步代码块 四、加锁的实现方式二&#xff1a;同步方法 五、同步方法和同步代码块的比较 六、加锁的实现方式三&#xff…
阅读更多...
zookeeper快速入门一：zookeeper安装与启动

zookeeper快速入门一：zookeeper安装与启动

本文是zookeeper系列之快速入门中的第一篇&#xff0c;欢迎大家观看与指出不足。 写在前面&#xff1a; 不影响教程&#xff0c;笔者安装zookeeper用的是WSL(windows下的linux子系统&#xff09;&#xff0c;当然你想直接在windows上用zookeeper也是可以的。 如果你也想用ws…
阅读更多...
最新文章

Copyright @ 2022~2023