【二叉树进阶】红黑树（Red Black Tree） - 平衡二叉搜索树

article/2025/10/1 6:10:28

文章目录

    • 一、红黑树的概念
    • 二、红黑树的性质
      • 2.1 红黑树和AVL树效率对比
    • 三、红黑树的结构（KV模型）
    • 四、红黑树的插入
      • 4.1 插入节点
      • 4.2 平衡化操作（难点）
        • 4.2.1 情况一
        • 4.2.2 情况二
        • 4.2.3 情况三
      • 4.3 总结
    • 五、红黑树的验证
    • 六、红黑树的删除（了解）
    • 七、红黑树的应用

一、红黑树的概念

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

AVL树和红黑树：

  • AVL树：严格平衡（左右子树高度差不超过1），所以AVL树的查找、插入、删除效率高：O(logN)，但插入和删除节点后，要维持树的平衡状态，做的旋转处理还是很多的。
  • 红黑树：近似平衡（控制最长路径不超过最短路径的2倍），变了一种方式来控制树的平衡，相较于AVL树，没有那么严格。

红黑树更多是一种折中的选择，它舍弃平衡二叉树的严格平衡，换取节点插入时尽可能少的调整。

因为红黑树的旋转情况少于AVL树，使得红黑树整体性能略优于AVL树，不然map和set底层怎么会用红黑树呢，包括很多语言的库里面都用了红黑树。

如果发明AVL树的人是天才的话，那么发明红黑树的人就是天才中的天才，太妙了。

二、红黑树的性质

【核心 & 重要】

  1. 每个结点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的（这就约束了红黑树里面没有连续的红色节点）

  4. 对于每个结点，从该结点到其所有可到达的叶结点的路径中，均包含相同数目的黑色结点

    （即==每条路径都有相同数量的黑色节点==，注意：路径是走到 NIL 空节点）

  5. 每个 NIL 叶子结点都是黑色的（此处的叶子结点指的是空结点）

如图，这颗红黑树有11条路径，每条路径都有两个黑节点（不包括NIL）

image-20220324160453474

【思考】

为什么满足以上性质后，就能保证 最长路径中节点个数不会超过最短路径中节点个数的2倍 了呢（不包括NIL）

当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点交替构成的（性质3限定了不能出现两个连续的红色节点）。

而性质4又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点，这么来说最长路径上的黑节点的数目和最短路径上的黑节点的数目相等。

最短路径：全是黑节点，最长路径：一黑一红，交替出现，所以最长路径刚好是最短路径的2倍。

image-20220324165436988

2.1 红黑树和AVL树效率对比

对于一棵拥有 n 个内部结点（不包括NIL叶子结点）的红黑树，树的最大高度为 h = 2log2(n + 1)

当红黑树是一颗满二叉树时，高度最小 h = log2(n+1)，当红黑树中最长路径刚好是最短路径2倍的时候，红黑树的高度最大 h = 2log2(n+1)

如果数据量是10亿：

查找效率查找次数(约等于)
AVL树：log2n30
红黑树：2log2n60

【结论】：

  1. 虽然AVL树的查找效率优于红黑树，但对于现在的CPU，查找30次和60次是没有什么区别的，可以认为红黑树和AVL树的查找效率几乎是一样的，简化后为 O(log2n)。
  2. 红黑树整体性能略优于AVL树（因为红黑树旋转情况少于AVL树）。
  3. 红黑树的插入删除比AVL树更便于控制操作。
  4. 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2n)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

三、红黑树的结构（KV模型）

和AVL树类似。

1、定义红黑树的节点结构

// 定义红黑颜色
enum Colour // 枚举类型，枚举值默认从0开始，往后逐个加1（递增）
{BLACK,RED
};// 红黑树节点的定义（KV模型）
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;            // 键值对Colour _col;               // 用来标记节点颜色RBTreeNode<K, V>* _left;   // 三叉链结构RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;// 构造函数RBTreeNode(const pair<K, V>& kv): _kv(kv), _col(RED), _left(nullptr), _right(nullptr), _parent(nullptr){}
};

2、定义红黑树结构

