红黑树:强大的数据结构之插入详解,附图

一、红黑树概述

红黑树是一种自平衡二叉查找树,具有以下性质:节点要么是红色要么是黑色;根节点是黑色;每个叶子节点(NIL 节点)是黑色;每个红色节点的两个子节点都是黑色;从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

在插入新节点时,新节点初始颜色为红色,这样可以尽量减少对树结构的影响。但如果新节点的父节点也是红色,就会违反红黑树的性质,此时需要进行调整。红黑树插入新节点主要有以下四种情况:

  1. 新节点位于根节点:若新节点位于根节点,其没有父节点时,将该节点直接设为黑色即可。
  1. 新节点的父节点已然是黑色:这种情况下不用进行调整,因为这已经是一棵符合红黑树性质的树。
  1. 父节点和叔节点都是红色:将父节点和叔节点设为黑色,将祖父节点设为红色,并将祖父节点设为当前节点,继续对新当前节点进行操作。
  1. 父节点是红色,叔节点是黑色:又分为四种情况。
    • 当前节点是父亲的左孩子,父亲是祖父的左孩子(Left-Left):将祖父节点右旋,交换父节点和祖父节点的颜色。
    • 当前节点是父亲的右孩子,父亲是祖父的左孩子(Right-Left):将父节点左旋,并将父节点作为当前节点,然后再使用 Left-Left 情形。
    • 当前节点是父亲的右孩子,父亲是祖父的右孩子(Right-Right):将祖父节点左旋,交换父节点和祖父节点的颜色。
    • 当前节点是父亲的左孩子,父亲是祖父的右孩子(Left-Right):将父节点右旋,并将父节点作为当前节点,然后再使用 Right-Right 情形。

通过这些规则和调整方法,可以确保在插入新节点后,红黑树依然保持其自平衡的性质。红黑树在计算机科学中有广泛的应用,如在 Java 的集合框架、数据库索引、操作系统内核等领域都发挥着重要作用。

红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的,则它的两个孩子结点是黑色的----就是说:  一条路径中没有连续的红色节点
4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点----每条路径黑色节点数量是相等的
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

二、主要两种情况加图分析

其实主要是俩种情况,其它都是变形出来的

P:parent

G:grandfather

U:uncle

三角形可以理解为完整的红黑树,或者空节点,不予考虑

情况1:cur为红 p、u为红,g为黑

解决:p和u变黑、g变红(g不为根)

情况2:cur为红,p为红g为黑,u不存在/u存在且为黑 

1、u不存在、abcde都是空,cur是新增   :右旋,p变黑,g变红

2、u存在且为黑     de是空或红,c是有一个黑色节点的红黑树,cur是黑的是由情况一变红的

情况一:

如果g是根节点,调整完成后,需要将g改为黑色如果g是子树,9一定有双亲,且g的双亲如果是红色,需要继续向上调整

情况二

说明:u的情况有两种
1.如果u节点不存在,则cur一定是新插入节点,因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色,就不满足性质4:每条路径黑色节点个数相同。
2.如果u节点存在,则其一定是黑色的,那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。
p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,p为g的右孩子,cur为p的右孩子,则进行左单旋转p、g变色--p变黑,g变红

插入规则与四种情况--上面的才是最重要的分析,此处是详细的四种情况

(一)新节点位于根节点

若新节点为根节点,无父节点,直接设为黑色。此情况简单直接,确保根节点满足红黑树性质。红黑树要求根节点为黑色,这样可以保证树的整体稳定性。当新插入的节点成为根节点时,为了满足红黑树的性质,必须将其颜色设为黑色。例如,在某些实际应用中,如果一开始红黑树为空,插入第一个节点时,就会将这个节点设为根节点并将其颜色设为黑色。

(二)父节点为黑色

当新节点的父节点已然是黑色时,无需调整,因这已符合红黑树的部分性质,新节点的插入不会破坏树的平衡。因为红黑树的性质规定,红色节点的子节点必须是黑色,而当父节点为黑色时,新插入的红色节点不会导致连续两个红色节点出现,也不会影响从根节点到叶子节点的路径上黑色节点的数量。所以在这种情况下,无需进行任何调整,红黑树依然保持平衡。

