物联网【C++】红黑树 - Powered by Discuz! Archiver

怀念夏天 发表于 2024-9-6 10:55:23

【C++】红黑树

前言：

AVL树是二叉平衡搜索树，红黑树是基于AVL树的改造，是基于旋转的次数的减少。
红黑树简介

红黑树的性质

[*]每个结点不是红色就是黑色
[*]根节点是黑色的
[*]假如一个节点是红色的，则它的两个孩子结点是黑色的
[*]对于每个结点，从该结点到其全部后代叶结点的简朴路径上，均包罗相同数目的黑色结点
[*]每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
红黑树操作

红黑树是一种自平衡的二叉搜索树，它通过在每个节点上添加颜色属性（红色或黑色）并遵循特定的规则来保持树的平衡，从而包管了插入、删除和查找操作的对数时间复杂度。
在C++中实现红黑树通常涉及以下步调：

[*]定义节点结构，包罗数据、颜色、左右子节点指针等。
[*]实现红黑树的基本操作，如插入、删除、左旋、右旋、颜色翻转等。
[*]维护红黑树的性质，确保在每次插入或删除后通过一系列旋转和颜色调解操作来规复平衡。
红黑树的实现

存储结构

[*]整体的存贮结构类似于AVL树，AVL实现平衡的需要平衡因子_bf
[*]红黑树的节点定义不是红色节点就是黑色节点，根据颜色的区分并且包管红红黑树的性质。
enum Colour
{
RED,
BLACK
};
template<class K, class V>
class RBTreeNode
{
   public:
   RBTreeNode<K, V>* _left;
   RBTreeNode<K, V>* _right;
   RBTreeNode<K, V>* _parent;
   pair<K, V> _kv;
   Colour _col;

   RBTreeNode(const pair<K, V>& kv)
         :_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv)
         {}
};
红黑树的插入、

[*]整体的思想和BST和AVL树是一样的左边小右边大
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
   _root = new Node(kv);
   _root->_col = BLACK;
   return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (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
   {
         return false;
   }
}

cur = new Node(kv);
cur->_col = RED;

if (kv.first < parent->_kv.first)
{
   parent->_left = cur;
}
else
{
   parent->_right = cur;
}
cur->_parent = parent;、
//调账
...
}
调解（旋转）

[*]红黑树的底层类似于AVL，仅仅是旋转次数变少，但是时间复杂度依旧是O（lgN）
左旋

void RotateL(Node* parent)
{

Node* cur = parent->_right;

Node* curleft = cur->_left;

parent->_right = curleft;

if (curleft)
{
curleft->_parent = parent;
}

cur->_left = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

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

cur->_parent = ppnode;
}
}
右旋

void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;

parent->_left = curright;

if (curright)
{
curright->_parent = parent;
}

cur->_right = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

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

cur->_parent = ppnode;
}

}
导致红黑树的不平衡缘故原由

[*]红黑树不可以连续个连续的节点是红色
[*]包管每一个路径黑色节点数目是一样的（根据这个条件，我们要插入红色节点）
环境一

[*]u节点存在，并且是红色
https://i-blog.csdnimg.cn/direct/84263870d82a45ca8b985e2c33ee5186.png
环境二

[*]u节点不存在或者u节点为黑色
https://i-blog.csdnimg.cn/direct/1861da1eeb314ffca676f72d4b8a7ce9.png
如何包管红黑树平衡

[*]我们需要寻找parent的节点的兄弟节点定义为uncle，举行判断，空，黑，红。
[*]假如是红色节点，将parent和uncle节点的颜色转换为黑色，继续向上调解
[*]假如节点不存在或者为黑的环境下，举行旋转，调解节点颜色。
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
   Node* uncle = grandparent->_right;
   if (uncle && uncle->_col == RED)
   {
         parent->_col = uncle->_col = BLACK;
         grandparent->_col = RED;
         cur = grandparent;
         parent = cur->_parent;
   }
   else//uncle is not or black
   {
         if (cur == parent->_left)
         {
            RotateR(grandparent);
            grandparent->_col = RED;
            parent->_col = BLACK;
         }
         else
         {
            RotateL(parent);
            RotateR(grandparent);
            grandparent->_col = RED;
            cur->_col = BLACK;
         }
         break;
   }
}
else//parent == grandparent->_right
{
   Node* uncle = grandparent->_left;

   if (uncle && uncle->_col == RED)
   {
         grandparent->_col = RED;
         parent->_col = uncle->_col= BLACK;
         cur = grandparent;
         parent = cur->_parent;
   }
   else
   {
         if (cur == parent->_right)
         {
            RotateL(grandparent);
            parent->_col = BLACK;
            grandparent->_col = RED;
         }
         else
         {
            RotateR(parent);
            RotateL(grandparent);
            cur->_col = BLACK;
            grandparent->_col = RED;
         }
   }
   break;
}
}
红黑树平衡的验证