// 红黑树的定义（KV模型）
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;private:Node* _root;public:RBTree() :_root(nullptr) {}        // 构造函数bool Insert(const pair<K, V>& kv); // 插入节点void RotateLeft(Node* parent);     // 左单旋void RotateRight(Node* parent);    // 右单旋bool IsBalance();                  // 检测红黑树是否平衡void InOrder();                    // 中序遍历// ......
private:void _InOrder(Node* root);         // 中序遍历子函数// ......
};

【思考】：在节点的定义中，为什么要将节点的默认颜色给成红色的？

  • 如果插入黑色节点，一定会破坏性质4（每条路径的黑色节点数量相等）；
  • 如果插入红色节点，可能会破坏性质3（树中不能出现两个连续的红色节点）；
  • 所以默认给红色。

四、红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

  1. 按照二叉搜索树的规则插入新节点
  2. 检测新节点插入后，红黑树的性质是否遭到破坏，然后进行平衡化操作

4.1 插入节点

思考：插入的新节点是红色好还是黑色好呢？

红色好，如果插入黑色，一定会破坏性质4（每条路径的黑色节点数量相等）；如果插入红色，可能会破坏性质3（树中不能出现两个连续的红色节点）

插入一个红色新节点后，检测红黑树的性质是否遭到破坏，分为2种情况：

  1. 如果其父节点颜色是黑色，没有违反红黑树任何性质，则不需要调整；

  2. 如果其父节点颜色是红色，则违反了性质3（树中不能出现两个连续的红色节点），此时需要对红黑树进行平衡化操作，分为以下几种情况来讨论👇

4.2 平衡化操作（难点）

约定：cur 为当前插入的节点，p (parent)为父节点，g (grandfather)为祖父节点，u (uncle)为叔叔节点

调整的关键：主要是看 cur 的叔叔节点 u 是否存在，以及叔叔节点 u 的颜色。

解析：cur为红，p为红，违反规则了，我们将p变黑，则导致p所在的所有路径上，黑节点数增加了一个，但因为 叔叔节点u 和 父节点p 在同一层上，所以叔叔节点u的状态会影响到 以祖父g为根的子树中 路径的黑节点数，可能导致违反规则（每条路径都有相同数量的黑色节点）。

👇注意：此处看到的树，可能是一颗完整的树，也可能是一颗子树。所以可能会一直调整到根节点才停止。

4.2.1 情况一

情况一：cur为红，p为红，g为黑，u存在且为红

image-20220327151933239

对情况一进行平衡化操作：先调整颜色，再往上调整

无论父亲 p 是祖父 g 的左孩子还是右孩子，无论 cur 是父亲 p 的左孩子还是右孩子，处理方式都一样：

  • 调整颜色：将 cur 的父亲 p 和叔叔 u 变黑，祖父 g 变红

  • 把祖父 g 当成新的 cur，往上调整（即往上检测新的子树破坏了性质），分为以下情况：

  1. 如果 cur 父亲 p 不存在，说明 cur 就是根节点，调整到头了，此时将根节点改为黑色

image-20220326104655422

  1. 如果 cur 父亲 p 存在且为黑色，无需调整（没有违反任何性质)
  2. 如果 cur 父亲 p 存在且为红色，继续调整，判断是否产生了情况二或三：

image-20220326174823552

【注意】：

情况一在向上调整的过程中，可能会产生情况二或三，处理方式：旋转（先要判断是哪种旋转） + 变色处理

4.2.2 情况二

情况二： cur为红，p为红，g为黑，u不存在 / u存在且为黑

image-20220327152042687

如图所示，情况一向上调整过程中，产生了情况二 - ①：

image-20220326211140683

对情况二进行平衡化操作：先单旋，再调整颜色（不管是哪种单旋，颜色调整都一样：p变黑，g变红）

注意：对局部的一颗子树平衡化操作，整个过程中，我们要保持当前子树的每条路径中黑色节点数量不变。

① 如果父亲 p 是祖父 g 的左孩子， cur 是父亲 p 的左孩子，先对祖父 g 进行右单旋；然后将父亲 p 变黑，祖父 g 变红：

  1. u不存在
image-20220326223624651
  1. u存在且为黑
image-20220326224036647

② 如果父亲 p 是祖父 g 的右孩子， cur 是父亲 p 的右孩子，先对祖父 g 进行进行左单旋；然后将父亲 p 变黑，祖父 g 变红：

  1. u不存在
