AVL树、红黑树

数据结构、算法总述：数据结构/算法 C/C++-CSDN博客

AVL树

定义

  1. 空二叉树是一个 AVL 树
  2. 如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 \left | h(ls)-h(rs) \right |\leq 1，h 是其左右子树的高度
  3. 树高为 O\left ( log\ n \right )

平衡因子：右子树高度 - 左子树高度

创建节点

由于 AVL 树的相关操作需要获取节点高度，因此我们需要为节点类添加 height 变量：

/* AVL 树节点类 */
struct TreeNode {
    int val{};          // 节点值
    int height = 0;     // 节点高度
    TreeNode *left{};   // 左子节点
    TreeNode *right{};  // 右子节点
    TreeNode() = default;
    explicit TreeNode(int x) : val(x){}
};

 “节点高度”是指从该节点到它的最远叶节点的距离，即所经过的“边”的数量。需要特别注意的是，叶节点的高度为 0 ，而空节点的高度为 −1 。我们将创建两个工具函数，分别用于获取和更新节点的高度：

/* 获取节点高度 */
int height(TreeNode *node) {
    // 空节点高度为 -1 ，叶节点高度为 0
    return node == nullptr ? -1 : node->height;
}

/* 更新节点高度 */
void updateHeight(TreeNode *node) {
    // 节点高度等于最高子树高度 + 1
    node->height = max(height(node->left), height(node->right)) + 1;
}

节点的平衡因子（balance factor）定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为 0 。我们同样将获取节点平衡因子的功能封装成函数，方便后续使用：

/* 获取平衡因子 */
int balanceFactor(TreeNode *node) {
    // 空节点平衡因子为 0
    if (node == nullptr)
        return 0;
    // 节点平衡因子 = 左子树高度 - 右子树高度
    return height(node->left) - height(node->right);
}

旋转 

我们将平衡因子绝对值 >1 的节点称为“失衡节点”。根据节点失衡情况的不同，旋转操作分为四种：右旋、左旋、先右旋后左旋、先左旋后右旋。

右旋

/* 右旋操作 */
TreeNode *rightRotate(TreeNode *node) {
    TreeNode *child = node->left;
    TreeNode *grandChild = child->right;
    // 以 child 为原点，将 node 向右旋转
    child->right = node;
    node->left = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}
左旋

/* 左旋操作 */
TreeNode *leftRotate(TreeNode *node) {
    TreeNode *child = node->right;
    TreeNode *grandChild = child->left;
    // 以 child 为原点，将 node 向左旋转
    child->left = node;
    node->right = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}
先左旋后右旋

仅使用左旋或右旋都无法使子树恢复平衡。此时需要先对 child 执行“左旋”，再对 node 执行“右旋”。

先右旋后左旋

旋转的选择

判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号，来确定旋转方式： 

失衡节点的平衡因子子节点的平衡因子旋转方式
>1≥0右旋
>1<0先左旋后右旋
<-1≤0左旋
<-1>0先右旋后左旋
/* 执行旋转操作，使该子树重新恢复平衡 */
TreeNode *rotate(TreeNode *node) {
    // 获取节点 node 的平衡因子
    int _balanceFactor = balanceFactor(node);
    // 左偏树
    if (_balanceFactor > 1) {
        if (balanceFactor(node->left) >= 0) {
            // 右旋
            return rightRotate(node);
        } else {
            // 先左旋后右旋
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }
    // 右偏树
    if (_balanceFactor < -1) {
        if (balanceFactor(node->right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // 先右旋后左旋
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    // 平衡树，无须旋转，直接返回
    return node;
}

基础操作

插入

在 AVL 树中插入节点后，从该节点到根节点的路径上可能会出现一系列失衡节点。因此，我们需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡。

/* 插入节点 */
void insert(int val) {
    root = insertHelper(root, val);
}

/* 递归插入节点（辅助方法） */
TreeNode *insertHelper(TreeNode *node, int val) {
    if (node == nullptr)
        return new TreeNode(val);
    /* 1. 查找插入位置并插入节点 */
    if (val < node->val)
        node->left = insertHelper(node->left, val);
    else if (val > node->val)
        node->right = insertHelper(node->right, val);
    else
        return node;    // 重复节点不插入，直接返回
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}
删除

在二叉搜索树的删除节点方法的基础上，需要从底至顶执行旋转操作，使所有失衡节点恢复平衡。

/* 删除节点 */
void remove(int val) {
    root = removeHelper(root, val);
}

/* 递归删除节点（辅助方法） */
TreeNode *removeHelper(TreeNode *node, int val) {
    if (node == nullptr)
        return nullptr;
    /* 1. 查找节点并删除 */
    if (val < node->val)
        node->left = removeHelper(node->left, val);
    else if (val > node->val)
        node->right = removeHelper(node->right, val);
    else {
        if (node->left == nullptr || node->right == nullptr) {
            TreeNode *child = node->left != nullptr ? node->left : node->right;
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == nullptr) {
                delete node;
                return nullptr;
            }
            // 子节点数量 = 1 ，直接删除 node
            else {
                delete node;
                node = child;
            }
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            TreeNode *temp = node->right;
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            int tempVal = temp->val;
            node->right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}
查找

与二叉搜索树一致

AVL树总代码

AVLTree.h

#include <iostream>
#include <assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
    AVLTreeNode* _left;
    AVLTreeNode* _right;
    AVLTreeNode* _parent;
    int _bf; // balance factor
    pair<K, V> _kv;

    AVLTreeNode(const pair<K, V>& kv)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _bf(0)
        , _kv(kv)
    {}
};

template<class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
        }

        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)//最坏情况一直更新到root，此时parent为nullptr
        {
            if (cur == parent->_left)//更新平衡因子
                parent->_bf--;
            else
                parent->_bf++;

            if (parent->_bf == 0)
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)//向上查找，检测是否出现不平衡
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                //旋转
                if (parent->_bf == 2 && cur->_bf == 1)//2，1说明右边子树深度阶梯式增加，所以往左旋转
                    RotateL(parent);//左单旋
                else if (parent->_bf == -2 && cur->_bf == -1)//-2，-1说明左边子树深度阶梯式增加，所以往右旋转
                    RotateR(parent);//右单旋
                else if (parent->_bf == -2 && cur->_bf == 1)//-2, 1说明左边子树中间深，先左单旋提高中间节点，再右单旋提高中间节点
                    RotateLR(parent);
                else if (parent->_bf == 2 && cur->_bf == -1)//2, -1说明右边子树中间深，先右单旋提高中间节点，再左单旋提高中间节点
                    RotateRL(parent);
                else
                    assert(false);

                break;
            }
            else //说明插入前AVL出现了问题，直接报错
            {
                assert(false);
            }
        }

        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;
        }

        parent->_bf = 0;
        subR->_bf = 0;
    }

    //右单旋
    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;
        }

        parent->_bf = 0;
        subL->_bf = 0;
    }

    //左右双旋
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        int bf = subLR->_bf;
        RotateL(parent->_left);
        RotateR(parent);

        if (bf == -1)
        {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        }
        else if (bf == 1)
        {
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        }
        else if (bf == 0)
        {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    //右左双旋
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);

        if (bf == -1)
        {
            subR->_bf = 1;
            subRL->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == 0)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }
    
    //中序
    void InOrder()
    {
        _InOrder(_root);
        cout << "end" << endl;
    }
    
private:
    //中序
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_kv.first << " - ";

        _InOrder(root->_right);
    }
    
    Node* _root = nullptr;
};

应用

  • 组织和存储大型数据，适用于高频查找、低频增删的场景。 

红黑树

红黑树是一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 ("RED" or "BLACK")，用于确保树在插入和删除时保持平衡

性质

  1. 节点为红色或黑色
  2. 根节点必须为黑色
  3. NIL 节点（空叶子节点）为黑色
  4. 红色节点的子节点为黑色
  5. 从根节点到 NIL 节点的每条路径上的黑色节点数量相同

创建节点

enum Colour
{
    RED,
    BLACK
};

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节点为红色

 如果父亲节点为红色，我们就会出现连续的红色节点，这时我们就需要进行调整了

当parent为红色，我们就需要再根据uncle的颜色，将插入分类两类：uncle为红色以及uncle为黑色 

注意：由于parent是红色节点，此时的grandfather一定是黑色节点

2.根据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有可能为NIL，此时我们要避免访问空指针，所以空指针也不能进循环

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循环

_root->_col = BLACK;

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

uncle节点为黑色

又因为红黑树中，NIL也算作黑色节点，所以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为黑色的情况，我们需要通过旋转+变色来维持红黑树。

旋转又分单旋和双旋（同AVL树）

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

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

 

当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

#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;
};

应用

  • 作为map&set的底层

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

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

相关文章

图片标签 以及 常见的图片的格式

图片标签 以及 常见的图片的格式

