红黑树

红黑树是一种很常用的自平衡二叉树。之前写过二叉搜索树,我们知道二叉搜索树查找速度是由树的高度决定的,但是因为二叉搜索树对树的平衡没什么限制,如果所有节点都在一个叉上,就变成了链表了。红黑树作为二叉搜索树的同时,用以下五个性质保证了树的平衡:

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

因为这些性质,一棵红黑树尽量保持每个路径上节点数差距不大,从来保证了树的查找速度。

红黑树

红黑树是一颗二叉搜索树,其查找方法自然也就是二叉搜索树的查找方法。因为给二叉搜索树节点涂了颜色,树上面的修改操作(如插入、删除)会影响红黑树的某些性质,恢复其性质需要需要O(log n) 次操作。

下面讲解一下红黑树的一些操作:

旋转

树的旋转是一种子树调整的操作,旋转分为左旋和右旋,这两种操作互为可逆操作,通过这种调整,树的中序遍历结果是不变的,一般用于调整数的平衡性。一般在插入和删除时,可以通过旋转和重新涂色来修复红黑树性质。

左旋

左旋40这颗子树,右孩子(60)占领其父节点(40)位置,其父节点(40)转为其(60)子节点,作为升级的代价,其左孩子节点(50)交给父节点(40)作为右孩子节点(主要是因为其左孩子节点变成了其父节点,所以自己的左孩子节点就交给了其新的左孩子作为右孩子):

红黑树左旋

右旋

以下是对80这棵树做的一次右旋操作,其操作和左旋是相反的,左孩子(40)占领其父节点(80)位置,父节点(80)转为右孩子,原来的右孩子(60)交给新的右孩子(80)做左孩子:

红黑树右旋

可以看到,选择保持了二叉搜索树的特性,颜色却不符合红黑树的特性了,所以红黑树旋转并不是一种等价转换方法,转换后需要重新涂色才能保证红黑树的性质。

插入节点

因为红黑树是一个二叉搜索树,插入节点的方法也和二叉搜索树差不多,插入到叶子节点位置,然后再考虑红黑树特有的颜色问题。

如果插入一个黑色节点,因为到【性质5】的存在,整个事情会变得比较棘手,所以新增的节点应该是一个红色节点,如此一来则有可能违背【性质2】或者【性质4】。碰到这两种情况就需要通过穷举来处理了:

  1. 违背【性质2】,新增节点为根节点,直接涂黑;
  2. 违反【性质4】,这种情况只有在新增节点的父节点是红色节点时才出现,同时可知其祖父节点一定是黑色的,如果存在兄弟节点,兄弟节点也是黑色的。此时处理需要分以下情况:
    1. 叔节点是红色。因为自己是红色,父节点和树节点涂黑以保持性质,祖父节点为了保持【性质5】而涂红。如此一来就进入了递归状态,开始根据其祖父节点的颜色进行调整;

      红黑树插入,叔节点是红色

      红黑树插入,叔节点是红色

    2. 叔节点是黑色,这时候不能通过批量涂色来解决,就只好看节点在树种的具体位置了:
      1. 父节点是左子树,新增节点是左孩子节点。这时候对其祖父节点子树做一次右旋,父节点和祖父节点交换一下颜色,这样其父节点就变成了黑色,兄弟节点(曾经的祖父节点)是红色,兄弟节点的两个子节点应该是之前自己的兄弟节点和叔节点,这两个节点为黑色,所有性质全部保持;

        插入左孩子,叔节点是黑色

        插入左孩子,叔节点是黑色

      2. 父节点是左子树,新增节点是右孩子节点。对新增节点的父节点子树进行一次左旋,自己作为叶子节点没孩子,父节点即使有孩子也不影响其孩子节点颜色。这时候情况就变成了【情况2.2.1】,递归处理即可;

        左子树插入右孩子,叔节点是黑色

        左子树插入右孩子,叔节点是黑色

删除节点