image-20220326223052195
  1. u存在且为黑
image-20220326224247504

4.2.3 情况三

情况三：cur为红，p为红，g为黑，u不存在 / u存在且为黑

image-20220327152226989

如图所示，情况一向上调整过程中，产生了情况三 - ①：

image-20220327101033865

对情况三进行平衡化操作：先双旋，再调整颜色（不管是哪种双旋，颜色调整都一样：cur变黑，g变红）

注意：对局部的一颗子树平衡化操作，整个过程中，我们要保持当前子树的每条路径中黑色节点数量不变。

① 如果父亲 p 是祖父 g 的左孩子， cur 是父亲 p 的右孩子，先对父亲 p 进行左单旋，再对祖父 g 进行右单旋；然后将 cur 变黑，祖父 g 变红：

  1. u不存在
image-20220326232316984
  1. u存在且为黑
image-20220327101616246

② 如果父亲 p 是祖父 g 的右孩子，cur 是父亲 p 的左孩子，先对父亲 p 进行右单旋，再对祖父 g 进行左单旋；然后将 cur 变黑，祖父 g 变红：

  1. u不存在
image-20220327100542736
  1. u存在且为黑
image-20220327102802970

4.3 总结

插入节点后，控制树的近似平衡，操作总结如下，整个逻辑拉通了，还是挺简单的👇

当插入红色新节点 cur 后，如果父亲 p 存在且为红，说明破坏红黑树性质了，需要平衡化操作。

首先记录 cur 的父亲 p 和祖父 g 的位置，然后判断父亲 p 的位置：

1）如果父亲 p 是祖父 g 的左孩子：

说明叔叔u是祖父g的右孩子，先判断叔叔的状态：

  • 如果「叔叔u存在且为红」，说明是情况一，直接先变色处理，然后再往上调整。

    • 先调整颜色：父亲 p 和叔叔 u 变黑，祖父 g 变红。

    • 再往上调整：原先祖父 g 当成新的 cur，判断新 cur 的父亲 p：

      1. 若父亲 p 不存在，说明调整到头了，停止调整，然后将根节点变黑。

      2. 若父亲 p 存在且为黑，没有破坏性质，停止调整。

      3. 若父亲 p 存在且为红，继续调整，并判断是否出现了情况二或三，要一直调整到 根节点 或者 父亲 p 存在且为黑 时，才停止调整。

  • 如果「叔叔u不存在」或者「叔叔u存在且为黑」，说明是情况二或者情况三，先判断 cur 的位置：

    • 如果 cur 是父亲 p 的左孩子（此时 cur、p、g是一条直线，说明是情况二）
      • 进行右单旋 + 变色处理（父亲 p 变黑，祖父 g 变红）
    • 如果 cur 是父亲 p 的右孩子（此时 cur、p、g是一条折线，说明是情况三）
      • 进行左右双旋 + 变色处理（cur 变黑，祖父 g 变红）
    • 上述情况二或三处理完成后，当前子树的根节点为黑 (p / cur)，没有连续红节点了，则停止调整。

2）如果父亲 p 是祖父 g 的右孩子：

说明叔叔u是祖父g的左孩子，先判断叔叔的状态：

  • 如果「叔叔u存在且为红」，说明是情况一，先变色处理（p和u变黑，g变红），然后再往上调整，去判断新的父亲p的状态，检测新的子树是否平衡，如果不平衡，是出现了哪种情况(1/2/3)呢？

    情况一处理方式类似于上面，此处略……

  • 如果「叔叔u不存在」或者「叔叔u存在且为黑」，说明是情况二或者情况三，先判断 cur 的位置：

    • 如果 cur 是父亲 p 的右孩子（此时 cur、p、g是一条直线，说明是情况二）

      • 进行左单旋 + 变色处理（父亲 p 变黑，祖父 g 变红）

    • 如果 cur 是父亲 p 的左孩子（此时 cur、p、g是一条折线，说明是情况三）

      • 进行右左单旋 + 变色处理（cur 变黑，祖父 g 变红）

    • 上述情况二或三处理完成后，当前子树的根节点为黑 (p / cur)，没有连续红节点了，则停止调整。

要注意下，上面几个停止调整，是循环的出口，否则就要一直调整到 根节点 或者 父亲 p 存在且为黑 时

