当前位置: 首页> 健康> 美食 > 免费网络营销课程_深圳卓越城蔚蓝铂樾府_网站打开速度优化_seo哪里有培训

免费网络营销课程_深圳卓越城蔚蓝铂樾府_网站打开速度优化_seo哪里有培训

时间:2025/7/10 16:49:16来源:https://blog.csdn.net/paradiso989/article/details/142926214 浏览次数:0次
免费网络营销课程_深圳卓越城蔚蓝铂樾府_网站打开速度优化_seo哪里有培训

目录

一、什么是红黑树

1.1 红黑树的规则

1.2 红黑树的特性

二、红黑树的插入

2.0 插入思路

2.1 情况一

2.2 情况二

2.3 情况三

2.2 插入代码


一、什么是红黑树

红黑树是一种特殊的二叉搜索树,它在每个节点上增加了一个颜色属性,可以是红色或黑色。

1.1 红黑树的规则

  • 每个节点要么是黑色要么是红色。
  • 根节点是黑色
  • 每个叶子节点(NIL节点,空节点)是黑色。
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
  • 如果⼀个结点是红⾊的,则它的两个孩⼦结点必须是黑色的,也就是说任意⼀条路径不会有连续的红⾊结点。
enum colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;colour _col;//三叉链RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

1.2 红黑树的特性

假设从根节点开始到NULL节点最短的路径高度为bh,则红黑树的总高度h满足:bh <= h <= 2*bh。

二、红黑树的插入

2.0 插入思路

总体思路:

  • 先按照搜索二叉树的规则进行插入,然后通过一系列操作使之满足红黑树的规则。
  • 如果是空树插入,新增结点是黑色结点。如果是非空树插⼊,新增结点必须红色结点
    if (_root == nullptr)
    {_root = new Node(kv);_root->_col = BLACK;return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}
    }cur = new Node(kv);
    cur->_col = RED;
    if (parent->_kv.first < kv.first)
    {parent->_right = cur;
    }
    else
    {parent->_left = cur;
    }
    //链接父亲
    cur->_parent = parent;
  • 插入后,如果其父亲节点是黑色的,则满足红黑树的规则。如果父亲节点是红色的,则不满足(红色节点的子节点都为黑色)的规则,需要调整。

2.1 情况一

叔叔节点存在且为红色

  • 考虑一般情况:
    让“叔叔”节点变为黑色,“爷爷”节点变为红色 ,“父亲”节点变为黑色
  • 考虑特殊情况:
    插入的树可能只是其中的一颗子树,爷爷节点的颜色变化可能会违反规则
    所以,将cur指向爷爷节点,继续进行处理
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;
}

2.2 情况二

  • 叔叔节点不存在
    cur指向的一定是新增的节点
  • 叔叔节点存在但是为黑色
    cur指向的一定不是新增的节点,而是某个子树新增了节点导致其爷爷节点变成了红色

如果父亲在爷爷的左边:则右旋

如果父亲在爷爷的右边:则左旋

最后:父亲节点变黑,爷爷节点变红

//父亲在爷爷的左树
if (cur == parent->_left)
{RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;
}
//父亲在爷爷的右树
if (cur == parent->_right)
{RotateL(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;
}

2.3 情况三

  • 叔叔节点不存在
    cur指向的一定是新插入的节点
  • 叔叔节点存在但是为黑色
    cur指向的一定不是新增的节点,而是某个子树新增了节点导致其爷爷节点变成了红色
//父亲节点在爷爷节点的左边
RotateL(parent);
RotateR(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;//父亲节点在爷爷节点的右边
RotateR(parent);
RotateL(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;

2.2 插入代码

旋转部分代码详见:数据结构之AVL树(万字详解)_avl树 详解-CSDN博客

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 (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//链接父亲cur->_parent = parent;//父亲是红色、处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left==parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else{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;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else{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;return true;
}
关键字:免费网络营销课程_深圳卓越城蔚蓝铂樾府_网站打开速度优化_seo哪里有培训

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: