C++实现红黑树核心插入实例代码.docx

第

C++实现红黑树核心插入实例代码

目录一、红黑树概念介绍二、红黑树模拟实现（1）红黑树节点（2）红黑树插入分析(核心)（3）插入代码思路(如何快速写插入算法)（4）判断平衡函数（5）查找函数（6）测试函数（7）测试结果三、红黑树源代码（1）RbTree.h（2）Test.cpp总结

一、红黑树概念介绍

概念：

红黑树，也是一种二叉搜索树，它是在每个结点上增加一个存储位表示结点的颜色，可以是红或黑，然后通过对任何一条从根到叶子的路径上各个结点着色方式的限制，保证了没有一条路径会能超过其他路径的俩倍，因而是近似平衡的。map和set的底层数据结构就是用红黑树来封装的。

性质：

1.根节点是黑色的

2.不能出现连续的红色节点

3.每条路径上有相同数量的黑色节点

4.每个叶子(空节点)结点都是黑色

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

满足上面的性质，红黑树就能保证：最长路径中节点个数不会超过最短路径节点个数的2倍。

优势：

假设全部的黑色节点有N个最短路径长度是logN整棵树的节点数量：[N,2N]，最长路径长度：2logN。假设10亿个节点，AVL：最多查找30次左右；RB：最多查找60次左右。

综合而言，其实对于查找大量数据30次和60次没太大差别，而红黑树不要求绝对平衡，只需保证最长路径不超过最短路径的2倍，相对来说降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优。

二、红黑树模拟实现

（1）红黑树节点

enumColor

RED=0,

BLACK,

templateclassK,classV

structRbTreeNode

RbTreeNodeK,V*_left;

RbTreeNodeK,V*_right;

RbTreeNodeK,V*_parent;

pairK,V

Color_col;

RbTreeNode(constpairK,Vkv)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_kv(kv)

,_col(RED)

};

里面同样用三叉链，要有左孩子右孩子，父节点，以及pair类的类型来存储kv两个相同或不同类型的值(当我们使用make_pair函数创建一个pair对象，该函数会自动推断参数类型)，并在里面增加一个枚举，用来表示一个节点不是红色就是黑色。关于构造函数里面的颜色初始化为黑色还是红色，在插入会讲解。

（2）红黑树插入分析(核心)

插入和前面的AVL插入部分是一样的，在里面如果是根节点，那就把跟点为置为黑色。

那这有一个问题就是节点构造函数里面的一个问题：我们在申请一个新节点时，宁愿新增红色还是黑色？

因为不管是增哪种颜色，本质上是违反规则三还是违反规则四的问题，如果插入黑色，一定违反规则四，但它代价太大，违反规则三就不一定，因为它的父节点可能为红色也可能为黑色，如果在黑色节点下面插入就没影响，反之就会影响。

对于上面的做法会出现下面的两大情况，第一GPC为一一条直线，第二GPC为折线。

如图：

G为祖父节点，P为父亲节点，C为当前节点，U为叔父节点

1、先解决当GPC为一条直线的时候：

（1）如果U存在且为红色，P必须变黑，U也得变黑，左右都增加了黑，那就把G变红,这样久能保持黑色节点不变，因为G现在变成红了，但是G的父节点如果是红色的还得继续处理，那就把G当成C节点，继续算它的祖父，再看U，如果U是红再把它变成黑。

它的所对应的抽象图以及具象图：

（2）如果U不存在或者存在且为黑又是两种情况

如果U不存在，再增加红节点，且有连续的红色节点，有可能会超过它的最短路径，只能旋转来降高度。把P变黑，把G给P的左，再把P作为左，同时把原来的G变红，这里就是左单旋加G和P变色。

如下例图：

它所对应的抽象及具象图：

如果U存在且为黑色

U存在且为黑是由第一种请况变化而来，这里发生了右单旋，P的左孩子作为G的左孩子，而G又作为P的右孩子，且P变为黑，G变为红。

对于上面的U不存在或者存在为黑两种情况进行总结：P为G的左孩子时，C为P的左孩子进行右单旋转，如果P为G的右孩子，C为P的右孩子，进行左单旋转。P变为黑色，G变为红色。

旋转的目的就是为了防止最长路径超过最短路径