(三)父节点和叔节点都是红色

将父节点和叔节点设为黑色,祖父节点设为红色,然后将祖父节点作为当前节点继续进行操作。此操作通过调整节点颜色来维持红黑树的性质,避免连续红色节点和保持黑色节点数量平衡。例如,假设当前红黑树中有一个节点 A,其颜色为红色,父节点为 B,颜色也为红色,叔节点为 C,颜色同样为红色,祖父节点为 D。按照规则,将 B 和 C 的颜色设为黑色,D 的颜色设为红色,然后以 D 为当前节点继续判断是否满足红黑树的性质。如果 D 还有父节点,就继续按照红黑树的插入规则进行调整。

(四)父节点是红色,叔节点是黑色

此时又分四种情况。若当前节点是父亲的左孩子,父亲是祖父的左孩子(Left-Left),将祖父节点右旋并交换父节点和祖父节点的颜色。例如,有节点 A(当前节点)、B(父节点)、C(祖父节点),A 是 B 的左孩子,B 是 C 的左孩子,此时进行右旋操作,将 C 右旋后,交换 B 和 C 的颜色,这样可以使树重新满足红黑树的性质。

若当前节点是父亲的右孩子,父亲是祖父的左孩子(Right-Left),先将父节点左旋并将父节点作为当前节点,再按 Left-Left 情形处理。比如节点 D(当前节点)、E(父节点)、F(祖父节点),D 是 E 的右孩子,E 是 F 的左孩子,先将 E 左旋,然后以 E 为当前节点,按照 Left-Left 的情况进行处理,即对新的祖父节点进行右旋并交换颜色。

若当前节点是父亲的右孩子,父亲是祖父的右孩子(Right-Right),将祖父节点左旋并交换父节点和祖父节点的颜色。假设节点 G(当前节点)、H(父节点)、I(祖父节点),G 是 H 的右孩子,H 是 I 的右孩子,此时进行左旋操作并交换颜色,以维持红黑树的平衡。

若当前节点是父亲的左孩子,父亲是祖父的右孩子(Left-Right),先将父节点右旋并将父节点作为当前节点,再按 Right-Right 情形处理。例如节点 J(当前节点)、K(父节点)、L(祖父节点),J 是 K 的左孩子,K 是 L 的右孩子,先将 K 右旋,然后以 K 为当前节点,按照 Right-Right 的情况进行调整,即对新的祖父节点进行左旋并交换颜色。这些情况通过旋转和颜色交换来调整树的结构,确保红黑树的性质得以维持。

三、红黑树插入操作详解

红黑树是一种自平衡的二叉搜索树,通过特定的颜色规则和旋转操作来保持树的平衡。以下是对红黑树插入操作函数 Insert 的详细解释。

一、创建新节点并初始化颜色

Node* tmp = new Node(data);
tmp->_col = RED;

这段代码创建了一个新的节点 tmp,并将其颜色初始化为红色。在红黑树中,新插入的节点通常先设为红色,这样在后续的调整过程中可以更容易地满足红黑树的性质。

二、处理新节点为根节点的情况

if (_pHead->_pLeft == _pHead)
{
    _pHead = tmp;
    _pHead->_col = BLACK;
    return true;
}

如果当前树为空(头节点的左子节点指向头节点本身),那么新节点将成为根节点。此时,将新节点设为黑色,以满足红黑树的性质(根节点为黑色),并返回插入成功。

三、寻找插入位置并插入新节点

Node* cur = _pHead;
Node* parent = cur;
while (cur)
{
    if (cur->_data < data)
    {
        parent = cur;
        cur = cur->_pRight;
    }
    else if(cur->_data > data)
    {
        parent = cur;
        cur = cur->_pLeft;
    }
    else if (cur->_data == data)
    {
        return false;
    }
    else
    {
        assert(false);
    }
}
if (data > parent->_data)
{
    parent->_pRight = tmp;
}
else
{
    parent->_pLeft = tmp;
}
tmp->_pParent = parent;
cur = tmp;