[*]根节点不需要举行验证直接返回就好
[*]根节点假如是红色的节点可以举行返回。包管根节点是黑色的
[*]红黑树的特点就是每一个路径的黑色节点数目是一样的。这时候就需要查抄黑色节点的数目
bool is_balance(Node* root)
{
if (root == nullptr)
{
   return true;
}

if (root->_col == RED)
{
   return false;
}
int stdnum = 0;
Node* cur = root;
while (cur)
{
   if (cur->_col == BLACK)
   {
         ++stdnum;
   }
   cur = cur->_left;
}

return Checknum(root, 0, stdnum);
}
查抄黑色节点

[*]使用传值调用，递归实现
[*]走到根节点举行判断，假如是和标准相等的环境下，返回true。
bool Checknum(Node* root, int blacknum, int stdnum)
{
if (root == nullptr)
{
   if (blacknum != stdnum)
   {
         return false;
   }
   return true;
}

if (root->_col == BLACK)
{
   ++blacknum;
}

return Checknum(root->_left, blacknum, stdnum)
   && Checknum(root->_right, blacknum, stdnum);
}
源码

#pragma once

#include<iostream>
#include<assert.h>
#include<utility>

using namespace std;

namespace RBTree
{
enum Colour
{
RED,
BLACK
};
template<class K, class V>
class RBTreeNode
{
public:
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Colour _col;

RBTreeNode(const pair<K, V>& kv)
:_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv)
{}
};

template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;

public:
bool is_balance()
{
return is_balance(_root);
}

bool Checknum(Node* root, int blacknum, int stdnum)
{
if (root == nullptr)
{
if (blacknum != stdnum)
{
return false;
}
return true;
}

if (root->_col == BLACK)
{
++blacknum;
}

return Checknum(root->_left, blacknum, stdnum)
&& Checknum(root->_right, blacknum, stdnum);
}
bool is_balance(Node* root)
{
if (root == nullptr)
{
return true;
}

if (root->_col == RED)
{
return false;
}
int stdnum = 0;
Node* cur = root;
while (cur)
{
if (cur->_col == BLACK)
{
++stdnum;
}
cur = cur->_left;
}

return Checknum(root, 0, stdnum);
}
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (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
{
return false;
}
}

cur = new Node(kv);
cur->_col = RED;

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

while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//uncle is not or black
{
if (cur == parent->_left)
{
RotateR(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
}
else
{
RotateL(parent);
RotateR(grandparent);
grandparent->_col = RED;
cur->_col = BLACK;
}
break;
}
}
else//parent == grandparent->_right
{
Node* uncle = grandparent->_left;

if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
parent->_col = uncle->_col= BLACK;
cur = grandparent;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
}
break;
}
}
_root->_col = BLACK;
return true;
}

void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;

parent->_left = curright;

if (curright)
{
curright->_parent = parent;
}

cur->_right = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

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

cur->_parent = ppnode;
}

}
void RotateL(Node* parent)
{

Node* cur = parent->_right;

Node* curleft = cur->_left;

parent->_right = curleft;

if (curleft)
{
curleft->_parent = parent;
}

cur->_left = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

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

cur->_parent = ppnode;
}
}

private:
Node* _root = nullptr;
};

}

}
void RotateL(Node* parent)
{

Node* cur = parent->_right;

Node* curleft = cur->_left;

parent->_right = curleft;

if (curleft)
{
curleft->_parent = parent;
}

cur->_left = parent;

Node* ppnode = parent->_parent;

parent->_parent = cur;

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

cur->_parent = ppnode;
}
}

private:
Node* _root = nullptr;
};

}

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

页: [1]

ToB企服应用市场:ToB评测及商务社交产业平台's Archiver

【C++】红黑树