代码如下：

// 插入节点
bool Insert(const pair<K, V>& kv)
{/* ----------------------------------------------------------------- *//* 一、查找到适合插入的空位置 */ // 树为空if (_root == nullptr){_root = new Node(kv); // 插入新节点_root->_col = BLACK;  // 根节点为黑色return true;}// 树不为空Node* cur = _root;      // 记录当前节点和它的父节点Node* parent = nullptr;while (cur) // cur为空时，说明找到插入位置了{if (kv.first > cur->_kv.first) // 键值大于当前节点{parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first) // 键值小于当前节点{parent = cur;cur = cur->_left;}else if (kv.first == cur->_kv.first) // 键值等于当前节点{return false; // 不允许数据冗余，返回false}}// 插入新节点，颜色为红色（可能会破坏性质3，产生两个连续红色节点）cur = new Node(kv);cur->_col = RED;// 判断新节点是其父亲的左孩子还是右孩子if (cur->_kv.first > parent->_kv.first){// 建立parent和cur之间的联系parent->_right = cur;cur->_parent = parent; // 更新cur的双亲指针}else{// 建立parent和cur之间的联系parent->_left = cur;cur->_parent = parent; // 更新cur的双亲指针}/* ----------------------------------------------------------------- *//* 二、检测红黑树性质有没有被破坏，并控制树的平衡 */// 如果cur的父亲p存在且为红，则树不平衡，就需要一直往上调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent;  // 记录cur的祖父grandfather// 1、如果parent是grandfather的左孩子if (parent == grandfather->_left) {Node* uncle = grandfather->_right; // uncle是grandfather的右孩子/* 调整的关键：判断叔叔的状态，得知具体是哪种情况，然后再进行处理 */// （1）uncle存在且为红，说明是情况1if (uncle && uncle->_col == RED){// 调整颜色parent->_col = uncle->_col = BLACK; // parent和uncle变黑grandfather->_col = RED;            // grandfather变红// 继续往上调整// 去判断新的父亲p的状态，检测新的子树是否平衡，如果不平衡，出现了哪种情况(1/2/3)cur = grandfather;       // 更新cur和parentparent = cur->_parent;            }// （2）uncle不存在/存在且为黑，说明是情况2或3else if (uncle == nullptr || uncle->_col == BLACK){// 先判断cur的位置：if (cur == parent->_left)         // 如果cur是parent的左孩子，说明是情况2{// 单旋 + 调整颜色RotateRight(grandfather);     // 右单旋parent->_col = BLACK;         // parent变黑grandfather->_col = RED;      // grandfather变红}else if(cur == parent->_right)    // 如果cur是parent的右孩子，说明是情况3{// 双旋 + 调整颜色RotateLeft(parent);           // 左单旋RotateRight(grandfather);     // 右单旋cur->_col = BLACK;            // cur变黑grandfather->_col = RED;      // grandfather变红}// 情况2或3处理完成后，当前子树的根节点为黑，没有连续红节点了，则停止调整break;}}// 2、如果parent是grandfather的右孩子else if (parent == grandfather->_right){Node* uncle = grandfather->_left;   // uncle是grandfather的左孩子/* 调整的关键：判断叔叔的状态，得知具体是哪种情况，然后再进行处理*/// (1) uncle存在且为红，说明是情况1if (uncle && uncle->_col == RED){// 调整颜色parent->_col = uncle->_col = BLACK; // parent和uncle变黑grandfather->_col = RED;            // grandfather变红// 继续往上调整// 去判断新的父亲p的状态，检测新的子树是否平衡，如果不平衡，出现了哪种情况(1/2/3)cur = grandfather;      // 更新cur和parentparent = cur->_parent;}// (2) uncle不存在/存在且为黑，说明是情况2或3else if (uncle == nullptr || uncle->_col == BLACK){// 先判断cur的位置：if (cur == parent->_right)        // 如果cur是parent的右孩子，说明是情况2{// 单旋 + 调整颜色RotateLeft(grandfather);      // 左单旋parent->_col = BLACK;         // parent变黑grandfather->_col = RED;      // grandfather变红}else if (cur == parent->_left)    // 如果cur是parent的左孩子，说明是情况3{// 双旋 + 调整颜色RotateRight(parent);          // 右单旋RotateLeft(grandfather);      // 左单旋cur->_col = BLACK;            // cur变黑grandfather->_col = RED;      // grandfather变红}// 情况2或3处理完成后，当前子树的根节点为黑，没有连续红节点了，则停止调整break;}}}// 运行到这里来了，说明：// 1. cur的父亲p不存在，则cur就是根节点，将根节点变黑// 2. cur的父亲p存在且为黑，树是平衡的，结束调整_root->_col = BLACK; // 根节点变黑/* ----------------------------------------------------------------- */return true;
}// 左单旋
void RotateLeft(Node* parent)
{Node* subR = parent->_right; // 记录parent的右孩子Node* subRL = subR->_left;   // 记录parent右孩子的左孩子// 建立parent和subRL之间的联系parent->_right = subRL;if (subRL)subRL->_parent = parent;// 建立subR和parent之间的联系Node* pp = parent->_parent;  // 先记录下parent的父节点subR->_left = parent;parent->_parent = subR;// 建立pp和subR之间的联系if (pp == nullptr)           // pp为空，说明parent原先是根节点{_root = subR;            // subR为新的根节点subR->_parent = nullptr; // subR的双亲指针指向空}else if(pp != nullptr)       // pp不为空，说明parent原先是一个普通子树{// 判断parent原先是父亲pp的左孩子还是右孩子if (parent == pp->_left){pp->_left = subR;}else if (parent == pp->_right){pp->_right = subR;}subR->_parent = pp;      // subR的双亲指针指向pp}
}// 右单旋
void RotateRight(Node* parent)
{Node* subL = parent->_left;  // 记录parent的左孩子Node* subLR = subL->_right;  // 记录parent左孩子的右孩子// 建立parent和subLR之间的联系parent->_left = subLR;if (subLR)subLR->_parent = parent;// 建立subL和parent之间的联系Node* pp = parent->_parent;  // 先记录下parent的父节点subL->_right = parent;parent->_parent = subL;// 建立pp和subL之间的联系if (pp == nullptr)           // pp为空，说明parent原先是根节点{_root = subL;            // subL为新的根节点subL->_parent = nullptr; // subL的双亲指向指向空}else if (pp != nullptr)      // pp不为空，说明parent原先是一个普通子树{// 判断parent原先是pp的左孩子还是右孩子if (parent == pp->_left){pp->_left = subL;}else if (parent == pp->_right){pp->_right = subL;}subL->_parent = pp;     // subL的双亲指针指向pp}
}

