看了这么多篇红黑树文章，你领略了嘛？

我们照旧举个例子，好比我们在最开始的红黑树基本之上插入节点21，此时会产生什么环境呢?

此时照旧老端正，比较着红黑树的5个特性一个一个来看，只要是违背了一条就必要做出调解。我们来看一下：

(1)每个节点只有两种颜色：赤色和玄色。这一条满意。

(2)根节点是玄色的。这一条也满意。

(3)每个叶子节点(NIL)都是玄色的空节点。这一条满意。

(4)从根节点到叶子节点，不会呈现两个持续的赤色节点。这一条发明不满意。

就是上面这一条法则没有满意，以是我们此时必要调解?题目来了怎样调解呢?由于直接看父节点没步伐实现，以是还必要调查其它的节点，也就是新节点的叔叔节点。按照叔叔节点的颜色来调解。调解的方法有两种：变色和旋转。

(1)叔叔节点是赤色：

此时插入的节点是21，可是叔叔节点是27，更好是赤色。我们直接来看调解的步调：

第一步：把新节点21的父节点22酿成玄色。

此时从头看一下是否满意红黑树的五条特性了没，一条一条发明，第五条没有满意，也就是从任何一个节点出发，到叶子节点，这条路径上没有沟通数量标玄色节点。好比从25出发。这时辰怎么办呢?那就继承调解。

第二步：把22的父节点25酿成赤色

这时辰照旧老端正，不要嫌弃贫困，由于只有经验了一步又一步的贫困之后，你才气紧记那5条法则特性。我们比较之后会发明节点25和节点27是两个持续的赤色节点，这时辰又粉碎了法则4。怎么办呢?那就继承调解就OK了。

莫非这时辰还要继承往上调解吗?假如你这样做就错了，由于不绝地往上调解最后就会把根节点酿成了赤色，会走进死胡同。我们往下走。

第三步：把节点27酿成玄色

来吧，继承从头检察那5条法则特性。很明明节点17和节点25是两个持续的赤色，又粉碎了。是不是心太累了，调解了这么久，照旧没有担保那5条法则，感受是不是还没有均衡二叉树好。假如你此刻有这种感受，我只能说，但愿你继承僵持下去，胜利就在面前。

第四步：把节点17和节点18都酿成玄色节点

来来来，此刻你再比较一下那5条法则，是不是完全担保了。写到这真的是太累了，和你读这篇文章的感受一样一样的，不外这种环境壹贝偾插入环境中的一种。继承往下看：

(1)叔叔节点是玄色：

这种环境下又分了两种环境：

第一种环境：新插入节点为父节点的左孩子

第二种环境：新插入节点为父节点的右孩子

凭证第一遍的思绪，我们对这两种环境执行同样的操纵，最终也能担保红黑树的5条特性。

到了这一步，插入操纵的全部环境就讲授完毕。其它关于左旋和右旋的常识我在这里不再声名白，由于你看到了红黑树这个水平，信托也必然看过均衡二叉树。左旋右旋哪几种环境，城市有先容到。

3、删除节点

红黑树的删除说真话越发的伟大，假如你看过算法导论的话应该能大白一点，我们在这里也举办一个或许的讲授。

删除大抵分了三种环境，

(1)第一种环境：要删除的节点有零个子节点

这种环境下最简朴，也就是删除的是根节点可能是叶子节点(这里的叶子节点都是指非NULL的叶子节点)，根节点直接删除即可。假如叶子节点是赤色的，也可以直接删除，假如叶子节点是玄色的，那么就必要举办调解，调解的步协调插入时调解的步调一样。

(2)第二种环境：要删除的节点有一个子节点

这时辰。把子节点的值替代掉要删除的节点的值。

此刻我们的5把11替代掉之后，又回到了第一种环境。假如节点5是赤色的，可以直接删除，假如节点5是玄色的，那么就必要举办调解，此时的节点5就是叶子节点。调解的步协调插入时调解的步调一样。

(3)第三种环境：要删除的节点有两个子节点

此刻删除的节点有两个子节点，同样的我们可以执行第二种环境的操纵，

若节点13之前是叶子节点，那就和第一种环境一样了，假如节点13是赤色的，可以直接删除，假如节点13是玄色的，那么就必要举办调解，此时的节点13就是叶子节点。调解的步协调插入时调解的步调一样。

若节点13之前尚有子节点，那就和第二种环境一样了。那就继承替代和判定。

以上呢就是删除的环境，最后一种环境是修改，这种环境是查找和插入的团结体，也就是先找到要修改的元素，修改完值之后，继承举办调解即可。

此刻尚有最后一个题目了，都说红黑树很重要，为什么重要呢?我们来看一下行使场景。

四、行使场景

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!