目录
红黑树和AVL树一样，因其逻辑复杂，面试时现场要求手撕就是纯纯刁难面试者。但某大厂面试官曾要求某些求职者现场手撕红黑树（我赌5毛，让面试官撕，他也撕不出来，而且你家员工上班手搓红黑树啊？），随后求职遭遇被发到网上吐槽，这便有了“手撕红黑树”的梗，也让红黑树成为了知名度最高的数据结构。（话虽如此，对于红黑树的性质、插入思想等概念还是需要掌握的）
红黑树本质也是一种二叉搜索树。底层结构需要使用二叉搜索树的地方，基本上都会使用红黑树来实现，而AVL树也因此坐上了冷板凳。
红黑树通过在每个节点上添加一个存储位，用于存储“RED”或“BLACK”。通过节点上红/黑颜色限制，确保最长路径不超过最短路径的两倍，因而它是接近平衡的树形结构。最短路径：全黑；最长路径：一黑一红交替。
1、红黑树的根节点是黑色的；
2、没有连续的红色节点（如果某个节点为红色，则它的左右孩子必须是黑色）
3、无论哪个节点，其每条路径的黑色节点数量相同；
4、所有的空节点（NIL节点）可以认为是黑色的。
最优情况：全黑或每条路径都是一黑一红的满二叉树，高度logN
最差情况：每颗子树左子树全黑，右子树一黑一红。高度2*logN。
可以发现，最坏情况的时间复杂度和AVL树一样，都是O(logN)，但是红黑树这种近似平衡的结构减少了大量旋转，综合性能优于AVL树。
新节点给红色，可能会违反上面说的红黑树性质2；如果新节点给黑色，必定会违反性质3。
情况一调整后可能变成情况一、情况二、情况三。
这种情况cur、parent、grandfather都是确定颜色的，唯独uncle的颜色是不确定的。
可以这么想：cur为红那么就需要将parent变为黑；parent变黑需要控制每条路径上黑节点的数量相同，那么就要把uncle变黑；如果grandfather不是根，需要反转为红，用以控制路径黑节点数量相同。继续向上调整即可。
uncle的情况分两种。
uncle不存在，则cur为插入节点，单旋即可。
uncle存在且为黑是第一种情况变过来的。
uncle的情况分两种。
uncle不存在，则cur为插入节点，两次单旋即可。
uncle存在且为黑，先掰直
插入新节点时，父节点为红，看叔叔的颜色。
1、叔叔存在且为红，变色，向上调整（可能变为三种情况中的任意一种）
2、叔叔不存在/存在且为黑，直线。单旋+变色
3、叔叔不存在/存在且为黑，折线，两次单旋+变色
bool Insert(const pair<K,V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//根节点给黑色
return true;
}
//_root不为空
Node* parent = nullptr;
Node* cur = _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;
}
//开始插入
cur = new Node(kv);
cur->_col = RED;//新插入节点给红色，可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同，必定违反规则。
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;//维护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 != nullptr && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else//情况二或情况三
{
if (cur == parent->_left)//情况二，直线
{
RotateRight(grandfather);//右单旋
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三，折线
{
RotateLeft(parent);//左单旋
RotateRight(grandfather);//右单旋
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//如果父亲是祖父的右孩子
{
Node* uncle = grandfather->_left;
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col =uncle->_col= BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//情况二，直线
{
//g
// p
// c
RotateLeft(grandfather);//左单旋
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三，折线
{
//g
// p
//c
RotateRight(parent);//右单旋
RotateLeft(grandfather);//左单旋
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col=BLACK;
return true;
}bool Check(Node* root,int blackNum,const int ref)//检查有没有连续红节点
{
if (root == nullptr)
{
if (blackNum != ref)
{
cout << "路径上黑节点数量不一致" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "违反规则，父子均为红" << endl;
return false;
}
return Check(root->_left, blackNum,ref) && Check(root->_right, blackNum, ref);
}
bool _IsBalance()
{
if (_root == nullptr)
return true;
if (_root->_col != BLACK)
{
return false;
}
//数一下一条路径黑色节点数量
int ref = 0;//统计一条路上黑色节点的数量
Node* left = _root;
while (left != nullptr)
{
if (left->_col == BLACK)
{
++ref;
}
left = left->_left;
}
return Check(_root,0,ref);
}1、在_IsBalance中确定号一条路径中黑色节点的数量，作为参数传递给Check函数，Check函数需要在递归至根节点时，统计，每条路径黑色节点数量是否和基准值ref相等。
2、Check函数中还需要判断：子节点为红，父节点也为红（此时不平衡）
#pragma once
#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
enum Color
{
RED,
BLACK,
};
template <class K,class V>
struct RBTreeNode
{
RBTreeNode(const pair<K,V>& kv)
:_parent(nullptr)
,_left(nullptr)
,_right(nullptr)
,_kv(kv)
,_col(RED)
{}
RBTreeNode<K,V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
pair<K, V> _kv;
Color _col;
};
template <class K, class V>
class RBTree
{
public:
typedef RBTreeNode<K,V> Node;
bool Insert(const pair<K,V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//根节点给黑色
return true;
}
//_root不为空
Node* parent = nullptr;
Node* cur = _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;
}
//开始插入
cur = new Node(kv);
cur->_col = RED;//新插入节点给红色，可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同，必定违反规则。
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;//维护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 != nullptr && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else//情况二或情况三
{
if (cur == parent->_left)//情况二，直线
{
RotateRight(grandfather);//右单旋
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三，折线
{
RotateLeft(parent);//左单旋
RotateRight(grandfather);//右单旋
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//如果父亲是祖父的右孩子
{
Node* uncle = grandfather->_left;
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col =uncle->_col= BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//情况二，直线
{
//g
// p
// c
RotateLeft(grandfather);//左单旋
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三，折线
{
//g
// p
//c
RotateRight(parent);//右单旋
RotateLeft(grandfather);//左单旋
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col=BLACK;
return true;
}
void Inorder()
{
_Inorder(_root);
}
bool IsBalance()
{
return _IsBalance();
}
private:
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
bool Check(Node* root,int blackNum,const int ref)//检查有没有连续红节点
{
if (root == nullptr)
{
if (blackNum != ref)
{
cout << "路径上黑节点数量不一致" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "违反规则，父子均为红" << endl;
return false;
}
return Check(root->_left, blackNum,ref) && Check(root->_right, blackNum, ref);
}
bool _IsBalance()
{
if (_root == nullptr)
return true;
if (_root->_col != BLACK)
{
return false;
}
//数一下一条路径黑色节点数量
int ref = 0;//统计一条路上黑色节点的数量
Node* left = _root;
while (left != nullptr)
{
if (left->_col == BLACK)
{
++ref;
}
left = left->_left;
}
return Check(_root,0,ref);
}
void RotateLeft(Node* parent)//左单旋
{
Node* grandfather = parent->_parent;
Node* cur = parent->_right;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (grandfather->_left == parent)//需要判定parent原来属于grandfather的哪一边
grandfather->_left = cur;
else
grandfather->_right = cur;
cur->_parent = grandfather;
}
parent->_right = cur->_left;
if (cur->_left != nullptr)
cur->_left->_parent = parent;
cur->_left = parent;
parent->_parent = cur;
}
void RotateRight(Node* parent)//右单旋
{
Node* grandfather = parent->_parent;
Node* cur = parent->_left;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (grandfather->_left == parent)
{
grandfather->_left = cur;
cur->_parent = grandfather;
}
else
{
grandfather->_right = cur;
cur->_parent = grandfather;
}
}
parent->_parent = cur;
parent->_left = cur->_right;
if (cur->_right != nullptr)
cur->_right->_parent = parent;
cur->_right = parent;
}
private:
Node* _root=nullptr;
};
void TestAVLTree()
{
//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//int a[] = { 9,8,7,6,5,4,3,2,1};
RBTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.Inorder();
//cout << t.IsBalance() << endl;
}我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01 客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02 数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit
文章目录一、概述简介原理模块二、配置Mysql使用版本环境要求1.操作系统2.mysql要求三、配置canal-server离线下载在线下载上传解压修改配置单机配置集群配置分库分表配置1.修改全局配置2.实例配置垂直分库水平分库3.修改group-instance.xml4.启动监听四、配置canal-adapter1修改启动配置2配置映射文件3启动ES数据同步查询所有订阅同步数据同步开关启动4.验证五、配置canal-admin一、概述简介canal是Alibaba旗下的一款开源项目，Java开发。基于数据库增量日志解析，提供增量数据订阅&消费。Git地址：https://github.co
HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候
我正在尝试在Rails上安装ruby，到目前为止一切都已安装，但是当我尝试使用rakedb:create创建数据库时，我收到一个奇怪的错误:dyld:lazysymbolbindingfailed:Symbolnotfound:_mysql_get_client_infoReferencedfrom:/Library/Ruby/Gems/1.8/gems/mysql2-0.3.11/lib/mysql2/mysql2.bundleExpectedin:flatnamespacedyld:Symbolnotfound:_mysql_get_client_infoReferencedf