五、红黑树的验证

红黑树的检测分为两步：

  • 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

  • 检测其是否满足红黑树的性质

    1. 根节点是否为黑色

    2. 是否存在连续红节点

    3. 统计每条路径上的黑节点数是否相等

① 检测是否存在连续红节点：

// 检测红黑树是否有连续红节点
bool CheckRedRed(Node* root)
{if (root == nullptr)return true;// 思路1：如果当前节点为红色，检测它的孩子是否为红色，但孩子可能为空，每次还得判断孩子是否为空，太麻烦了// 思路2：如果当前节点为红色，我们去检测它的父亲是否为红色// 因为根节点没有父亲，且根节点为黑色，是不会被判断的if (root->_col == RED && root->_parent->_col == RED){cout << "出现连续红节点，违反性质了" << endl;return false;}// 继续判断当前节点的左右孩子return CheckRedRed(root->_left)&& CheckRedRed(root->_right);
}

② 检测每条路径上的黑节点数是否相等：

首先计算出红黑树其中一条路径的黑节点数，作为一个 baseValue 基准值(参考值)

然后再求出红黑树每条路径的黑节点数，与基准值比较，如果不相等，说明违反性质了。

  • blackNum：表示从根节点到当前节点的黑节点数
  • baseValue：基准值（最左侧路径的黑节点数）
