红黑树的创建

红黑树的创建

在二叉查找树的最后提到, 二叉树最终的形状如下图所示:

实际上,为了避免二叉树形状向最坏情况靠拢, 通常会创建能够自平衡的 2-3 树。 而 红黑树 是 2-3 树比较简单的一种实现形式:

  1. 红黑树将用二叉树表示 2-3 树, 实现起来相对容易;
  2. 内部使用向左倾斜的链接表示第三个节点;

红黑树定义如下:

  • 没有任意节点拥有两个红色链接;
  • 从跟节点到末节点的黑色链接数目相等;
  • 红色节点向左倾斜;

用红黑树来表示 2-3 树例子:

红黑树的节点定义

节点定义

在二叉查找树节点的基础上增加一个 Color 字段, 相关代码如下:

// Color Const, Red As true, Black as false
private const bool Red = true;
private const bool Black = false;

private class Node {
    public TKey Key;
    public TValue Val;
    public Node Left, Right;
    public bool Color; // Color
}

// Check node's color.
private static bool IsRed(Node h) {
    if (h == null) {
        return false;
    }
    return h.Color == Red;
}

红黑树的创建

红黑树的创建和二叉查找树类似, 为了在添加节点时维持节点的顺序和树的平衡性, 增加了如下一些操作:

左旋

将一个临时向右倾斜的红色链接向左旋转, 如下图所示:

对应的 c# 实现代码如下:

private Node RotateLeft(Node h) {
    Debug.Assert(h != null && IsRed(h.Right));
    Node x = h.Right;
    h.Right = x.Left;
    x.Left = h;
    x.Color = x.Left.Color;
    h.Color = Red;
    x.N = h.N;
    h.N = Size(h.Left) + Size(h.Right) + 1;
    return x;
}

右旋

将左倾的红色链接向右旋转为临时的向右倾斜的红色链接, 如下图所示:

对应的 c# 实现代码如下:

private Node RotateRight(Node h) {
    Debug.Assert(h != null && IsRed(h.Left));
    Node x = h.Left;
    h.Left = x.Right;
    x.Right = h;
    x.Color = x.Right.Color;
    h.Color = Red;
    x.N = h.N;
    h.N = Size(h.Left) + Size(h.Right) + 1;
    return x;
}

翻转颜色

将节点的左右链接(临时情况)由红色改为黑色, 如下图所示:

对应的 c# 实现代码如下:

private void FlipColors(Node h) {
    Debug.Assert(h != null && h.Left != null && h.Right != null);
    Debug.Assert((!IsRed(h) && IsRed(h.Left) && IsRed(h.Right))
        || (IsRed(h) && !IsRed(h.Left) && !IsRed(h.Right)));
    h.Color = !h.Color;
    h.Left.Color = !h.Left.Color;
    h.Right.Color = !h.Right.Color;
}

添加节点

有了上面定义的几个操作, 添加节点分两种情况:

  1. 向单节点添加新节点, 在底部形成双节点, 如下图所示:

这种情况下比较容易处理, 需要的步骤如下:

  1. 按照二叉查找树的方式添加节点, 将新节点标记为红色;
  2. 如果新节点是其父节点的右链接, 则进行左旋操作;

  1. 向双节点添加新节点, 在底部形成三节点, 如下图所示:

这种情况稍微麻烦一些, 需要的步骤如下:

  1. 按照二叉查找树的方式添加节点, 将新节点标记为红色;
  2. 如果需要, 通过旋转形成临时的四节点;
  3. 翻转颜色, 将红色链接上移一层;
  4. 如果需要, 通过旋转形成左倾的红色节点;
  5. 如果需要, 以此方法向上递归;

最终红黑树添加节点的 c# 代码如下:

public void Put(TKey key, TValue val) {
    root = Put(root, key, val);
    root.Color = Black;
    Debug.Assert(Check());
}

private Node Put(Node h, TKey key, TValue val) {
    if (h == null) {
        return new Node(key, val, Red, 1);
    }
    int cmp = key.CompareTo(h.Key);
    if (cmp < 0) {
        h.Left = Put(h.Left, key, val);
    }
    else if (cmp > 0) {
        h.Right = Put(h.Right, key, val);
    }
    else {
        h.Val = val;
    }

    if (IsRed(h.Right) && !IsRed(h.Left)) {
        h = RotateLeft(h);
    }
    if (IsRed(h.Left) && IsRed(h.Left.Left)) {
        h = RotateRight(h);
    }
    if (IsRed(h.Left) && IsRed(h.Right)) {
        FlipColors(h);
    }

    h.N = Size(h.Left) + Size(h.Right) + 1;

    return h;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 在虚拟目录中部署 ASP.NET Core 应用

    ASP.NET Core 已经发布了 2.0 RC1 (Go Live) 版本, API 已经不在变化, 但是很多人期待的已久的在虚拟目录中部署的功能还是没有出...

    beginor
  • 设计模式之状态模式

    Allow an object to alter its behavior when its internal state changes. The objec...

    beginor
  • 在 Ubuntu Server 上安装配置 Mono 生产环境

    在 Ubuntu Server 上安装和配置 Apache2 + Mono 生产环境的记录。 服务器环境是 Ubuntu Server 13.04 虚拟机模式 ...

    beginor
  • 有效的学习C语言,易懂,趣味,实用的成长之路

    学好C语言的秘诀就是1234:“一字真言,两种态度,三个框架,四项注意”。 各位看官,学好C语言,其实只需一个字,那就是“编”。 学习C语言,乃至学习所有的语言...

    企鹅号小编
  • FDRNet|混合降质图像复原

    paper: https://arxiv.org/pdf/2007.11430.pdf

    AIWalker
  • 转行大数据,编程学Java还是Python?

    Python和Java,是大数据行业最常见的两种编程语言,对于想转行大数据的人来说,学习哪个语言是比较好的选择呢?

    加米谷大数据
  • PDO::prepare讲解

    PDO::prepare — 准备要执行的SQL语句并返回一个 PDOStatement 对象(PHP 5 = 5.1.0, PECL pdo = 0.1....

    砸漏
  • Java魔法堂:URI、URL(含URL Protocol Handler)和URN

    一、前言                                 过去一直搞不清什么是URI什么是URL,现在是时候好好弄清楚它们了!本文作为学习笔记,...

    ^_^肥仔John
  • 百度地图API开发指南(三)

    首先您需要定义自定义覆盖物的构造函数,在下面的示例中我们定义一个名为SquareOverlay的构造函数,它包含中心点和边长两个参数,用来在地图上创建一个方形覆...

    幽鸿
  • HTML中百度地图的使用

    越陌度阡

扫码关注云+社区

领取腾讯云代金券