数据结构/C++：二叉搜索树

数据结构/C++：二叉搜索树

    • 概念
    • 模拟实现
      • 结构分析
      • 插入
      • 中序遍历
      • 查找
      • 删除
      • 析构函数
      • 拷贝构造
      • 赋值重载
      • 递归查找
      • 递归插入
      • 递归删除
    • 总代码展示

概念

二叉搜索树（BST - Binary Search Tree）是一种特殊的二叉树，每个顶点最多可以有两个子节点。其遵顼以下规则：

若它的左子树不为空，则左子树上所有节点的至都小于根节点的值
若它的右子树不为空，则右子树上所有节点的至都大于根节点的值
它的左右子树也分别为二叉搜索树

比如以下二叉树就是一个二叉搜索树：
在这里插入图片描述
对于节点59，其左子树节点46小于59，其右子树所有节点79，94，87，96都大于59，其它节点以此类推。

其有两个特性：

  1. 查找数据非常快，每次查找数据，只需要将数据与当前节点比较，然后决定去左子树还是右子树找，如果最后找到了nullptr，那就是不存在。

比如我们在刚才的二叉树中查找87：

请添加图片描述

可以发现：查找一个值，最多只需要树高度次，这也是二叉搜索树得名的原因，很适合搜索值。

  1. 二叉搜索树的中序遍历，得到值是有序的。正是因为二叉搜索树左子树的值都小于根，右子树的值都大于根。中序遍历是 左子树 - 根 - 右子树，所以最后得到的数据就是有序的。

接下来我们模拟实现这个数据结构，使用的语言是C++语言。

模拟实现

结构分析

由于二叉树的每一个节点都要存储：左子树根节点，右子树根节点，当前节点，当前节点的存储值。所以要用一个结构体统一处理：

节点类：

template<class K>
struct BSTreeNode
{
    typedef BSTreeNode<K> Node;

    Node* _root;
    Node* _left;
    Node* _right;
    K _key;
};

然后我们再给节点写一个构造函数：

template<class K>
struct BSTreeNode
{
    typedef BSTreeNode<K> Node;

    Node* _root;
    Node* _left;
    Node* _right;
    K _key;
    
    BSTreeNode(const K& key)
        :_root(nullptr)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_key(key)
    {}
};

对于二叉搜索树的类，我们只需要定义一个指向根节点的_root成员即可：
二叉搜索树类：

template<class K>
class BSTree
{
    typedef BSTreeNode<K> Node;
private:
    Node* _root = nullptr;
};

以上就是一个标准的二叉搜索树结构，也是基本的二叉树结构。接下来我们实现二叉搜索树的各个接口。

插入

想要对二叉搜索树进行节点插入，有两种情况：

  1. 节点值存在：此时不再进行插入
  2. 节点值不存在：进行插入

值得注意的是：如果某一个值不存在于二叉搜索树中，那么插入这个值一定是在nullptr插入。

那么我们第一步就是要找到适合插入的节点，看到以下代码：

bool Insert(const K& key)
{
    Node* cur = _root;

    while (cur)
    {
        if (key < cur->_key)
            cur = cur->_left;
        else if (key > cur->_key)
            cur = cur->_right;
        else
            return false;
    }
}

整个Insert函数的返回值是bool类型的，因为Insert有可能插入失败，此时就要返回值检测是否插入成功。

首先定义一个cur指针，往下查找待插入的节点，只要因为一定在nullptr插入，所以只要cur不为nullptr，就一直找下去。

if (key < cur->_key)如果当前的值key小于当前cur节点的值，那么cur就往左子树插入cur = cur->_left;

else if (key > cur->_key)如果当前的值key大于当前cur节点的值，那么cur就往右子树插入cur = cur->_right;

如果前两个条件不成立，说明当前节点和我们需要插入的值相同，说明原先就有待插入的值，此时返回false

以上代码，我们完成了找到在哪一个节点插入，既然我们需要插入节点，那就需要知道当前节点的父节点，然后再对父节点插入：