1.图片的基本使用 2.图片的常见格式 3.bmp格式
阅读更多...
易我分区大师18.5发布上线：全方位提升您的磁盘管理体验

易我分区大师18.5发布上线：全方位提升您的磁盘管理体验

近期&#xff0c;易我分区大师18.5版本正式发布上线&#xff01; 新版本在原有基础上进行了升级和优化&#xff0c;不仅继承了前版本的强大功能&#xff0c;还新增了C盘数据迁移、清除Windows PIN码以及蓝屏问题助手等实用功能&#xff0c;帮助用户更轻松、更高效地管理电脑磁…
阅读更多...
HTML的使用（中）

HTML的使用（中）

文章目录 前言一、HTML表单是什么&#xff1f;二、HTML表单的使用 &#xff08;1&#xff09;<form>...</form>表单标记&#xff08;2&#xff09;<input>表单输入标记总结 前言 在许多网页平台上浏览&#xff0c;大多逃不了登录账号。此时在网页中填写的用户…
阅读更多...
数据库SQL编写规范-SQL书写规范整理（SQL语句书写规范全解-Word原件）

数据库SQL编写规范-SQL书写规范整理（SQL语句书写规范全解-Word原件）

编写本文档的目的是保证在开发过程中产出高效、格式统一、易阅读、易维护的SQL代码。 1 编写目 2 SQL书写规范 3 SQL编写原则 软件全套精华资料包清单部分文件列表&#xff1a; 工作安排任务书&#xff0c;可行性分析报告&#xff0c;立项申请审批表&#xff0c;产品需求规格说…
阅读更多...
吴恩达深度学习笔记：优化算法 (Optimization algorithms)2.3-2.5

吴恩达深度学习笔记：优化算法 (Optimization algorithms)2.3-2.5

目录 第二门课: 改善深层神经网络&#xff1a;超参数调试、正 则 化 以 及 优 化 (Improving Deep Neural Networks:Hyperparameter tuning, Regularization and Optimization)第二周&#xff1a;优化算法 (Optimization algorithms)2.3 指数加权平均数&#xff08;Exponential…
阅读更多...
unity 学习笔记

unity 学习笔记

一、 事件顺序 gameObjet Instantiate gameObjet.自定义函数 gameObjet.Start 二、预设体使用 例子&#xff1a;Button 点击创建 预设体 BagPanel
阅读更多...
【MIT6.S081】Lab7: Multithreading(详细解答版)

【MIT6.S081】Lab7: Multithreading(详细解答版)

实验内容网址：https://xv6.dgs.zone/labs/requirements/lab7.html 本实验的代码分支：https://gitee.com/dragonlalala/xv6-labs-2020/tree/thread2/ Uthread: switching between threads 关键点：线程切换、swtch 思路： 本实验完成的任务为用户级线程系统设计上下文切换机制…
阅读更多...
windows平台Visual Studio2022编译libuvc调试usb摄像头

windows平台Visual Studio2022编译libuvc调试usb摄像头

一、下载libuv源码&#xff0c;源码地址&#xff1a;libuvc/libuvc: a cross-platform library for USB video devices (github.com) 二、新建vs工程&#xff0c;将libuvc源码中的include和src目录下的文件拷贝到工程中。 1.include源码修改 ①libuvc头文件修改 将 #includ…
阅读更多...
自动删除 PC 端微信缓存数据，包括从所有聊天中自动下载的大量文件、视频、图片等数据内容，解放你的空间。

自动删除 PC 端微信缓存数据，包括从所有聊天中自动下载的大量文件、视频、图片等数据内容，解放你的空间。

Clean My PC Wechat 自动删除 PC 端微信自动下载的大量文件、视频、图片等数据内容&#xff0c;解放一年几十 G 的空间占用。 该工具不会删除文字的聊天记录&#xff0c;请放心使用。请给个 Star 吧&#xff0c;非常感谢&#xff01; 现已经支持 Windows 系统中的所有微信版本…
阅读更多...
Java进阶11 IO流、功能流

Java进阶11 IO流、功能流

Java进阶11 IO流-功能流 一、字符缓冲流 字符缓冲流在源代码中内置了字符数组&#xff0c;可以提高读写效率 1、构造方法 方法说明BufferedReader(new FileReader(文件路径))对传入的字符输入流进行包装BufferedWriter(new FileWriter(文件路径))对传入的字符输出流进行包装…
阅读更多...
基于Springboot+Vue的Java项目-宠物商城网站系统开发实战(附演示视频+源码+LW)

基于Springboot+Vue的Java项目-宠物商城网站系统开发实战(附演示视频+源码+LW)

