欢迎来到军工软件开发人才培养基地——学到牛牛

红黑树的基本概念与结构

时间:2024-05-06 07:01:10 来源:学到牛牛

1、红黑树的简介:

红黑树是一种自平衡的二叉查找树,是一种高效的查找树。红黑树具有良好的效率,它可在 O(logN) 时间内完成查找、增加、删除等操作。

红黑树是具备了某些特性的二叉查找树,能解决非平衡树问题,是一种接近平衡的二叉树(说它是接近平衡因为它并没有像AVL树的平衡因子的概念,它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构,进而提升整体的性能,并没有严格的卡定某个平衡因子来维持绝对平衡)。

2、红黑树的特性:

红黑树保证最长路径不超过最短路径的二倍(最短路径就是全黑节点,最长路径就是一个红节点一个黑节点,当从根节点到叶子节点的路径上黑色节点相同时,最长路径刚好是最短路径的两倍)。

一颗典型的红黑树如下:

 

在其中我们可以发现一些明显的特点,比如:

· 节点不是红色就是黑色,根节点为红色

· 红黑树的叶子节点是空节点,而不是传统的叶子节点

· 同一路径不存在连续红节点

 

以上只是红黑树的部分规则,红黑树规则如下:

(1)根是黑色

(2)节点是红色或黑色

(3)叶子节点都是黑色(最底层的空节点)

(4)从任意节点到叶子节点的所有路径都包含相同数目的黑色节点

(5)红色节点的子节点都是黑色,红色节点的父节点都是黑色,从根节点到叶子节点的路径上不能有2个连续的红色节点

 

在上述五个规则之中,还有以下特点:

· 规则4与规则5保证了红黑树的大致平衡,根到叶子的所有路径中最长路径不会超过最短路径的2倍。

· 使红黑树在最坏的情况下,也可以有O(log2​N)的查找效率。

· 关于叶子节点:NULL代表空节点。

默认新插入的节点为红色,因为父节点黑色的概率较大,这样可以避免颜色冲突。

 

红黑树操作:

红黑树操作和其他树形结构差不多,一般操作包括基本的查找、插入、删除等。相对于查找,红黑树的插入和删除操作要相对复杂一些。

1、自平衡策略:

在插入或删除后沿着节点到根的路径执行左旋、右旋、变色,就能让树重新满足定义。

旋转操作分为左旋与右旋。左旋是将某个节点旋转为其右子节点的左子节点,右旋是将节点旋转为左子节点的右子节点。

左旋:

右旋:

变色:

对于当前节点而言,若左右子节点均为红色,则执行变色。

2、插入操作:

插入时新节点默认为红色,若插入后依然满足红黑树定义,则插入完成。否则,根据叔叔节点进行调整。

叔叔节点为黑色时:LL型、RR型、LR型、RL型。

叔叔节点为红色时:叔叔节点、父亲节点、爷爷节点全变色,爷爷节点变新节点,然后再进行一轮调整。

3、删除操作:

相对于插入而言,红黑树的删除要稍微复杂一些。

· 若待删除节点为红色节点,则直接删除即可。

· 若待删除节点为黑色节点,且其孩子节点为红色,则将待删除节点替换为孩子节点,并将孩子节点由红转黑即可。

· 若待删除节点为黑色节点,且其孩子节点为黑色,则需要进一步解决。

针对最后一种删除,首先将待删除节点替换为它的孩子节点,并设定为节点N,N沿用原待删除节点(对父子节点)的称呼。但注意,实际删除的是原待删除节点,且删除后通过N的路径长度-1。

具体情况如下:

①.N是新的根。

此时不做任何调整。

②.N的父节点、兄弟节点、以及兄弟节点的孩子节点均为黑色。

将兄弟节点变为红色,然后继续递归向上判定。

③.N的兄弟节点为红色,其余节点均为黑色。

左旋,然后将父节点与兄弟节点的颜色互换。

④.N的父节点为红色,兄弟节点及兄弟节点的孩子节点均为黑色。

将父节点与兄弟节点的颜色互换。

⑤.N的兄弟节点为黑色,兄弟节点的左孩子为红色,右孩子为黑色。

右旋,然后将兄弟节点与兄弟节点左孩子的颜色互换。

⑥.N的兄弟节点为黑色,兄弟节点的右孩子为红色。

左旋,将父节点与兄弟节点颜色互换。