想要了解如何删除节点,首先要理解二叉搜索树的删除逻辑:找到这个节点的中序遍历后继节点,后继节点和删除节点交换位置后删除应删除的节点,在代码的处理上只需要替换删除节点的值为后继节点的值,然后干掉后继节点就可以了。

如果我们恰好删除了一个红色的,那么对整棵树是没什么影响的,红黑树的性质都可以保住。但是如果删除的恰好是一个黑色的节点,就会影响当前红黑树的性质,我们穷举一下会违反的情况:

  1. 黑高肯定是变了,违反【性质5】;
  2. 如果删除的根节点,根节点的孩子是红色变成了新的根节点,违反【性质2】;
  3. 被删除节点的父节点和子节点都是红色的,删除后会违反【性质4】。

为了临时维护红黑树性质,假设被删除节点的孩子节点除了自己永远本色外还额外涂了黑色,这个多余出来的黑色想办法让别人接手(比如某个红色节点),然后再删掉这个点,这样黑色的个数总体来讲是不变的,这样也就解决了【问题1】,红色节点接手黑色自己变黑也就解决了【问题2】、【问题3】,但在这之前,我们需要主动违反【性质1】,不破不立。

好了,开始进入正题。

首先使用二叉搜索树的删除逻辑找到真正要删除的节点,然后我们开始使用重色方式来做调整,这个重色节点可能是【双黑】或者【红黑】,具体调整方法可以穷举出以下情况(假设重色节点是左孩子节点,若是右孩子节点则反过来处理):

  1. 重色节点恰好是【红黑】,直接涂黑是不影响红黑树性质的,涂黑结束;
  2. 重色节点是【双黑】:
    1. 其兄弟节点是红色的,把兄弟节点染成黑色,父节点染成红色,因为节点是重黑色,左旋父节点子树依然可以保持红黑树性质,这样就变成了兄弟节点是黑色,见【情况2-B】;

      双黑红色兄弟节点

      双黑红色兄弟节点

    2. 兄弟节点是黑色:
      1. 兄弟节点的两个儿子都是黑色:把重色节点的黑色去掉,兄弟节点涂红,父节点附加黑色,如此一来,重色节点恢复本色;兄弟节点作为红色节点,父子都是黑色;整体的黑高也没有变化;所以红黑树性质不受影响。父节点作为双色节点进入递归;

        双黑节点黑兄弟黑侄子,父节点可能是红色也可能是黑色。

        双黑节点黑兄弟两黑侄子,父节点可能是红色也可能是黑色。绿色表示双黑或红黑,灰色表示可能是任何颜色,紫色表示双黑。节点20经过处理后可以删除,其多出来的那个黑色已经转移到了30上面。后续再递归整理30的颜色。

      2. 兄弟节点的左孩子是红色,右孩子是黑色:兄弟节点和其左孩子节点交换颜色,右旋兄弟节点子树,进入【情况2-B-iii】;

        双黑节点黑兄弟左红右黑侄子,灰色代表可能为任何颜色

        双黑节点黑兄弟左红侄子右黑侄子,灰色代表可能为任何颜色,紫色为双黑节点

      3. 兄弟节点的右孩子是红色:父节点和兄弟节点交换颜色,兄弟节点的右孩子涂黑,重色节点去掉额外的黑色,对父节点子树进行一次左旋,此时黑色节点数量不变,红色节点少了一个,相当于当前节点的黑色交给了兄弟节点的红色右孩子节点。调整结束。

        双黑节点黑兄弟右红侄子,灰色代表可能为任何颜色

        双黑节点黑兄弟右红侄子,灰色代表可能为任何颜色

根据以上分析可以得出,删除时最坏情况是经过【情况2-A】,然后经过【情况2-B-ii】,最后是【情况2-b-iii】,最多3次经过旋转。

代码如下:

头文件brtree.h

实现 brtree.c:

test.c

如有问题,还请帮忙纠正,谢谢。

红黑树》上有5条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注