大家好&#xff01;我是程序员一帆&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &am…
阅读更多...
暗区突围TWITCH掉宝领测试资格后，steam激活显示是无效激活码

暗区突围TWITCH掉宝领测试资格后，steam激活显示是无效激活码

自《暗区突围》测试启动以来&#xff0c;吸引了大量玩家关注&#xff0c;特别是通过在Twitch平台上观看直播即可获得测试资格的活动&#xff0c;更是掀起了热潮。然而&#xff0c;部分玩家在成功获得激活码后&#xff0c;在Steam平台激活时遭遇了“无效激活码”的问题。本文将提…
阅读更多...
勒索软件漏洞？在不支付赎金的情况下解密文件

勒索软件漏洞？在不支付赎金的情况下解密文件

概述 在上一篇文章中&#xff0c;笔者对BianLian勒索软件进行了研究剖析&#xff0c;并且尝试模拟构建了一款针对BianLian勒索软件的解密工具&#xff0c;研究分析过程中&#xff0c;笔者感觉构建勒索软件的解密工具还挺有成就感&#xff0c;因此&#xff0c;笔者准备再找一款…
阅读更多...
排序-归并排序（merge sort）

排序-归并排序（merge sort）

归并排序&#xff08;Merge Sort&#xff09;是一种分而治之的算法&#xff0c;它将原始数组分成越来越小的子数组&#xff0c;直到每个子数组只有一个元素&#xff0c;然后将这些子数组两两合并&#xff0c;过程中保持排序状态&#xff0c;最终合并成一个完全有序的数组。归并…
阅读更多...
windows和Linux卸载移动磁盘

windows和Linux卸载移动磁盘

文章目录 Linux卸载磁盘target is busy.window卸载磁盘打开事件查看器 Linux卸载磁盘target is busy. #查看有哪些进程访问挂载点 lsof /media/lei/repository/#杀死进程 pkill node window卸载磁盘 #提示 #该设备正在使用中. 请关闭可能使用该设备的所有程序或窗口,然后重试…
阅读更多...
ZL-016D多通道小鼠主动跑轮系统主要研究动物生活节律

ZL-016D多通道小鼠主动跑轮系统主要研究动物生活节律

简单介绍&#xff1a; 多通道小鼠主动跑轮系统是由动物本身自发运动来推动跑轮转动。在这种构型中&#xff0c;笼内动物长期活动的信息&#xff0c;如跑轮转动方向、转数、累计总行程等&#xff0c;能够使用编码器进行长度计记录。此装置由转轮组件、笼体、以及转动方向速度传…
阅读更多...
国产分布式数据库高可用故障检测实现

国产分布式数据库高可用故障检测实现

在分布式数据库架构下&#xff0c;当数据库节点异常时&#xff0c;数据库管理组件能够自动感知到异常并触发节点隔离或者自动切换&#xff0c;是数据库高可用容灾的基本能力。在节点服务器异常、网络异常或进程异常等场景下&#xff0c;各数据库产品本身已经具备了可靠的检测能…
阅读更多...
前端连续发送同一个请求时，终止上一次请求

前端连续发送同一个请求时，终止上一次请求

场景&#xff1a;几个tab页之间快速的切换&#xff08;tab页只是参数不同&#xff0c;下边的数据渲染给同一个data&#xff09;就会导致如果我在1,2,3&#xff0c;tab页按照顺序快速点击&#xff0c;发送三个请求&#xff0c;我想要展示的是3但是如果1或者2请求响应的时间比3长…
阅读更多...
超简洁的todolist工具，电脑桌面高效计划管理软件

超简洁的todolist工具，电脑桌面高效计划管理软件

对于上班族来说&#xff0c;在电脑上使用一款高效计划管理软件至关重要。这样的工具不仅能帮助我们清晰地规划和追踪工作任务&#xff0c;还能有效提高工作效率&#xff0c;减少遗漏和延误。例如&#xff0c;当我们面临多个项目并行时&#xff0c;通过管理软件可以一目了然地查…
阅读更多...
web入门练手案例（二）

web入门练手案例（二）

下面是一下web入门案例和实现的代码&#xff0c;带有部分注释&#xff0c;倘若代码中有任何问题或疑问&#xff0c;欢迎留言交流~ 数字变色Logo 案例描述 “Logo”是“商标”的英文说法&#xff0c;是企业最基本的视觉识别形象&#xff0c;通过商标的推广可以让消费者了解企…
阅读更多...
最新文章

Copyright @ 2022~2023