bool Insert(const K& key)
{     
    Node* cur = _root;
    Node* parent = nullptr;

    while (cur)
    {
        if (key < cur->_key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (key > cur->_key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;
        }
    }
    return true;
}

相比于一开始的代码，我们在一开始查找节点时，额外定义了一个parent节点，每次cur节点改变时，都保证parent是其父节点，这样我们就可以完成最后的插入操作了。

那么我们要如何对父亲节点进行插入？现在我们确定了待插入的父节点，那么我们要插入到父节点的左子树，还是右子树？

这就涉及到待插入值与父节点的值的判断：如果待插入值小于父节点值，插入左子树；反之插入右子树。

代码如下：

cur = new Node(key);
if (key < parent->_key)
    parent->_left = cur;
else
    parent->_right = cur;

但是我们的代码还是存在一个问题，那就是：我们目前没有处理空树的情况，也就是_root为nullptr。这种情况下我们直接让_root节点存储key值就可以了。

代码如下：

if (_root == nullptr)
{
    _root = new Node(key);
    return true;
}

至此，我们就完成了整个插入操作的接口：

bool Insert(const K& key)
{
    if (_root == nullptr)
    {
        _root = new Node(key);
        return true;
    }
    
    Node* cur = _root;
    Node* parent = nullptr;

    while (cur)
    {
        if (key < cur->_key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (key > cur->_key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;
        }
    }

    cur = new Node(key);
    if (key < parent->_key)
        parent->_left = cur;
    else
        parent->_right = cur;

    return true;
}

中序遍历

中序遍历，对于二叉树而言是一个比较简单的操作，我们看到以下代码：

void InOrder(Node* root)
{
    if (root == nullptr)
        return;

    InOrder(root->_left);
    cout << root->_key << " - ";
    InOrder(root->_right);
}

以上代码，先遍历左子树InOrder(root->_left);，然后输出当前节点的值cout << root->_key << " - ";，再遍历右子树InOrder(root->_right);。是一个很常规的中序遍历，但是存在一个问题：这个函数外部没法传参。

比如说我要遍历某一个二叉搜索树bst：

bst.InOrder(bst._root);

这个调用是存在问题的，那就是_root是私有成员，外部不能把_root作为参数传入中序遍历的接口。此时我们就需要再在外面套一层接口，像这样：

void InOrder()
{
    _InOrder(_root);
}

void _InOrder(Node* root)
{
    if (root == nullptr)
        return;

    _InOrder(root->_left);
    cout << root->_key << " - ";
    _InOrder(root->_right);
}

我们给函数InOrder创建了一个子函数_InOrder，外部无需传参就可以调用InOrder。我们将中序遍历的代码写在了子函数中，而在InOrder内部，再去调用这个子函数 _InOrder(_root);，就可以正常传参了。

查找

想要查找，基本逻辑就是：

当前节点的值小于key，到左子树查找
当前节点的值大于key，到右子树查找
当前节点的值等于key，返回true
如果查找到nullptr，说明不存在，返回false

代码如下：

bool Find(const K& key)
{
    Node* cur = _root;

    while (cur)
    {
        if (key < cur->_key)
            cur = cur->_left;
        else if (key > cur->_key)
            cur = cur->_right;
        else
            return true;
    }

    return false;
}

删除

二叉搜索树的删除是最麻烦的一步，因为删除一个节点会牵扯到大量节点，接下来我们一步一步推导。

首先，既然要删除特定的节点，那么我们就要先查找到该节点。既然要修改该节点，那么也要查找到其父节点，这个思路与前面的插入接口非常相似。代码如下：

bool Erase(const K& key)
{
    Node* cur = _root;
    Node* parent = nullptr;

    while (cur)
    {
        if (key < cur->_key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (key > cur->_key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
        	//删除节点
            return true;
        }
    }

    return false;
}

接下来我们就需要考虑//删除节点这一块的问题了，其会分为很多种情况，我们先看到第一种：

假设我们要删除以下二叉搜索树的79节点：
在这里插入图片描述
这就涉及到两个方向的问题：其父亲节点59应该怎么办？其孩子节点94应该怎么办？

首先，由于79只有一个子树，所以不用考虑两个子树之间会出现节点值不满足二叉搜索树要求的冲突。

对于59节点，其要求右子树的所有值大于59
对于94节点，因为是右子树，其要求父亲节点必须小于94

那么我们是不是可以直接将94节点链接到59节点下方，然后删除79，这样下来，整棵树还满足二叉搜索树的结构。

动图如下：

请添加图片描述

也就是说：只要被删除的节点，有一个子树为nullptr，那么就可以将另外一个子树直接链接到其父节点下。这是第一种情况，代码实现：

 if (cur->_left == nullptr)
 {
     if (cur == parent->_left)
         parent->_left = cur->_right;
     else
         parent->_right = cur->_right;

     delete cur;
 }
 else if (cur->_right == nullptr)
 {
     if (cur == parent->_left)
         parent->_left = cur->_left;
     else
         parent->_right = cur->_left;

     delete cur;
 }
 else
 {
	//其他情况
 }

我们拿出第一段代码解析：

 if (cur->_left == nullptr)
 {
     if (cur == parent->_left)
         parent->_left = cur->_right;
     else
         parent->_right = cur->_right;

     delete cur;
 }

备注：通过前面查找节点，此时的cur已经是待删除的节点，parent是cur父节点。

cur->_left == nullptr ：如果待删除节点cur的左子树为为nullptr，那么我们就要把cur的右子树交给其parent节点

但是我们不知道要交给parent的左子树，还是右子树，此时看cur与parent的关系。如果cur是parent的左子树 if (cur == parent->_left)，那就插入到parent的左子树 parent->_left = cur->_right;，反之插入到右子树parent->_right = cur->_right;。

delete cur;：经过以上操作，我们重新调整了整棵树的结构，现在就可以直接删除cur节点了

但是这个代码还有一个问题，我们看到以下情况：

假设我们要删除以下二叉搜索树的98节点：

在这里插入图片描述
由于98右子树为nullptr，那么其会其可以直接将左子树连接到98的父节上。但是98是_root节点，其没有父节点，parent为空指针，此时程序就会发生错误，所以我们要特殊处理一下删除_root的情况，如果我们要删除_root，且_root有一个子树为nullptr，那么我们直接把另外一棵子树的根节点变成_root即可。

代码如下：

if (cur->_left == nullptr)
{
    if (cur == _root)
    {
        _root = cur->_right;
    }
    else
    {
        if (cur == parent->_left)
            parent->_left = cur->_right;
        else
            parent->_right = cur->_right;
    }

    delete cur;
}
else if (cur->_right == nullptr)
{
    if (cur == _root)
    {
        _root = cur->_right;
    }
    else
    {
        if (cur == parent->_left)
            parent->_left = cur->_left;
        else
            parent->_right = cur->_left;
    }

    delete cur;
}
else
{
	//其他情况
}

现在我们再来讨论另外一种情况：当待删除节点的左右子树都不为空，这该怎么办？

假设我们要删除以下二叉搜索树的36节点：
在这里插入图片描述我们要如何保证删除36之后，整棵树都满足二叉搜索树？这涉及到以下问题：

对于99节点，其要求左子树的所有值小于99
对于27节点，因为是左子树，其要求父亲节点必须大于27
对于81节点，因为是右子树，其要求父亲节点不许小于81

也就是说我们要找到一个值，大于所有左子树节点，小于所有右子树节点，放在36原先的位置。
有两种解决方案：

  1. 取出左子树最大的值替换删除节点
  2. 取出右子树最小的值替换删除节点

我先讲解一下为什么可以这么做：

以取出右子树最小值为例：对于原先的二叉搜索树结构，36节点左侧所有值小于36，右边所有值大于36，所以我们从右子树取出任意一个值，都是大于左子树的值的。但是我们取出的值，又要小于右子树所有节点的，所以要取出右子树的最小值。左子树同理。

那么如何取出右子树最小值？右子树的最小值节点，是第一个左子树为nullptr的节点，也就是最左侧的节点。对于以上代码，从81开始的整棵树，最小值就是49，也是第一个左子树为nullptr的节点。

取出节点后，我们把右子树最小节点rightMin的值交给待删除节点的cur，但是rightMin还有可能有右子树，那么就要把右子树移交给rightMin的父节点。比如以上树中，就是要把49节点的右子树59交给71。

那么我们书写一下代码：

Node* rightMinParent = cur;
Node* rightMin = cur->_right;

while (rightMin->_left)
{
    rightMinParent = rightMin;
    rightMin = rightMin->_left;
}

cur->_key = rightMin->_key;

if (rightMinParent->_left == rightMin)
    rightMinParent->_left == rightMin->_right;
else
    rightMinParent->_right == rightMin->_right;

delete rightMin;

解析：

rightMin代表右子树最小值，rightMinParent代表其父节点

通过while (rightMin->_left)来找第一个左子树为nullptr的节点。

cur->_key = rightMin->_key;：把需要删除的节点cur的值改为rightMin的值，此时二叉搜索树依然符合要求

然后把左子树最小值的节点 rightMin删除掉，if (rightMinParent->_left == rightMin)：如果是父节点的左子树，就把当前 rightMin的右子树移交给父节点左子树rightMinParent->_left == rightMin->_right;。（rightMin下面可能还有子树）反之交给父节点的右子树。

最后删除节点：delete rightMin;

最终效果如下：
请添加图片描述

析构函数

想要删除整棵树，那就需要递归式地删除每一个节点，为了保证树的节点不会错乱，我们最好通过后序遍历删除，代码如下：

~BSTree()
{
    Destroy(_root);
}

void Destroy(Node* root)
{
    if (root == nullptr)
        return;

    Destroy(root->_left);
    Destroy(root->_right);

    delete root;
}

比较简单，不做详解了。

拷贝构造

想要拷贝一棵树出来，我们也需要进行递归式的深拷贝，不过由于要先有父节点，再有子节点，所以要用前序遍历。代码如下：

BSTree(const BSTree<K>& t)
{
    _root = Copy(t._root);
}

Node* Copy(Node* root)
{
    if (root == nullptr)
        return nullptr;

    Node* newRoot = new Node(root->_key);

    newRoot->_left = Copy(root->_left);
    newRoot->_right = Copy(root->_right);

    return newRoot;
}

解析：

Node* newRoot = new Node(root->_key);先创建一个根节点，然后将该节点的左子树连接到拷贝后的左子树：newRoot->_left = Copy(root->_left);，右子树同理。当遇到nullptr就停止递归。

这也是一个二叉树基本操作，不详细讲解了。

赋值重载

代码如下：

BSTree<K>& operator=(BSTree<K> t)
{
    swap(_root, t._root);
    return *this;
}

这是一个比较现代的赋值重载，注意我们在传参时BSTree<K> t不是一个引用，而是一个不同的参数，此时参数t是实参的一份拷贝，是通过拷贝构造创建的，然后我们把这个形参拷贝构造出来的树直接交换给自己： swap(_root, t._root);。这样就相当于通过拷贝构造，完成了一个赋值重载。

接下来，我们再通过递归的模式，来复写几个接口，看看不同的实现方法。

递归查找

首先要通过递归查找到指定值，那就是：

如果key小于当前节点，递归左子树
如果key大于当前节点，递归右子树
如果key等于当前节点，返回true
如果当前节点为nullptr，说明没找到，返回false

代码如下：

bool FindR(const K& key)
{
    return _FindR(_root, key);
}

bool _FindR(Node* root, const K& key)
{
    if (root == nullptr)
        return false;

    if (key < root->_key)
        return _FindR(root->_left, key);
    else if (key > root->_key)
        return _FindR(root->_right, key);
    else
        return true;
}

递归插入

在递归插入前，先通过一般的形式进行查找：

如果key小于当前节点，递归左子树
如果key大于当前节点，递归右子树
如果key等于当前节点，说明节点存在，返回false
如果当前节点为nullptr，则在该节点插入一个新的节点，并返回true

代码如下：

bool InsertR(const K& key)
{
    return _InsertR(_root, key);
}

bool _InsertR(Node*& root, const K& key)
{
    if (root == nullptr)
    {
        root = new Node(key);
        return true;
    }

    if (key < root->_key)
        return _InsertR(root->_left, key);
    else if (key > root->_key)
        return _InsertR(root->_right, key);
    else
        return false;
}

以上代码有一个非常巧妙之处，在于_InsertR的root参数类型为Node*& root，也就是一个指针的引用。我们既然要插入节点，不可避免地要修改父节点的指针，C语言中我们要多传一个标识父节点的参数。但是C++有引用，引用传参传的是变量的别名，此时我们的参数root就是父节点_left或者_right的别名。当我们创造节点后，直接赋值给root，其实就已经完成了插入操作。

递归删除

首先通过递归找到节点：

bool EraseR(const K& key)
{
    return _EraseR(_root, key);
}

bool _EraseR(Node*& root, const K& key)
{
    if (root == nullptr)
        return false;

    if (key < root->_key)
    {
        return _EraseR(root->_left, key);
    }
    else if (key > root->_key)
    {
        return _EraseR(root->_right, key);
    }
    else
    {
    	//删除节点
    }
}

通过递归找到删除节点后，要考虑两种情况：

  1. 待删除节点有一个子树为nullptr
  2. 待删除节点拥有两个子树

先看到第一种：

Node* del = root;

if (root->_left == nullptr)
{
	root = root->_right;
}
else if (root->_right == nullptr)
{
	root = root->_left;
}
else
{
}
delete del;
return true;

备注：此时我们已经通过递归找到了待删除的节点root

基本原理已经讲解过：如果root左子树为nullptr，就把其右子树交给父节点。但是这里的root = root->_right;是在干啥？

注意，我们这的传参是Node*& root，也就是传引用，对于root这个变量而言，他不仅仅是待删除的节点，也是父节点左子树或右子树的别名。所以我们root = root->_right;的过程其实就是在修改父节点的子树。

这个操作有两个很大的好处：

  1. 我们不需要再单独保留父节点parent了，直接通过引用即可修改父节点
  2. 如果删除的节点是根节点，那么root就是_root的别名，也不需要额外处理删除根节点的情况了

当然，这个步骤会导致root被修改，所以我们还要提前保留一份root，方便后续删除。

接下来我们再看到左右子树都不为nullptr的情况：

 else
{
    Node* rightMin = root->_right;

    while (rightMin->_left)
    {
        rightMin = rightMin->_left;
    }

    swap(root->_key, rightMin->_key);

    return _EraseR(root->_right, key);
}

首先要查找rightMin ，也就是 while (rightMin->_left)这个循环。

找到右子树的最小值后，我们就要把它的值交给待删除节点root，即： swap(root->_key, rightMin->_key);

但是这里有一个细节，那就是：反正都要删掉，为什么不直接root->_key, = rightMin->_key这样赋值，然后直接删掉呢？

对于右子树而言，root的值小于右子树的所有值，rightMin的值也小于右子树的所有值，所以通过swap交换后，右子树整棵树依然符合二叉搜索树的结构，而且待删除的key值被转移到了左子树为nullptr的节点，此时我们再通过递归_EraseR(root->_right, key)，就可以按照第一种情况把key节点给删掉。这一步非常巧妙，当然你也可以按照原先的方式删除。

删除代码如下：

bool EraseR(const K& key)
{
    return _EraseR(_root, key);
}

bool _EraseR(Node*& root, const K& key)
{
    if (root == nullptr)
        return false;

    if (key < root->_key)
    {
        return _EraseR(root->_left, key);
    }

    else if (key > root->_key)
    {
        return _EraseR(root->_right, key);
    }
    else
    {
        Node* del = root;

        if (root->_left == nullptr)
        {
            root = root->_right;
        }
        else if (root->_right == nullptr)
        {
            root = root->_left;
        }
        else
        {
            Node* rightMin = root->_right;

            while (rightMin->_left)
            {
                rightMin = rightMin->_left;
            }

            swap(root->_key, rightMin->_key);

            return _EraseR(root->_right, key);
        }
        delete del;
        return true;
    }
}

总代码展示

BinarySearchTree.h：

#pragma once
#include <iostream>
using namespace std;

template<class K>
struct BSTreeNode
{
    typedef BSTreeNode<K> Node;

    Node* _root;
    Node* _left;
    Node* _right;
    K _key;

    BSTreeNode(const K& key)
        :_root(nullptr)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_key(key)
    {}
};

template<class K>
class BSTree
{
    typedef BSTreeNode<K> Node;
public:
    BSTree() = default;

    BSTree(const BSTree<K>& t)
    {
        _root = Copy(t._root);
    }

    Node* Copy(Node* root)
    {
        if (root == nullptr)
            return nullptr;

        Node* newRoot = new Node(root->_key);

        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);

        return newRoot;
    }
        
    ~BSTree()
    {
        Destroy(_root);
    }

    void Destroy(Node* root)
    {
        if (root == nullptr)
            return;

        Destroy(root->_left);
        Destroy(root->_right);

        delete root;
    }

    BSTree<K>& operator=(BSTree<K> t)
    {
        swap(_root, t._root);
        return *this;
    }

    bool Insert(const K& key)
    {
        if (_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }
        
        Node* cur = _root;
        Node* parent = nullptr;

        while (cur)
        {
            if (key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(key);
        if (key < parent->_key)
            parent->_left = cur;
        else
            parent->_right = cur;

        return true;
    }

    bool Erase(const K& key)
    {
        Node* cur = _root;
        Node* parent = nullptr;

        while (cur)
        {
            if (key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                if (cur->_left == nullptr)
                {
                    if (cur == _root)
                    {
                        _root = cur->_right;
                    }
                    else
                    {
                        if (cur == parent->_left)
                            parent->_left = cur->_right;
                        else
                            parent->_right = cur->_right;
                    }

                    delete cur;
                }
                else if (cur->_right == nullptr)
                {
                    if (cur == _root)
                    {
                        _root = cur->_right;
                    }
                    else
                    {
                        if (cur == parent->_left)
                            parent->_left = cur->_left;
                        else
                            parent->_right = cur->_left;
                    }

                    delete cur;
                }
                else
                {
                    Node* rightMinParent = cur;
                    Node* rightMin = cur->_right;

                    while (rightMin->_left)
                    {
                        rightMinParent = rightMin;
                        rightMin = rightMin->_left;
                    }

                    cur->_key = rightMin->_key;

                    if (rightMinParent->_left == rightMin)
                        rightMinParent->_left == rightMin->_right;
                    else
                        rightMinParent->_right == rightMin->_right;

                    delete rightMin;
                }

                return true;
            }
        }

        return false;
    }

    bool Find(const K& key)
    {
        Node* cur = _root;

        while (cur)
        {
            if (key < cur->_key)
                cur = cur->_left;
            else if (key > cur->_key)
                cur = cur->_right;
            else
                return true;
        }

        return false;
    }

    void InOrder()
    {
        _InOrder(_root);
        cout << "end" << endl;
    }

    bool FindR(const K& key)
    {
        return _FindR(_root, key);
    }

    bool InsertR(const K& key)
    {
        return _InsertR(_root, key);
    }

    bool EraseR(const K& key)
    {
        return _EraseR(_root, key);
    }

private:
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_key << " - ";
        _InOrder(root->_right);
    }

    bool _FindR(Node* root, const K& key)
    {
        if (root == nullptr)
            return false;

        if (key < root->_key)
            return _FindR(root->_left, key);
        else if (key > root->_key)
            return _FindR(root->_right, key);
        else
            return true;
    }

    bool _InsertR(Node*& root, const K& key)
    {
        if (root == nullptr)
        {
            root = new Node(key);
            return true;
        }

        if (key < root->_key)
            return _InsertR(root->_left, key);
        else if (key > root->_key)
            return _InsertR(root->_right, key);
        else
            return false;
    }

    bool _EraseR(Node*& root, const K& key)
    {
        if (root == nullptr)
            return false;

        if (key < root->_key)
        {
            return _EraseR(root->_left, key);
        }

        else if (key > root->_key)
        {
            return _EraseR(root->_right, key);
        }
        else
        {
            Node* del = root;

            if (root->_left == nullptr)
            {
                root = root->_right;
            }
            else if (root->_right == nullptr)
            {
                root = root->_left;
            }
            else
            {
                Node* rightMin = root->_right;

                while (rightMin->_left)
                {
                    rightMin = rightMin->_left;
                }

                swap(root->_key, rightMin->_key);

                return _EraseR(root->_right, key);
            }
            delete del;
            return true;
        }
    }

    Node* _root = nullptr;
};

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

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

相关文章

逆向案例四:360k静态和精灵数据动态AES解密，用js的方法

逆向案例四:360k静态和精灵数据动态AES解密，用js的方法

一、360K 网页链接:https://www.36kr.com/p/2672600261670407 页面中有静态的需要解密的内容&#xff0c;确定html包&#xff0c;确定方法 1.1方法步骤 在下方的搜索中输入decrypt(或者关键字window.initialState &#xff0c;进入js文件 在AES.decrypt处打上断点&#xff0…
阅读更多...
【Java项目介绍和界面搭建】拼图小游戏——键盘、鼠标事件

【Java项目介绍和界面搭建】拼图小游戏——键盘、鼠标事件

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收藏 …
阅读更多...
15-Linux部署HBase集群

15-Linux部署HBase集群

Linux部署HBase集群 简介 HBase 是一种分布式、可扩展、支持海量数据存储的 NoSQL 数据库。 和Redis一样&#xff0c;HBase是一款KeyValue型存储的数据库。 不过和Redis设计方向不同 Redis设计为少量数据&#xff0c;超快检索HBase设计为海量数据&#xff0c;快速检索 HB…
阅读更多...
运行Python文件时出现‘utf-8’code can‘t decode byte 如何解决？（如图）

运行Python文件时出现‘utf-8’code can‘t decode byte 如何解决？（如图）

如图 亦或者出现“SyntaxError: Non-UTF-8 code starting with \xbb ” 出现这种问题往往是编码格式导致的&#xff0c;我们可以在py文件中的第一行加入以下代码&#xff1a; # codingutf-8或者 # codinggdk优先使用gbk编码 解释一下常用的两种编码格式&#xff1a; utf-…
阅读更多...
供应链管理（SCM）：界面设计全面扫盲，得供应链者得天下

供应链管理（SCM）：界面设计全面扫盲，得供应链者得天下

大家伙&#xff0c;我是大千UI工场&#xff0c;专注UI分享和项目接单&#xff0c;本期带来供应链系统的设计分享&#xff0c;欢迎大家关注、互动交流。 一、什么是SCM SCM系统是供应链管理&#xff08;Supply Chain Management&#xff09;系统的缩写。供应链管理是指协调和管…
阅读更多...
CSS列表属性

CSS列表属性

CSS列表属性 列表相关的属性&#xff0c;可以作用在 ul、ol、li 元素上。 代码如下&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><title>列表相关属性</title><style>ul {/* …
阅读更多...
MySQL的一行数据是如何存储的？

MySQL的一行数据是如何存储的？

目录 1.COMPACT 行格式长什么样&#xff1f; 例子1&#xff1a;用户设置了主键值&#xff0c;列都是not null的。(默认字符集是utf8mb4,在这种情况下&#xff0c;char(N)类型就不是定长的了&#xff09; 例子2&#xff1a;没有设置主键&#xff0c;也没有唯一索引&#xff0…
阅读更多...
微信小程序-生命周期

微信小程序-生命周期

页面生命周期 onLoad: 页面加载时触发的方法&#xff0c;在这个方法中可以进行页面初始化的操作&#xff0c;如获取数据、设置页面状态等。 onShow: 页面显示时触发的方法&#xff0c;在用户进入页面或从其他页面返回该页面时会调用此方法。可以在此方法中进行页面数据刷新、动…
阅读更多...
浅谈马尔科夫链蒙特卡罗方法（MCMC）算法的理解

浅谈马尔科夫链蒙特卡罗方法（MCMC）算法的理解

1.解决的问题 计算机怎么在任意给定的概率分布P上采样&#xff1f;首先可以想到把它拆成两步&#xff1a; &#xff08;1&#xff09;首先等概率的从采样区间里取一个待定样本x&#xff0c;并得到它的概率为p(x) &#xff08;2&#xff09;然后在均匀分布U[0,1]上取一个值&a…
阅读更多...
基于主从模式的Reactor的仿muduo网络库

基于主从模式的Reactor的仿muduo网络库

&#x1f307;个人主页&#xff1a;平凡的小苏 &#x1f4da;学习格言&#xff1a;命运给你一个低的起点&#xff0c;是想看你精彩的翻盘&#xff0c;而不是让你自甘堕落&#xff0c;脚下的路虽然难走&#xff0c;但我还能走&#xff0c;比起向阳而生&#xff0c;我更想尝试逆风…
阅读更多...
分布式系统中常用的缓存方案

分布式系统中常用的缓存方案

1. 引言 随着互联网应用的发展和规模的不断扩大&#xff0c;分布式系统中的缓存成为了提升性能和扩展性的重要手段之一。本文将介绍几种在分布式系统中常用的缓存方案&#xff0c;包括分布式内存缓存、分布式键值存储、分布式对象存储和缓存网关等。 1.1 缓存在分布式系统中的…
阅读更多...
数据结构c版（3）——排序算法

数据结构c版（3）——排序算法

本章我们来学习一下数据结构的排序算法&#xff01; 目录 1.排序的概念及其运用 1.1排序的概念 1.2 常见的排序算法 2.常见排序算法的实现 2.1 插入排序 2.1.1基本思想&#xff1a; 2.1.2直接插入排序&#xff1a; 2.1.3 希尔排序( 缩小增量排序 ) 2.2 选择排序 2.2…
阅读更多...
WPS如何共享文件和文件夹

WPS如何共享文件和文件夹

1 WPS共享单个文件 用WPS打开要分享的文件&#xff0c;点击右上角的“分享”键&#xff0c;选择上传到云端。 之后点击“创建并分享”&#xff0c;即可分享该文档。 2 WPS创建共享文件夹 2.1 如何共享文件夹 首先打开WPS&#xff0c;点击左上角的首页。在首页栏中&#…
阅读更多...
Sqli-labs靶场第21、22关详解[Sqli-labs-less-21、22]自动化注入-SQLmap工具注入|sqlmap跑base64加密

Sqli-labs靶场第21、22关详解[Sqli-labs-less-21、22]自动化注入-SQLmap工具注入|sqlmap跑base64加密

Sqli-labs-Less-21、22 由于21/22雷同&#xff0c;都是需要登录后&#xff0c;注入点通过Cookie值进行测试&#xff0c;值base64加密 修改注入数据 选项&#xff1a;--tamperbase64encode #自动化注入-SQLmap工具注入 SQLmap用户手册&#xff1a;文档介绍 - sqlmap 用户手册 由…
阅读更多...
SpringBoot+mybatisplus运行单元测试类报错unable to find a @SpringBootConfiguration

SpringBoot+mybatisplus运行单元测试类报错unable to find a @SpringBootConfiguration

这个问题一般是因为启动类目录和测试类不一致&#xff0c;或者没有写使用SpringBootApplication注解的启动类。 1.如果没写启动类&#xff0c;请在与测试类同目录层级&#xff08;注意是在main/java下对应的目录&#xff0c;即测试类在test/java下的目录为com.xxx则启动类需要…
阅读更多...
代码随想录第45天|● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

代码随想录第45天|● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家劫舍III

文章目录 ● 198.打家劫舍思路代码1.dp数组两个变量 ● 213.打家劫舍II思路&#xff1a;代码 ● 337.打家劫舍III思路代码&#xff1a; ● 198.打家劫舍 思路 代码 1.dp数组 class Solution {public int rob(int[] nums) {if(nums.length1)return nums[0];int[] dpnew int[nu…
阅读更多...
6、JavaWeb-Mybatis

6、JavaWeb-Mybatis

P116 Mybatis-入门 Mybatis是一款优秀的持久层框架&#xff0c;用于简化JDBC的开发。 持久层就是三层控制中的Dao层&#xff0c;数据访问层/持久层&#xff0c; P117 Mybatis-入门-快速入门程序 步骤&#xff1a; 创建springboot工程&#xff0c;数据表和实体类 引入mybat…
阅读更多...
Centos7使用man查找命令时，报错No manual entry for xxxx

Centos7使用man查找命令时，报错No manual entry for xxxx

Centos7使用man查找命令时&#xff0c;报错No manual entry for xxxx 在Linux中使用man指令查找指令信息时&#xff0c;报No manual entry for xxxx。 比如使用man指令查找sleep3号手册时&#xff0c;出现以下错误&#xff1a; 这是由于没有安装man-pages这个rpm包导致的&#…
阅读更多...
3、Linux-命令提示符与常用命令（一）

3、Linux-命令提示符与常用命令（一）

目录 一、命令提示符 二、命令格式 三、常用命令&#xff08;一&#xff09; 0、clear&#xff1a;清空终端窗口的内容。 1、ls&#xff1a;列出当前目录或指定目录下的文件和子目录 2、pwd&#xff1a;显示当前所在工作目录的完整路径。 3、cd&#xff1a;切换目录。 …
阅读更多...
Redis的介绍与使用

Redis的介绍与使用

文章目录 Redis简介安装RedisRedis常用命令全局命令String类型数据Hash哈希类型数据List列表类型数据Set集合类型数据SortedSet有序集合类型数据 一些选择题一些选择题 Redis简介 Redis是一款基于键值对的NoSQL数据库&#xff0c;它的值支持多种数据结构&#xff1a; 字符串(s…
阅读更多...
最新文章

Copyright @ 2022~2023