这里使用一个循环来找到新节点的插入位置。如果新节点的值大于当前节点的值,就继续在右子树中查找;如果小于当前节点的值,就继续在左子树中查找。当找到合适的插入位置后,将新节点插入到父节点的相应子节点位置,并设置新节点的父指针。最后,将当前指针 cur 指向新插入的节点。

四、处理插入后可能违反红黑树性质的情况

if (parent->_col == BLACK)
{
    return true;
}
else
{
    while (parent && parent->_col!= BLACK)
    {
        Node* grandfather = parent->_pParent;
        if (parent == grandfather->_pLeft)
        {
            Node* uncle = grandfather->_pRight;
            if (cur == parent->_pLeft)
            {
                if (uncle && uncle->_col == RED)
                {
                    // 情况 1:父节点和叔节点都是红色
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = grandfather->_pParent;
                }
                else if(!uncle || uncle->_col == BLACK)
                {
                    // 情况 2:父节点为红色,叔节点为黑色,且当前节点是父节点的左子节点
                    RotateR(grandfather);
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                }
                else
                {
                    assert(false);
                }
            }
            else
            {
                if (uncle && uncle->_col == RED)
                {
                    // 情况 3:父节点和叔节点都是红色
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = grandfather->_pParent;
                }
                else if (!uncle || uncle->_col == BLACK)
                {
                    // 情况 4:父节点为红色,叔节点为黑色,且当前节点是父节点的右子节点
                    RotateL(parent);
                    RotateR(grandfather);
                    grandfather->_col = RED;
                    cur->_col = BLACK;
                }
                else
                {
                    assert(false);
                }
            }
        }
        else
        {
            Node* uncle = grandfather->_pLeft;
            if (cur == parent->_pRight)
            {
                if (uncle && uncle->_col == RED)
                {
                    // 情况 5:父节点和叔节点都是红色
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = grandfather->_pParent;
                }
                else if(!uncle || uncle->_col == BLACK)
                {
                    // 情况 6:父节点为红色,叔节点为黑色,且当前节点是父节点的右子节点
                    RotateL(grandfather);
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                }
                else
                {
                    assert(false);
                }
            }
            else
            {
                if (uncle && uncle->_col == RED)
                {
                    // 情况 7:父节点和叔节点都是红色
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = grandfather->_pParent;
                }
                else if (!uncle || uncle->_col == BLACK)
                {
                    // 情况 8:父节点为红色,叔节点为黑色,且当前节点是父节点的左子节点
                    RotateR(parent);
                    RotateL(grandfather);
                    grandfather->_col = RED;
                    cur->_col = BLACK;
                }
                else
                {
                    assert(false);
                }
            }
        }
    }
    _pHead->_col = BLACK;
    return true;
}

如果新节点的父节点为黑色,那么插入操作完成,无需进一步调整。如果父节点为红色,那么可能违反红黑树的性质,需要进行调整。

  1. 首先,判断父节点是祖父节点的左子节点还是右子节点,并确定叔节点。
  2. 如果当前节点是父节点的左子节点且叔节点为红色,那么将父节点和叔节点设为黑色,祖父节点设为红色,并将当前节点指向祖父节点,继续向上调整。
  3. 如果当前节点是父节点的左子节点且叔节点为黑色,那么进行右旋操作,并将祖父节点设为红色,父节点设为黑色。
  4. 如果当前节点是父节点的右子节点且叔节点为红色,同样将父节点和叔节点设为黑色,祖父节点设为红色,并将当前节点指向祖父节点,继续向上调整。
  5. 如果当前节点是父节点的右子节点且叔节点为黑色,先进行左旋操作,再进行右旋操作,并将祖父节点设为红色,当前节点设为黑色。

最后,将头节点设为黑色,以确保根节点为黑色。

通过以上步骤,红黑树的插入操作能够在保持树的平衡的同时,满足红黑树的性质。

上一篇:小程序兼容问题


下一篇:Github 2024-09-28Rust开源项目日报Top10-Pake: 利用 Rust 轻松构建轻量级多端桌面应用