// 计算红黑树最左侧这条路径的黑节点数，作为基准值(参考值)
int CountBaseValue()
{int count = 0; // 统计黑节点数Node* cur = _root;while (cur)    // 遇到NIL时，统计结束{if (cur->_col == BLACK)count++;cur = cur->_left;}return count;
}/* 检测红黑树每条路径的黑节点数是否相等* 思路：求出每条路径的黑节点数，与基准值比较，如果不相等，说明违反性质了* blackNum：表示从根节点到当前节点的黑节点数，默认从0开始* baseValue：基准值（最左侧路径的黑节点数）*/
bool CheckBlackNums(Node* root, int blackNum, int baseValue)
{// 当前节点为空，说明遇到了NIL，判断该路径的黑节点数是否等于基准值if (root == nullptr){if (blackNum != baseValue){cout << "每条路径黑节点数不相等，违反性质了" << endl;return false;}elsereturn true;}// 当前节点为黑色，则从根节点到当前节点的黑节点数加1if (root->_col == BLACK)blackNum++;return CheckBlackNums(root->_left, blackNum, baseValue)&& CheckBlackNums(root->_right, blackNum, baseValue);
}

【注意】：

这里计算每条路径的黑节点数 blackNum 时，使用的是传值，因为这样就可以在递归的过程中计算到每条路径的黑节点数，因为每个函数栈帧中的 blackNum 变量都是独立存在的。

下一层的 blackNum 是上一层的拷贝，下一层中++，不会影响上一层。

比如在 黑节点1 中对 blackNum++，变成2，但 红节点8 中的 blackNum 值还是1，所以就不会影响到计算右孩子即 黑节点11 所在路径的黑节点数。

image-20220329161315621

求一棵树的叶子节点数和总的节点数，就可以用引用

红黑树的验证代码如下：

// 检测红黑树是否平衡
bool IsBalance()
{if (_root == nullptr)return true;// 1、检测红黑树的根节点是否为红色if (_root->_col == RED){cout << "根节点为红色，违反性质了" << endl;return false; // 直接返回false}// 2、CheckRedRed：检测红黑树是否有连续红节点// 3、CheckBlackNums：检测红黑树每条路径黑节点数是否相等return CheckRedRed(_root) && CheckBlackNums(_root, 0, CountBaseValue());
}

用n个随机值元素来测试红黑树：

int main()
{// 用n个随机值元素来测试红黑树// 定义r的向量const int n = 1000000;vector<int> a;a.reserve(n);// 初始化随机种子srand(time(0));for (size_t i = 0; i < n; i++){// 生成随机值a.push_back(rand());// 如果只写rand()，这样生成的随机值不是真的随机，每次都是一样的// 所以要初始化随机数生成器srand()，给它一个随机种子}// 定义红黑树，插入n个元素RBTree<int, int> rb;for (auto& e : a){rb.Insert(make_pair(e, e));}// 打印验证结果cout << rb.IsBalance() << endl;return 0;
}

观察运行结果，插入n个元素后，红黑树是平衡的。

六、红黑树的删除（了解）

因为红黑树也是二叉搜索树，可按照二叉搜索树的方式将节点删除。

  • 如果删除的一个红色节点，是不会违反任何规则的，
  • 如果删除的是黑色节点，一定会破坏规则，导致每条路径上的黑节点数不相等了，这个时候就要小心了，我们要进行平衡化操作（旋转、变色），使树平衡。

推荐文章：红黑树 - Never - 博客园 (cnblogs.com)

七、红黑树的应用

  1. C++ STL库 – map/set、mutil_map/mutil_set

  2. Java 库

  3. linux内核

  4. 其他一些库


http://chatgpt.dhexx.cn/article/kxp5SWsm.shtml

相关文章

MySQL 慢查询日志导入 Elasticsearch 可视化查询分析

MySQL 慢查询日志导入 Elasticsearch 可视化查询分析

当应用程序后台 SQL 查询慢的时候我们一般第一时间会查看数据库慢查询记录&#xff0c;但是慢查询记录是原始文本&#xff0c;直接查询搜索分析比较费时费力&#xff0c;虽然业界有针对 MySQL 慢查询分析的命令行工具&#xff08;比如&#xff1a;pt-query-digest&#xff09;&…
阅读更多...
MySQL 慢查询日志如何查看及配置

MySQL 慢查询日志如何查看及配置

简介 MySQL 慢查询日志是排查问题 SQL 语句&#xff0c;以及检查当前 MySQL 性能的一个重要功能。 查看是否开启慢查询功能&#xff1a; 说明&#xff1a; slow_query_log 慢查询开启状态 slow_query_log_file 慢查询日志存放的位置&#xff08;这个目录需要MySQL的运行帐号的…
阅读更多...
MySQL高级篇——聊聊MySQL的慢查询日志

MySQL高级篇——聊聊MySQL的慢查询日志

文章目录&#xff1a; 1.数据库服务器的优化步骤 2.查看系统性能参数 3.定位执行慢的 SQL&#xff1a;慢查询日志 4.查看 SQL 执行成本&#xff1a;SHOW PROFILE 1.数据库服务器的优化步骤 当我们遇到数据库调优问题的时候&#xff0c;该如何思考呢&#xff1f;这里把思考…
阅读更多...
清理mysql慢查询日志_MySQL清理慢查询日志slow_log的方法

清理mysql慢查询日志_MySQL清理慢查询日志slow_log的方法

一、清除原因 因为之前打开了慢查询，导致此表越来越大达到47G，导致磁盘快被占满，使用xtrabackup进行备份的时候文件也超大。 mysql> show variables like log_output%; Connection id: 1694401091 Current database: mysql +---------------+-------+ | Variable_name | …
阅读更多...
mysql 慢查询日志的设置与优化

mysql 慢查询日志的设置与优化

目录 1 引言 2 慢查询日志配置 3 分析工具 1 引言 MySQL数据中有记录慢查询的一种手段。并且是MySQL自带的。可用来排查那些查询sql语句执行得慢。从而给开发者提供一个调优得依据。 MySQL 慢查询的相关参数解释&#xff1a; slow_query_log &#xff1a;是否开启慢查…
阅读更多...
如何开启mysql慢查询日志？

如何开启mysql慢查询日志？

1、查看mysql的慢查询日志是否开启 show variables like %query%; 可以看到slow_query_log的值是OFF&#xff0c;也就是mysql默认是不启用慢查询日志的。 这里还有个long_query_time&#xff0c;默认是10秒&#xff0c;也就是超过了10秒即为慢查询。 log_queries_not_using_…
阅读更多...
MySQL慢查询日志详解

MySQL慢查询日志详解

本次代码执行环境的mysql版本是 &#xff1a;5.6.37-log 1.慢查询日志概念(也叫慢日志):在 MySQL 中执行时间超过指定时间的 SQL 语句 2.常见的几个相关的变量 (可以直接去mysql下的配置文件my.cnf文件中去改,我下面是直接在SQLyog中进行操作) 默认情况下慢查询日志是关闭的…
阅读更多...
MySQL 慢查询日志 使用方法浅析 日志定位与优化技巧

MySQL 慢查询日志 使用方法浅析 日志定位与优化技巧

目录 前言 1、如何开启使用慢查询日志&#xff1f; 1.1 开启慢查询日志 1.2 设置慢查询阈值 1.3 确定慢查询日志的文件名和路径 1.3.1 查询MySQL数据目录 1.3.2 查询慢查询日志文件名 1.3.3 查询全局设置变量 1.3.4 查询单个变量命令 1.3.5 其他注意事项 2、如何定位并优…
阅读更多...
mysql慢查询日志在哪里

mysql慢查询日志在哪里

如何查找MySQL中查询慢的SQL语句 你是指慢查询日志吗&#xff1f; 在my.ini中加上下面两句话 log-slow-queriese:\mysql5.5\mysql_slow_query.log long_query_time10 前面一句是设置慢查询日志存放路径&#xff0c;第二句是指多少秒以上算慢查询&#xff0c;上面的语句&#xf…
阅读更多...
MySQL慢查询日志分析

MySQL慢查询日志分析

&#xff08;1&#xff09;慢查询日志 MySQL提供了慢SQL的日志记录功能&#xff0c;我们可以通过设置一些属性来记录系统使用过程中慢查询的执行日志。使用MySQL慢查询日志对有效率问题的SQL进行监控。 查看属性 【1】查看MySQL是否开启慢查询日志记录功能 show variables l…
阅读更多...
MySQL优化之慢日志查询

MySQL优化之慢日志查询

目录 一、慢查询日志(slow_query_log)概念二、慢查询日志实践1. 打开慢查询日志开关2. 设置合理的、业务可以接受的慢查询时间上限long_query_time3. 压测执行各种业务4. 查看慢查询日志5. 用explain分析这些耗时的sql语句&#xff0c;从而针对性优化 三、show profiles查看sql…
阅读更多...
MySQL日志（一）—— 慢查询日志slow log

MySQL日志（一）—— 慢查询日志slow log

一、慢查询日志&#xff08;slow log&#xff09; 慢查询日志&#xff0c;就是查询超过一定的时间没有返回结果的时候&#xff0c;MySQL会将执行的SQL记录到日志中&#xff0c;这个日志&#xff0c;就称为慢查询日志。通过分析慢查询日志&#xff0c;可以快速找出执行慢的SQL语…
阅读更多...
【OpenCv3】 VS C++ （五）：SLIC超像素分割算法

【OpenCv3】 VS C++ （五）：SLIC超像素分割算法

下一节地址&#xff1a;https://blog.csdn.net/qq_40515692/article/details/102788157 OpenCv专栏&#xff1a;https://blog.csdn.net/qq_40515692/article/details/102885061 超像素&#xff08;SuperPixel&#xff09;&#xff0c;就是把原本多个像素点&#xff0c;组合成一…
阅读更多...
superpixels(超像素）

superpixels(超像素）

superpixels(超像素&#xff09; 1.理解&#xff1a; 超像素不是在普通的像素基础上继续微观细分&#xff0c;超像素是一系列像素的集合&#xff0c;这些像素具有类似的颜色、纹理等特征&#xff0c;距离也比较近。其中超像素比较常用的一种方法是SLIC Semantic Segmentatio…
阅读更多...
Seeds超像素分割

Seeds超像素分割

#%% SEED超像素分割 import cv2 import numpy as np import imageio # print(dir(cv2.ximgproc))img imageio.imread(rE:\Vaihingen\data\orginalimages\top_mosaic_09cm_area31.tif)[:,:,::-1] converted_img cv2.cvtColor(img, cv2.COLOR_BGR2HSV)# print(type(img_feature…
阅读更多...
Python实现超像素分割

Python实现超像素分割

目录 一、什么是超像素&#xff1f;二、超像素具有哪些特点&#xff1f;三、Simple Linear Iterative Clustering (SLIC)算法实现步骤四、SLIC算法代码实现五、效果展示和分析六、基于超像素的边缘检测代码七、基于超像素的边缘检测效果展示与分析八、思维扩展参考资料注意事项…
阅读更多...
基于Matlab的SLIC超像素分割算法分析

基于Matlab的SLIC超像素分割算法分析

SLIC超像素分割算法分析 1&#xff1a;导入原始照片&#xff0c;初始化聚类中心&#xff0c;按照设定的超像素个数&#xff0c;在图像内均匀的分配聚类中心。假设图片总共有 N 个像素点&#xff0c;预分割为 s 个相同尺寸的超像素&#xff0c;那么每个超像素的大小为N/ s &…
阅读更多...
超像素分割算法————综述

超像素分割算法————综述

参考&#xff1a;超像素—学习笔记 什么是超像素&#xff1f;评价标准&#xff1f;SLIC、SEED、ETPS算法 比较的指标&#xff1a;图像边界的粘附性、算法速度、存储效率、分割性能 超像素算法&#xff1a;将像素组合成感知有意义的原子区域( atomic regions)&#xff0c;其可…
阅读更多...
超像素分割 SLIC算法 使用示例

超像素分割 SLIC算法 使用示例

参考博客 介绍超像素分割 & SLIC算法 SLIC超像素分割详解&#xff08;一&#xff09;&#xff1a;简介_计算机视觉life的博客-CSDN博客_slic超像素分割 机器学习&#xff1a;simple linear iterative clustering (SLIC) 算法_Matrix_11的博客-CSDN博客_简单线性迭代聚类…
阅读更多...
图像处理: 超像素(superpixels)分割 SLIC算法

图像处理: 超像素(superpixels)分割 SLIC算法

原理 超像素概念是2003年Xiaofeng Ren提出和发展起来的图像分割技术&#xff0c;是指具有相似纹理、颜色、亮度等特征的相邻像素构成的有一定视觉意义的不规则像素块。它利用像素之间特征的相似性将像素分组,用少量的超像素代替大量的像素来表达图片特征,很大程度上降低了图像…
阅读更多...
推荐文章

Copyright @ 2022~2023